队列

---

阅读目录

• 什么是队列
• 队列的存储结构
• 队列的常见操作及实现代码

---

1.什么是队列

队列也是一种特殊的线性表，它是一种操作受限的线性表。它只允许在表的一端进行元素插入，而在另一端进行元素删除。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(font)。
与现实生活中的排队类似，新加入的成员总是在队尾，而排在队列最前面的总是最先离开队列，即先进先出，因此队列也称为先进先出表(FIFO)。

1.队列的存储结构

队列.jpg

3.队列的常见操作及实现代码

1.初始化队列
思路：构造一个空队列，即将头指针head和尾指针rear都设置为0。

2.入队
思路：若队列不满，则将数据x插入到尾指针rear指向的位置，然后再将rear加1。

3.出队
思路：若队列不空，则将头指针head加1，并返回被删除的元素。

4.取队头

思路：若队列不空，则返回队头元素。

5.取队长
思路：即尾指针rear-头指针head。

6.判队空
思路：只需要判断头指针head与尾指针是否相等即可

7.判队满
思路：只需判断尾指针与MaxSize是否相等即可

注：在一个非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。

OC版：
SeqQueue.h:

#import <Foundation/Foundation.h>
@class Student;
//封装顺序队列
@interface SeqQueue : NSObject
@property (nonatomic,strong)NSMutableArray *data; //使用数组来存放结点
@property (nonatomic,assign)NSInteger maxSize;//最大容量
@property (nonatomic,assign)NSInteger head;//头指针
@property (nonatomic,assign)NSInteger foot;//尾指针
@end

@interface SeqQueueHelper:NSObject
//初始化
+(SeqQueue*)initSeqQueue:(SeqQueue *)queue;
//入队
+(SeqQueue *)Enter:(SeqQueue *)queue elem:(Student *)data;
//出队
+(Student *)Dequeue:(SeqQueue *)queue;
//取队头
+(Student *)GetHead:(SeqQueue *)queue;
//取队长
+(NSInteger)GetLength:(SeqQueue *)queue;

SeqQueue.m:

#import "SeqQueue.h"

@implementation SeqQueue
-(instancetype)init{
    if (self = [super init]) {
        _data = [NSMutableArray arrayWithCapacity:10];
    }
    return self;
}
@end

@implementation SeqQueueHelper
//初始化
+(SeqQueue*)initSeqQueue:(SeqQueue *)queue;
{
    queue = [SeqQueue new];
    queue.head = 0;
    queue.foot = 0;
    queue.maxSize = 3;
    return queue;
}
//入队
+(SeqQueue *)Enter:(SeqQueue *)queue elem:(Student *)data
{
    if ([self isFull:queue]) {
        return nil;
    }
    queue.data[queue.foot++] = data;
    return queue;
}
//出队
+(Student *)Dequeue:(SeqQueue *)queue
{
    if ([self isEmpty:queue]) {
        return nil;
    }
    Student *s = queue.data[queue.head];
    queue.head ++;
    return s;
}
//取队头
+(Student *)GetHead:(SeqQueue *)queue
{
    if ([self isEmpty:queue]) {
        return nil;
    }
    return queue.data[queue.head];
}
//取队长
+(NSInteger)GetLength:(SeqQueue *)queue
{
    return queue.foot-queue.head;
}

//判断是否队满
+(BOOL)isFull:(SeqQueue *)queue
{
    if (queue.foot>=queue.maxSize) {
        return YES;
    }
    return FALSE;
}
//判断是否队空
+(BOOL)isEmpty:(SeqQueue *)queue
{
    if (queue.foot == queue.head) {
        return YES;
    }
    return false;
}

mian.m:

int main(int argc, const char * argv[]) {
    @autoreleasepool {
   
        Student *stu = [[Student alloc]init];
        stu.name = @"小明";
        stu.age = 22;
        Student *stu1 = [[Student alloc]init];
        stu1.name = @"小丽";
        stu1.age = 25;
        Student *stu2 = [[Student alloc]init];
        stu2.name = @"小王";
        stu2.age = 34;
        Student *stu3 = [[Student alloc]init];
        stu3.name = @"小涨";
        stu3.age = 34;
         SeqQueue*que ;
        //初始化队列
        que = [SeqQueueHelper initSeqQueue:que];

        //入队列
        [SeqQueueHelper Enter:que elem:stu];
        [SeqQueueHelper Enter:que elem:stu1];
        [SeqQueueHelper Enter:que elem:stu2];
        //出队列
        [SeqQueueHelper Dequeue:que];
        //获取队列长度
        
        NSLog(@"队列的长度:%ld",[SeqQueueHelper GetLength:que]);
        //获取队头
        Student *sss = [SeqQueueHelper GetHead:que];
}
    return 0;
}