队列

概述

队列（Queue） 是一种遵循**先进先出（First-In-First-Out, FIFO）**原则的动态集合。最先入队（enqueue）的元素最先出队（dequeue），类似于在超市收银台排队——先到者先接受服务。

定义

队列（Queue）

队列 $Q$ 是一个支持以下操作的动态集合，维护两个属性：

• $Q.head$：指向队首元素（下一个被移除的元素）。
• $Q.tail$：指向下一个新元素将被插入的位置。

操作定义：

• $\text{textsc}Enqueue(Q,x)$：$Q[Q.tail]\leftarrow x$；若 $Q.tail=Q.length+1$，则 $Q.tail\leftarrow 1$；否则 $Q.tail\leftarrow Q.tail+1$。
• $\text{textsc}Dequeue(Q)$：若队列为空则报错 underflow；$x\leftarrow Q[Q.head]$；若 $Q.head=Q.length$，则 $Q.head\leftarrow 1$；否则 $Q.head\leftarrow Q.head+1$；返回 $x$。

队列使用数组 $Q[\mathrm{1..}n]$ 实现，通过**循环数组（circular array）**技巧避免元素出队后数组前端的浪费空间。

核心性质

• FIFO 原则：元素的出队顺序与入队顺序严格一致。
• 操作复杂度：$\text{textsc}Enqueue$、$\text{textsc}Dequeue$ 均为 $O(1)$ 时间。
• 循环数组：通过取模运算（或条件判断）将 $head$ 和 $tail$ 在 $1$ 到 $n$ 之间循环，使数组空间被重复利用。
• 容量限制：当队列填满（$head=tail$ 且队列非空）时发生溢出。

循环数组工作原理

数组 Q[1..6]，初始 head=1, tail=1（空队列）

Enqueue(a):  [a, _, _, _, _, _]  head=1, tail=2
Enqueue(b):  [a, b, _, _, _, _]  head=1, tail=3
Enqueue(c):  [a, b, c, _, _, _]  head=1, tail=4
Dequeue()→a: [_, b, c, _, _, _]  head=2, tail=4
Enqueue(d):  [_, b, c, d, _, _]  head=2, tail=5
Enqueue(e):  [_, b, c, d, e, _]  head=2, tail=6
Enqueue(f):  [f, b, c, d, e, _]  head=2, tail=1  ← tail 回绕到数组头部

操作示例

操作	队列内容（head→tail）	head	tail
初始	—	1	1
Enqueue(4)	4	1	2
Enqueue(1)	4, 1	1	3
Dequeue() → 4	1	2	3
Enqueue(3)	1, 3	2	4

章节扩展

第10章：基于数组的实现

队列与栈同属第10章中”简单的基于数组的数据结构”。队列的关键设计难点在于：元素从头部移除后，如何高效利用释放的空间。CLRS 采用循环数组方案，通过让 $head$ 和 $tail$ 指针在数组边界回绕，实现 $O(1)$ 的入队和出队操作。

队列在算法中广泛用于：广度优先搜索（BFS）、任务调度、缓冲区管理等场景。

第20章：基本图算法

BFS使用FIFO队列实现层序遍历：发现白色顶点时将其着灰色并入队，处理时出队并探索邻接顶点。队列保证了同层顶点先于下层顶点被处理，这是BFS最短路径性质的基础。

第24章：最大流

Edmonds-Karp算法使用BFS在残差网络中寻找最短（边数最少）增广路径。BFS的FIFO队列保证了每次找到的增广路径是最短的，从而使算法在 O(VE²) 时间内终止。

参见

• 栈 — 同为线性受限结构，但遵循 LIFO 原则
• 链表 — 队列也可以用链表实现，入队在尾部、出队在头部
• 二叉堆 — 对比：优先队列同样具有”出队”语义，但按优先级而非到达顺序