Olverae Assets

1 一句话定义

队列（queue）是一种「先进先出（FIFO）」的容器：从一端（队尾）放入（enqueue），从另一端（队首）取出（dequeue），先排进来的先被服务。

把它想成排队买票：新来的人到队尾排队，售票员永远从队首叫人，先来的先买到、不许插队。和栈（后进先出）正好相反。BFS 逐层遍历、打印任务排队、消息缓冲，背后都是队列。用数组实现时还会让队尾「转一圈回到开头」复用空位——这就是环形队列。

10 最先排进来，坐在队首、会最先被取走；40 刚到，排在队尾。下一节你将在一个 6 格的环形队列里 enqueue/dequeue，亲眼看队尾「转一圈回到开头」。

2 模型 · 环形队列：看队尾怎么"转圈回卷"

用一个 6 格数组当队列。enqueue 在队尾 tail 放、dequeue 从队首 head 取，两个下标都用 (i+1) % 容量 前进——走到末尾就绕回开头复用空格子。盯住 head / tail 和那个"转圈"。

环形队列：数组 + head + tail + count

关键是 % 容量 让下标到末尾后绕回开头；用 count 记元素个数，干净地区分空与满。

int items[CAP];
int head = 0, tail = 0, count = 0;

void enqueue(int v) {        // 在队尾放入
    items[tail] = v;
    tail = (tail + 1) % CAP;     //  到末尾就绕回开头
    count++;
}
int dequeue() {              // 从队首取出
    int v = items[head];
    head = (head + 1) % CAP;     //  同样绕回
    count--;
    return v;
}

为什么要 % CAP：数组是直的、队列是「流动」的，dequeue 后开头的格子空出来，让 tail 绕回去复用，才不会假装"满了"。空 vs 满都会让 head == tail，所以单看 head、tail 区分不了——用 count（或刻意留一个空格）来判断，是环形队列最容易写错的地方。

环形队列 · enqueue 10,20,30,40 → dequeue×2 → enqueue 50,60,70

代码（当前行高亮）

0

head 队首

0

tail 队尾

0

count 个数

—

刚出队的值

提示

点 ▶ 看 enqueue / dequeue。绿=队首 head，蓝=队尾 tail。注意 enqueue 50、60、70 时 tail 怎么绕回到开头复用空格子。

3 核心要点 · 4 句人话吃透队列

每张卡片先一句大白话。重点：FIFO、为什么要环形、空满怎么判、和栈的对照。

① 两端进出（FIFO）

一句话：队尾进、队首出，先进先出。和栈的"同一端进出"不同，队列两端各管一件事。

三个核心操作：enqueue（队尾入队）、dequeue（队首出队并返回）、front/peek（看队首不取）。都是 O(1)。

② 为什么要"环形"

一句话：dequeue 后开头空出来的格子，让 tail 绕回去复用，否则数组很快就"假装满了"。

如果只让 head/tail 一路向右、不回卷，dequeue 腾出的前面格子就浪费了，没多久 tail 撞到数组末尾就用不下去。用 (i+1) % CAP 让下标转圈，空间循环利用。

tail 到末尾: 5 →(+1)%6→ 0 // 绕回开头

③ 空 vs 满怎么区分

一句话：空和满时都满足 head == tail，光看这两个下标分不清——这是头号坑。

两种常见解法：(a) 用 count 记元素个数（count==0 空，count==CAP 满，最直观）；(b) 刻意留一个空格，规定 (tail+1)%CAP==head 为满。本页用的是 count 法。

④ 队列 vs 栈 + BFS

一句话：队列 FIFO 保持到达顺序，栈 LIFO 翻转顺序。BFS 逐层遍历用的就是队列。

把图遍历里的栈换成队列，深度优先(DFS)就变成广度优先(BFS)。词梯、骑士走棋、迷宫最短步数等"逐层扩散"全靠队列。

队列: 进 1,2,3 → 出 1,2,3 (原序) 栈: 进 1,2,3 → 出 3,2,1 (反序)

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是写队列最常翻车的坑——空满判定混淆、忘了取模回卷、空队列还出队、满队列还入队覆盖。点击卡片看运行效果。

① 空/满判定混淆

只用 head==tail 判空 → 满时也误判成空

② 忘了取模回卷

tail++ 不取模 → 越界，且不复用前面空格

③ 空队列还 dequeue

没判 count>0 → 取到垃圾、count 变负

④ 满队列还 enqueue

没判 count<CAP → 覆盖还没出队的数据

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题正对队列套路：FIFO 顺序、出队结果、环形回卷、空满判定、BFS 关系。最后到练习系统亲手模拟一个队列。

去做例题：队列 · 模拟出队序列

去做例题

Queues

队列