队列：让先到的数据先被处理

很多程序面对的不是“哪个元素最大”，也不是“最近加入了什么”，而是一个更朴素的问题：谁先到，谁先处理。打印任务按提交顺序等待，消息按到达顺序消费，无权图搜索先处理离起点更近的一层。只要处理顺序由等待时长决定，队列就是最直接的模型。

队列把元素从一端加入，从另一端移除。加入的一端叫队尾，移除的一端叫队头。这个限制看似简单，真正实现时却有不少容易写错的地方：数组走到末尾后怎样复用前面的空位，head == tail 到底表示空还是满，最后一个链表节点出队后该更新哪些指针，BFS 为什么必须在入队时标记顶点。

本文从抽象接口开始，逐步实现环形数组队列和链式队列，再把队列放进广度优先搜索中观察它怎样维持分层顺序。最后我们会明确区分普通队列、双端队列和优先队列，避免只因名字里都有“队列”就混用接口。

先进先出到底约束了什么

假设元素按 甲、乙、丙 的顺序进入一个初始为空的队列，中间没有出队，那么离开顺序一定是 甲、乙、丙。这种规则叫先进先出，常写作 FIFO。

这里的“先进”只看加入当前队列的先后，不看元素的值、优先级或处理成本。即使 丙 的数值更小，或者处理它只需一毫秒，只要它排在 甲 和 乙 后面，普通队列就不会越过前面的元素先取 丙。

队列的基本接口

• enqueue(x)：把 x 加到队尾；
• dequeue()：移除并返回队头元素；
• front()：读取队头元素，但不移除；
• isEmpty()：判断队列是否为空；
• size()：返回当前元素个数。

固定容量实现通常还提供 isFull()。dequeue() 和 front() 的前置条件是队列非空；固定容量队列的 enqueue(x) 还要求队列未满。对空队列执行删除叫下溢，对已满的固定容量队列继续加入叫上溢。实现可以抛出异常、返回失败状态或阻塞等待，但不能悄悄把一次失败说成成功。

操作只改变两端，不改变相对顺序

考虑下面的操作序列：

enqueue(4), enqueue(1), enqueue(3), dequeue(),
enqueue(8), front(), dequeue()

若把左侧写成队头，状态变化如下：

每次成功入队只把新元素放到所有旧元素之后；每次成功出队只移除最前面的元素。因此，任意两个仍在队列中的元素，如果 x 比 y 先入队，那么 x 仍然排在 y 前面。这条相对顺序不变式就是 FIFO 的核心。

front() 是查询，不改变状态。这个细节在循环条件中很实用：程序可以先查看下一个任务，再决定是否真的取走它。

交互实验：追踪队头与队尾

下面的队列容量为 6。你可以连续入队、出队，观察队头元素、队尾元素和操作日志怎样变化。

小测

环形数组如何复用已经离开的槽位

如果我们用普通数组保存队列，并在每次出队后把所有剩余元素向左搬一格，出队一次就要移动许多元素，时间复杂度会退化为 $O(n)$。如果从不搬移，只让队头和队尾一直向右走，数组前面虽然已经空出来，队尾到达末端时却无法复用它们。

环形数组解决的是存储位置复用。我们把长度为 n 的数组看成首尾相接：下标 n - 1 的下一个位置是下标 0。实际内存仍是一段普通连续数组，“圆环”只体现在下标计算上。

明确两个指针的含义

这一节采用以下约定：

• head 指向下一次出队要读取的元素；
• tail 指向下一次入队要写入的空槽；
• 队列中的元素从 head 开始，沿下标递增方向走到 tail 之前；
• 下标到达 n - 1 后，下一步回到 0。

下一个位置统一写成：

初始化时 head = tail = 0。只要每次移动都使用取模，两个指针始终满足：

用一个空槽区分空和满

当 head == tail 时，从队头走到队尾之前没有任何元素，因此队列为空。问题是：如果允许 n 个槽全部装满，tail 绕一圈后也会再次等于 head，同一个状态就同时表示空和满。

最简洁的解决方法是始终保留一个空槽：

空：head == tail
满：next(tail) == head

于是长度为 n 的底层数组最多保存 n - 1 个队列元素。当前长度可以直接由两个指针算出：

这不是浪费算法逻辑，而是在用一个槽位换取无歧义的状态编码。容量参数必须说清楚：若业务要求最多保存 8 个元素，采用这种方案时应分配 9 个数组槽。

入队和出队的准确顺序

ENQUEUE(Q, x)
    若 next(Q.tail) == Q.head：报告上溢
    Q.data[Q.tail] = x
    Q.tail = next(Q.tail)
 
DEQUEUE(Q)
    若 Q.head == Q.tail：报告下溢
    x = Q.data[Q.head]
    Q.head = next(Q.head)
    返回 x

