2.4 队列：先进先出的调度心法

2.4 队列：先进先出的调度心法

本节摘要：队列一头进、一头出，纪律是先进先出（FIFO），表达"先来先服务"的公平语义。朴素数组实现的出队要整体搬移 O(n)，环形队列用取模把首尾指针绕环走，把进出都压到 O(1)。本节实现环形队列并数清搬移账，顺带认识双端队列与优先队列两门近亲。

先来的先用，公平即语义

栈的世界里"最新的最优先"，队列恰好反过来：排队买票、任务调度、消息投递、缓冲区读写，全是"谁先到谁先走"。队列表达的不是效率，是秩序——公平性本身就是一类需求。

队列的招式极简：入队 enqueue 在队尾放，出队 dequeue 从队头取，看队头 peek 不动它，外加判空与大小。难点全在实现层面：用数组做队列，出队之后队头前移，前面的空间怎么复用？

朴素数组出队的搬移账

# 朴素实现：出队一次要搬多少次
def dequeue_naive(q):
    if not q:
        return None
    val = q[0]
    moves = 0
    for i in range(len(q) - 1):       # 后面所有元素整体前挪一格
        q[i] = q[i + 1]
        moves += 1
    q.pop()
    return val, moves

q = ["a", "b", "c", "d", "e"]
for _ in range(3):
    val, moves = dequeue_naive(q)
    print(f"出队 {val}：搬移 {moves} 次，剩余 {q}")
# 输出：
# 出队 a：搬移 4 次，剩余 ['b', 'c', 'd', 'e']
# 出队 b：搬移 3 次，剩余 ['c', 'd', 'e']
# 出队 c：搬移 2 次，剩余 ['d', 'e']
​

三次出队共搬移 4+3+2=9 次。队列越长、出队越频繁，这笔账越吓人：出队是 O(n)，队列基本废了。问题不在数组，在"队头固定在 0 号位"这个隐含假设——把它去掉，让队头游走，就是环形队列。

环形队列：取模让首尾绕环走

开一块定长数组，front 指向队头、rear 指向下一个可写入的位置，两个指针只前进不后退，走到末尾就用取模绕回 0。空间被当成一个环使用，出队只需 front 前移一格，进队只需写入 rear 处再前移一格——两次 O(1)。

# 环形队列：进出都是 O(1)，状态全程可跟踪
class CircularQueue:
    def __init__(self, k):
        self.buf = [None] * k      # 定长缓冲区
        self.front = 0             # 队头位置
        self.size = 0              # 当前元素个数

    def enqueue(self, x):
        if self.size == len(self.buf):
            return False           # 满：牺牲掉一个约定见下文
        rear = (self.front + self.size) % len(self.buf)  # 计算队尾写入位
        self.buf[rear] = x
        self.size += 1
        return True

    def dequeue(self):
        if self.size == 0:
            return None
        val = self.buf[self.front]
        self.buf[self.front] = None
        self.front = (self.front + 1) % len(self.buf)    # 队头绕环前进
        self.size -= 1
        return val

cq = CircularQueue(4)
for ch in "abcd":
    cq.enqueue(ch)
    print(f"入队 {ch}：缓冲 {cq.buf}，front={cq.front}，size={cq.size}")
# 输出：
# 入队 a：缓冲 ['a', None, None, None]，front=0，size=1
# 入队 b：缓冲 ['a', 'b', None, None]，front=0，size=2
# 入队 c：缓冲 ['a', 'b', 'c', None]，front=0，size=3
# 入队 d：缓冲 ['a', 'b', 'c', 'd']，front=0，size=4
print("再入队 e：", cq.enqueue(e := "e"))
# 输出：再入队 e： False（容量 4 已满）
print("出队：", cq.dequeue(), cq.dequeue())
cq.enqueue("e"); cq.enqueue("f")
print("绕环写入后缓冲：", cq.buf, "，front =", cq.front, "，size =", cq.size)
# 输出：绕环写入后缓冲： ['e', 'f', 'c', 'd']，front = 2，size = 4
# front=2，rear 绕回 0、1 号位写入 e、f——旧元素顺序未受打扰
​

注意最后一步：出队两次后 front 停在 2，新元素从 0 号位绕回来写。取模把"数组末尾"和"数组开头"焊接成环，这正是环形队列的心法：位置永远在 (起点加偏移) 对长度取模处。

⚠️ 常见坑：判满判空条件。若不维护 size，只用 front 与 rear 相等判空，则满时两者也相等——空满不分。两种正解：牺牲一个格子（满定义为 rear 的下一个等于 front），或像上面直接维护 size 计数。工程实现二选一，别混用。

工程现实：别用朴素列表当队列

Python 列表做队列的代价刚才数过了（出队搬移 O(n)）。标准库的 collections.deque 用双向链表块实现，两端进出都是 O(1)：

# deque：两端进出全部 O(1)
from collections import deque
d = deque()
for i in range(5):
    d.append(i)              # 右端入队
print("队列：", list(d))
# 输出：队列： [0, 1, 2, 3, 4]
print("左端出队：", d.popleft(), "；右端也能出：", d.pop())
# 输出：左端出队： 0 ；右端也能出： 4
print("剩余：", list(d))
# 输出：剩余： [1, 2, 3]
​

deque 同时开放两端，这其实是双端队列（deque）：需要"两端都能进出"的场景（滑动窗口求最值、工作窃取调度）用它。Java 的 ArrayDeque、C++ 的 deque 同理。另有一门近亲优先队列：出队顺序不看先来后到，看优先级——它不是线性表，而是堆的孩子，第三章 3.4 专讲。

队列撑起的世界

• 消息队列：分布式系统里削峰填谷的标准件，订单先入队、消费者按能力取，生产与消费解耦；
• 任务调度：操作系统就绪队列、线程池任务队列，公平轮转；
• 广度优先搜索：第四章 4.2 的主角，"按层扩展"的层序完全由队列的进出顺序刻画——先发现的先探索；
• 缓冲区：键盘缓冲、视频流缓冲，读写速度差的"蓄水池"。

识别信号与栈对照记忆：栈管"最近的先处理"，队列管"先来的先服务"；两者都不允许插队（随机访问），需要插队的是优先队列或哈希表的事。

💡 关键直觉：环形队列的精妙不在数据搬动，而在视角搬动——元素不动，指针绕环，把"腾空间"从搬移 O(n) 变成了前进 O(1)。

本节要点回顾

• 队列心法：一头进一头出、先进先出，表达公平调度的秩序语义；
• 朴素数组出队是 O(n)（搬移账 4+3+2 可复算），环形队列用取模把首尾绕环，进出全部 O(1)；
• 空满歧义是环形队列的经典坑：牺牲一格或维护 size 计数，二选一并贯彻；
• 工程选型：Python 用 collections.deque、Java 用 ArrayDeque，别拿动态数组硬扛队列；
• 双端队列两端开放、优先队列按优先级出队，是队列家族的两门变体，后者通往堆。

线性结构的最后一位主角最特殊：它不靠位置找元素，而是直接"算"出元素的住址——哈希表。