课程 · #4 / 11

队列

先进先出（FIFO）——每一次都是公平的顺序

Queue · FIFO

head

tail

init

token

动手试试：在传送带上入队/出队。切换到 ring buffer（环形缓冲），看看循环下标如何重复利用固定的内存——永远不需要搬移。

为什么它重要

队列为排队等候、任务调度和广度优先探索建模。只要到达顺序重要，你就需要一个队列。它们是操作系统、网络以及图算法的根基。

核心思想

想想咖啡店里的一条队伍。排在最前面的人最先被服务。新来的顾客从队尾加入。

先进先出（FIFO）。

如果说栈关乎撤销与回溯，那么队列关乎公平与顺序：

打印队列：文档按提交的先后顺序打印
任务调度器：进程按到达顺序运行（轮转）
BFS：逐层探索节点，先访问更早被发现的节点

入队（加到队尾）和出队（从队首移除）都是 O(1)。

要点回顾

入队与出队都是 O(1)
FIFO 顺序——先进先出
用于 BFS、任务调度、缓冲
环形缓冲是一种高效的、基于数组的实现

再深入一些

双端队列（deque）允许在两端插入/删除——这对滑动窗口算法，以及用单调双端队列在 O(n) 总时间内求"每个大小为 k 的窗口里的最大值"的技巧很有用。优先队列（在堆那一课讲到）是"不公平"的队列，其中重要性压倒了到达顺序——把本课的某个旋钮再拧动一格，你就得到了一个堆。环形缓冲通过回绕，在固定大小的数组里高效地实现队列。

实战中的队列

ROS 话题队列。 ROS（机器人操作系统）里每个发布者都向其话题所对应的、容量固定的环形缓冲队列写入。当订阅者跟不上时，最旧的消息会被丢弃。调好那个队列深度，是机器人工程师最先要学会的事情之一。
消息中间件（Kafka、RabbitMQ、NATS、Redis Streams）。 它们全都建立在队列抽象之上，再叠加持久化与复制。消费者从队首读取；生产者向队尾追加。
机器人地图上的 BFS 边界。 图那一课的网格模式直接展示了这一点——波前路径规划就是带队列的 BFS，而大多数占据栅格规划器（A*、JPS、theta*）正是这样初始化的。
打印假脱机、操作系统调度器的运行队列、Web 服务器的请求队列。 凡是以"先到先得"为策略的地方都有它。

为什么环形缓冲是 `O(1)` 摊还 —— 即便扩容是 `O(n)`

一个朴素的、基于数组的队列在从队首出队时，要把剩下的 n 个元素全部左移——O(n)。环形缓冲则用你在演示里看到的取模下标避开了这一点：front 和 rear 在容量上取模前进，不留下任何需要填补的空隙。

但当环装满了会怎样？你分配一个两倍大的新缓冲区并拷贝过去。这是 O(n)——和数组翻倍证明用的是同一个扩容技巧。在 n 次入队上，总工作量是 2n − 1，所以单次操作是 O(1) 摊还。如果不翻倍——比如每次只增加一个常数——总工作量就会膨胀到 O(n²)。

这是你第二次见到翻倍套路了；你还会在哈希表的再散列里再次见到它，并在堆的建堆里隐式地遇到它。认准这个形状："罕见的昂贵操作，由许多此前廉价的操作买单"——这就是一句话概括的摊还分析。

数学细节

时间复杂度: Enqueue: O(1); Dequeue: O(1); Peek front: O(1); Search: O(n)
环形缓冲: front = (front + 1) mod capacity; rear = (rear + 1) mod capacity

实现

用 VecDeque 实现队列

use std::collections::VecDeque;

let mut queue = VecDeque::new();

queue.push_back(1);  // Enqueue
queue.push_back(2);
queue.push_back(3);  // Queue: [1, 2, 3]

let front = queue.pop_front();  // Returns Some(1)
// Queue is now [2, 3]

经典应用

BFS 图遍历
任务/作业调度
打印假脱机
流数据的缓冲

练习

三道队列题目，每道都倚重 FIFO 纪律的不同侧面：

用两个栈实现队列 —— 中等 · 用两个 LIFO 加上惰性倒灌来伪装成 FIFO（摊还 O(1)）
滑动窗口最大值 —— 困难 · 单调双端队列套路，把 O(n log k) 降到 O(n)
有界环形缓冲（机器人） —— 中等 · 每个 ROS 话题和 UART 驱动都构建于其上的、容量固定的 FIFO

→ 浏览全部练习题

🎢 队列