入队先检查满，再写 tail 指向的空槽，最后推进 tail。出队先检查空，再读取 head 指向的队头，最后推进 head。顺序写反会带来典型的差一错误：先推进 tail 再写会跳过当前空槽；先推进 head 再读会跳过真正的队头。

弹出后，原数组槽里的旧值可能还存在，但它已经位于逻辑区间之外，不再属于队列。保存对象引用的语言里可以主动清空该槽，便于回收内存；这不会改变 FIFO 语义。

绕回过程示例

底层数组长度为 6，可保存 5 个元素。初始 head = tail = 0，依次执行：

enqueue(甲), enqueue(乙), enqueue(丙), enqueue(丁),
dequeue(), dequeue(), enqueue(戊), enqueue(己), enqueue(庚)

最终逻辑顺序是 [丙, 丁, 戊, 己, 庚]，而物理槽位可能分散在数组末端和开头。head = 2，tail = 1；从下标 2 开始依次读取 2、3、4、5、0，正好得到五个元素。物理下标不连续，不影响逻辑顺序连续。

交互实验：让指针真正绕回去

这个实验展示每个物理槽位。数组长度固定为 7，因此最多存 6 个元素；连续操作后可以看到 head 和 tail 从末端回到 0。

小测

空满判定与边界正确性

保留一个空槽不是唯一方案。如果希望长度为 n 的数组保存完整的 n 个元素，可以增加一个 count 变量：

空：count == 0
满：count == n

此时 head 仍指向下一次出队位置，tail 仍指向下一次入队位置。两者相等时可能为空，也可能为满，真正的区别由 count 给出。每次成功入队令 count = count + 1，每次成功出队令 count = count - 1。

另一种方案保存一个“上一次操作是否为入队”的标志，或者让 tail 指向最后一个有效元素。它们也能工作，但不要从不同方案各抄一半。例如，用 count == n 判满，却忘记在出队时减少 count，队列会永久停在“已满”；让 tail 指向最后一个元素，却套用“先写 tail 再推进”的代码，也会覆盖旧数据。

用不变式检查每次修改

采用 count 方案时，合法状态至少满足：

若 count > 0，data[head] 是当前队头；若 count < n，data[tail] 是下一可写槽。逻辑顺序是从 head 出发连续走 count 步得到的元素序列。

一次成功入队的正确性可以分三步检查：

一次成功出队也类似：先验证 count > 0，读取 data[head]，再推进 head 并减少 count。被移除的是逻辑序列的第一个元素，剩余元素的相对顺序没有变化。

一个使用完整容量的 TypeScript 实现

class CircularQueue<T> {
  private readonly data: Array<T | undefined>;
  private head = 0;
  private tail = 0;
  private count = 0;
 
  constructor(private readonly capacity: number) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new RangeError("容量必须是正整数");
    }
    this.data = new Array<T | undefined>(capacity);
  }
 
  size(): number {
    return this.count;
  }
 
  isEmpty(): boolean {
    return this.count === 0;
  }
 
  isFull(): boolean {
    return this.count === this.capacity;
  }
 
  enqueue(value: T): void {
    if (this.isFull()) {
      throw new Error("队列上溢");
    }
    this.data[this.tail] = value;
    this.tail = (this.tail + 1) % this.capacity;
    this.count += 1;
  }
 
  dequeue(): T {
    if (this.isEmpty()) {
      throw new Error("队列下溢");
    }
    const value = this.data[this.head] as T;
    this.data[this.head] = undefined;
    this.head = (this.head + 1) % this.capacity;
    this.count -= 1;
    return value;
  }
 
  front(): T {
    if (this.isEmpty()) {
      throw new Error("空队列没有队头");
    }
    return this.data[this.head] as T;
  }
}

这份实现的 enqueue、dequeue、front、size、isEmpty 和 isFull 最坏时间都是 $O(1)$，底层空间是 $O(n)$。清空出队槽位是为了释放对象引用；判断队列成员仍然只看 head、tail 和 count。

动态扩容会改变哪项复杂度

固定容量队列在满时报告上溢。动态数组队列可以分配更大的数组，并按逻辑队列顺序把现有元素复制到新数组的 0..count-1，再设置 head = 0、tail = count。

一次扩容需要复制 count 个元素，因此该次入队是 $O(n)$。若容量每次按固定倍数增长，连续许多次入队的平均代价仍可做到摊还 $O(1)$；但不能因此声称每一次入队的最坏时间都是 $O(1)$。

最小但有效的边界测试

测试不能只覆盖“入队三个、出队三个”的直线路径。至少要检查：

小测

链式队列怎样维护两个端点

数组队列把元素放在连续槽位中，链式队列则让每个节点保存一个值和指向下一节点的链接。为了让入队和出队都在常数时间完成，我们同时保存：

