队列

队列是一种先进先出（FIFO）的线性结构。先进入队列的元素先被取出。

一、基本操作

操作	说明
InitQueue	初始化队列
EnQueue	入队
DeQueue	出队
GetFront	获取队头元素
QueueEmpty	判断是否为空
QueueLength	获取队列长度

二、顺序队列

顺序队列用数组存储元素，通过 front 和 rear 标记队头和队尾。

普通顺序队列容易出现“假溢出”：前面空间已经释放，但 rear 到达数组末尾后无法继续插入。

三、循环队列

循环队列把数组看成环形空间。

常见判断：

队空：front == rear
队满：(rear + 1) % capacity == front

为了区分队空和队满，通常会浪费一个数组位置。

四、链队列

链队列使用链表实现。

优点：

• 空间按需分配；
• 不容易出现固定容量问题。

缺点：

• 需要管理动态内存；
• 指针操作更容易出错。

五、应用场景

• 任务队列；
• 消息队列；
• 广度优先搜索；
• 生产者消费者；
• 打印任务；
• 请求排队。

六、练习

• 实现循环队列。
• 实现链队列。
• 使用队列实现 BFS。
• 使用队列模拟任务调度。