队列（Queue）
队列（Queue）
队列 是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。和 栈 一样，队列是一种操作受限制的线性表，但限制方式恰好相反。
队列最核心的性质是先进先出（FIFO，First In First Out）：最早放进去的元素，最先被取出来。可以把它想象成排队买票——先来的站在队头，先拿到票；后来的人只能排到队尾，不能插队。
队列的操作
队列的操作同样简单，核心也是两种：从队尾加入，从队头取出。
| 操作 | 含义 |
|---|---|
| Enqueue / Push | 入队，在队尾插入一个元素 |
| Dequeue / Pop | 出队，从队头取出并移除一个元素 |
| Front / Peek | 查看队头元素，但不移除 |
| isEmpty | 判断队列是否为空 |
| Size | 返回队列中元素个数 |
在理想实现下，入队和出队的时间复杂度都是 O(1)。对空队列执行 Dequeue 或 Peek 会导致下溢（Underflow）；若容量固定且队满仍入队，则会发生上溢（Overflow）。
队列的实现
用链表实现
用 链表 实现时，通常维护 head（队头）和 tail（队尾）两个指针：入队在 tail 后追加节点，出队删除 head 并前移。只要 tail 指针存在，两端操作都是 O(1)。
struct Node { int val; Node* next; };
class Queue {
Node* head = nullptr;
Node* tail = nullptr;
public:
void enqueue(int x) {
Node* n = new Node{x, nullptr};
if (tail) tail->next = n;
else head = n;
tail = n;
}
int dequeue() {
int v = head->val;
Node* old = head;
head = head->next;
if (!head) tail = nullptr;
delete old;
return v;
}
bool empty() { return head == nullptr; }
};
链表实现的优点是容量不受限、入队无需搬移元素；缺点是每个节点多一个指针，内存不连续。
用数组实现（循环队列）
用 数组 实现时，如果每次出队都把后面元素整体前移，复杂度会变成 O(n)。工程上更常用循环队列（Circular Queue）：把数组首尾相接，用 front 和 rear 两个下标分别指向队头、队尾下一个空位，入队出队只移动下标，不搬移数据。
front rear
v v
[ | | A | B | C | | | ]
^ ^
数组末尾绕回开头
当 rear 走到数组末尾时，下一个位置是下标 0，而不是整体搬移。判断队满、队空时，需要约定是“牺牲一个槽位”还是单独维护 size 计数——两种做法都很常见。
数组实现的优点是缓存友好、常数小；缺点是需要处理循环下标和容量边界，或者像栈一样在写满时扩容。
队列的应用
队列和栈一样看似简单，却无处不在：
- 广度优先遍历（BFS）：树 和 图 的层序遍历、最短路径的层次扩展，都依赖队列“先处理早进来的节点”这一特性。
- 任务调度：操作系统把等待 CPU 的进程放进就绪队列，按到达顺序或优先级依次调度；打印队列、消息队列也是同一思路。
- 缓冲区与流水线：生产者往队尾放数据，消费者从队头取数据，用队列解耦“产生速度”和“处理速度”的不匹配（如键盘输入缓冲、网络包缓冲）。
- 异步与事件处理：GUI 里用户点击、定时器到期等事件，常被放进事件队列，主线程按顺序逐个处理。
广度优先遍历时队列的变化
图 和 树 的广度优先遍历（BFS），本质就是一个不断入队、出队的过程。它的思路是“一层一层向外扩”：先把起点的邻居都访问完，再访问下一层。
以遍历一棵树为例，用队列实现的过程大致是：
- 把根节点入队。
- 从队头取出一个节点，访问它。
- 把它尚未访问的子节点按从左到右顺序入队。
- 重复第 2、3 步，直到队列为空。
因为先进入队列的节点会先被处理，所以访问顺序天然按层展开——这正是广度优先。
还是这棵树：
A
/ \
B C
/ \
D E
队列的变化过程如下：
| 步骤 | 动作 | 队列内容（队头在左） | 已访问 |
|---|---|---|---|
| 1 | 入队 A | [A] | |
| 2 | 出队 A，入队 B、C | [B, C] | A |
| 3 | 出队 B，入队 D、E | [C, D, E] | A B |
| 4 | 出队 C | [D, E] | A B C |
| 5 | 出队 D | [E] | A B C D |
| 6 | 出队 E | [] | A B C D E |
最终访问顺序是 A B C D E，正是层序遍历的结果。
对比 栈 里的深度优先示例（A B D E C），同一个数据结构、同一种遍历目标，仅仅因为用了栈还是队列，访问顺序就完全不同——栈负责“往深处钻”，队列负责“按层铺开”。
在无权图的最短路问题里，BFS 还有一个重要性质：第一次到达某个顶点时，所走步数一定是最少的。Dijkstra 在边权为 1 的特殊情况下，也可以看作带层次的 BFS 扩展。
双端队列与优先队列
在普通 FIFO 队列之上，还有两个常见变体：
| 结构 | 特点 | 典型用途 |
|---|---|---|
| 双端队列（Deque） | 队头、队尾都可以入队/出队 | 滑动窗口、单调队列优化 |
| 优先队列（Priority Queue） | 每次取出优先级最高（或最低）的元素，而非最早入队的 | 任务调度、Dijkstra 堆优化、事件模拟 |
优先队列的底层往往用堆实现，时间复杂度与纯 FIFO 队列不同（入队/出队通常为 O(log n)），但“按某种规则取下一个该处理的元素”这一抽象，在算法和系统里极其常用。图论中最短路一节提到的堆优化 Dijkstra，用的就是优先队列而非普通队列。
小结
队列用先进先出约束了元素的进出顺序：一端进、一端出，所有元素按到达顺序排队。掌握 enqueue / dequeue、循环数组与链表两种实现，以及 BFS 与任务调度等典型场景，就能理解大多数系统里“排队等待处理”的逻辑。与栈配对记忆效果最好：栈是 LIFO，队列是 FIFO；DFS 用栈，BFS 用队列。