• head：指向队头节点；
• tail：指向队尾节点。

若只保存 head，出队仍是 $O(1)$，但入队需要从头走到链尾，会变成 $O(n)$。若使用单链表却从尾部删除，寻找尾节点的前驱同样需要遍历。正确方向是：尾部加入，头部移除。

空队列和最后一个节点是关键边界

空链式队列应满足：

head == null 且 tail == null

向空队列加入第一个节点时，新节点既是队头也是队尾，所以两个指针都要指向它。普通入队时，先令旧尾节点的 next 指向新节点，再把 tail 更新为新节点。

从只有一个节点的队列出队后，head 会变为 null。此时还必须把 tail 也设为 null。如果遗漏这一步，tail 会继续指向已经不属于队列的旧节点，下一次入队可能把新节点接到错误位置。

type Link<T> = {
  value: T;
  next: Link<T> | null;
};
 
class LinkedQueue<T> {
  private head: Link<T> | null = null;
  private tail: Link<T> | null = null;
  private count = 0;
 
  enqueue(value: T): void {
    const node: Link<T> = { value, next: null };
 
    if (this.tail === null) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.count += 1;
  }
 
  dequeue(): T {
    if (this.head === null) {
      throw new Error("队列下溢");
    }
 
    const value = this.head.value;
    this.head = this.head.next;
    this.count -= 1;
 
    if (this.head === null) {
      this.tail = null;
    }
    return value;
  }
 
  front(): T {
    if (this.head === null) {
      throw new Error("空队列没有队头");
    }
    return this.head.value;
  }
 
  size(): number {
    return this.count;
  }
}

两种表示的取舍

“链式队列不会上溢”不是严格说法。它不受固定数组长度限制，但节点分配仍可能失败，系统也可能设置最大任务数。数据结构的表示和业务容量策略是两件事。

若已知容量上限且操作频繁，环形数组通常更紧凑；若元素数变化大又不想整体搬移，链式表示更自然。选择依据是容量、内存布局和错误策略，不是二者谁“永远更快”。

小测

广度优先搜索为什么需要普通队列

给定无权图和起点，广度优先搜索先访问距离起点为 0 的顶点，再访问距离为 1 的顶点，随后是距离为 2、3 的顶点。这里的距离是路径经过的边数。普通 FIFO 队列正好保存“已发现、但邻接边还没有全部检查”的顶点。

顶点状态与队列的对应关系

为了讲清搜索进度，可以把顶点分成三种状态：

• 白色：尚未发现；
• 灰色：已经发现并入队，但邻接表还未完全扫描；
• 黑色：邻接表已经扫描完毕。

队列在每次 while 条件检查时恰好包含全部灰色顶点。起点先被标成灰色并入队。循环每次从队头取出一个灰色顶点 u，检查它的所有邻居；第一次遇到白色邻居 v 时，记录距离和前驱，把 v 标成灰色并加入队尾。u 的邻居全部检查完后，u 变成黑色。

BFS(G, s)
    对每个顶点 u：
        u.discovered = false
        u.distance = 无穷
        u.parent = null
 
    s.discovered = true
    s.distance = 0
    Q = 空队列
    Q.enqueue(s)
 
    当 Q 非空：
        u = Q.dequeue()
        对 G.adj[u] 中每个 v：
            若 v.discovered == false：
                v.discovered = true
                v.distance = u.distance + 1
                v.parent = u
                Q.enqueue(v)

在只需要防止重复发现时，一个布尔值足以实现；灰色和黑色的区分主要帮助我们描述“仍在队列”和“已处理完”的差别。

为什么要在入队时标记

假设 甲 和 乙 都连接到尚未发现的 丙。处理 甲 时发现 丙，应立即标记并入队。之后处理 乙，看到 丙 已被标记，就不会重复入队。

如果等到出队时才标记，那么 甲 和 乙 都可能把 丙 加入队列。一个顶点会被处理多次，父节点还可能反复覆盖，复杂度与搜索树都失去保证。因此，“检查白色—立即标记—设置距离和父节点—入队”应当属于同一个发现动作。

FIFO 怎样维持距离层次

假设队头顶点距离为 $k$。它新发现的邻居距离是 $k + 1$，这些邻居被放到队尾。此前已经排在队列里的顶点不会被它们越过，因此距离为 $k$ 的其余顶点会先处理，随后才轮到距离为 $k + 1$ 的顶点。

搜索期间，队列里的距离值始终非递减，并且最多同时出现相邻的两层。例如队头距离为 2 时，队尾至多是 3，不会突然出现 4。由此可以得到两个直接结论：

• 所有距离为 $k$ 的可达顶点都会在距离为 $k + 1$ 的顶点之前出队；
• 一个顶点第一次被发现时得到的距离，就是起点到它的最少边数。

邻接表中邻居的排列顺序可能改变“同一层里谁先发现”，所以前驱树不一定唯一；但各顶点的最短距离不会因此改变。

复杂度来自两次总量统计

每个顶点只在第一次发现时入队，因此最多入队一次、出队一次。每次队列操作是 $O(1)$，所有队列操作合计 $O(V)$。

每个顶点出队时扫描一次自己的邻接表。邻接表总长度与边数同阶：有向图中每条边出现一次，无向图中每条边在两个端点的表中各出现一次，仍然是 $O(E)$。加上初始化，BFS 的总时间为：

保存顶点状态、距离、前驱和队列需要 $O(V)$ 额外空间。若图用邻接矩阵表示，每次出队都要检查整行的 $V$ 个位置，总时间会变为 $O(V^2)$。

用前驱恢复一条最短路径

第一次发现 v 时记录 parent[v] = u。搜索结束后，从目标沿前驱不断回到起点，再把结果反转，就得到一条最少边数路径。若目标仍未发现，就说明从该起点不可达。

function restorePath(
  start: string,
  target: string,
  parent: Map<string, string | null>
): string[] | null {
  if (!parent.has(target)) return null;
 
  const reversed: string[] = [];
  let current: string | null = target;
 
  while (current !== null) {
    reversed.push(current);
    if (current === start) return reversed.reverse();
    current = parent.get(current) ?? null;
  }
  return null;
}

这段恢复过程的时间与输出路径的顶点数成正比。BFS 处理的是无权图，或每条边权重都相同的图；边权不同且非负时，应使用按暂定距离选择顶点的算法，不能把普通 FIFO 队列直接当成优先队列。

交互实验：逐步观察搜索前沿

点击“下一步”会处理一个队头顶点。面板同时显示距离、前驱和队列，可以直接看到同层顶点先处理、下一层顶点后进入。

小测

名字相近的队列结构不能混为一谈

“队列”有时指普通 FIFO 抽象类型，有时出现在更专门的结构名称里。判断它们是否能替换，应该看下一次删除哪个元素，而不是只看容器长得像不像。

普通队列

普通队列只允许从队尾加入、从队头移除。删除目标由等待顺序决定，最早加入且尚未删除的元素先离开。环形数组和链表只是实现方式，不改变这个抽象语义。

双端队列

双端队列允许在两端加入和删除：

pushFront, pushBack, popFront, popBack

如果只使用 pushBack 和 popFront，它表现为普通队列；如果只使用 pushBack 和 popBack，它表现得像栈。双端队列的接口更宽，不代表程序可以随意从中间删除。

环形数组同样可以实现双端队列：在队头加入时让 head 向前绕回，在队尾删除时让 tail 向前回退。它仍需要明确空满编码。

优先队列

优先队列每次移除的是优先级最高或最低的元素，而不是等待最久的元素。两个任务先后加入后，后来的高优先级任务可以先离开。常见二叉堆实现中，插入和删除最高优先级元素通常是 $O(\log n)$，查看最高优先级元素是 $O(1)$。

因此，加权最短路算法需要按当前最小暂定距离选顶点时，使用的是最小优先队列；无权图 BFS 按发现先后处理，使用的是普通 FIFO 队列。把两者互换，处理次序和正确性依据都会改变。

环形缓冲区不是新的删除规则

“环形”描述的是下标和存储槽位怎样复用，“FIFO”描述的是元素以什么顺序离开。环形数组可以实现普通队列，也可以实现双端队列；普通队列也可以用链表实现。不要把表示方式当成抽象类型。

有些数据流系统在缓冲区满时会覆盖最旧数据。这种“覆盖式环形缓冲区”不是普通的固定容量队列行为，因为普通队列满时入队应失败、阻塞或扩容，不能未经约定自动删除队头。若业务确实需要覆盖，接口应明确报告丢弃策略。

并发队列还要约定等待语义

在生产者—消费者程序中，空队列上的 dequeue 可能阻塞，直到生产者加入元素；满队列上的 enqueue 也可能等待空位。这叫阻塞队列。它仍可保持 FIFO，但除了顺序，还必须处理线程安全、唤醒和关闭状态。

这些同步要求不改变基本不变式，却会改变接口行为。单线程环形数组中的“立即报告下溢”，不能直接当成并发队列的完整实现。

选型时先问三个问题

1. 下一次应该删除最早到达的元素，还是最高优先级元素？
2. 是否需要从两端操作，还是只需要尾入头出？
3. 容量满或队列空时，应该失败、扩容、覆盖，还是等待？

回答完这三个问题，才能确定抽象类型和错误策略。然后再在环形数组、链表、堆等表示之间选择。

小测