队列及其应用
从食堂打饭的队形讲到操作系统的调度队列:搞懂 FIFO 的本质、循环队列的取模技巧、 链队列的指针细节,再用队列解决杨辉三角、层序遍历、迷宫最短路和滑动窗口最大值。
- 概念层:队列的定义、FIFO 特性、队头 front / 队尾 rear、ADT 的基本操作,以及队列与栈的对照。
- 存储层:顺序队列的「假溢出」是怎么来的 → 循环队列取模
(rear+1)%MaxSize的原理 → 三种判满方案的取舍。 - 实现层:完整可编译的循环队列与链队列(全局数组 /
struct结点 +head、tail+ 自由函数),含单元素出队的经典坑。 - 扩展层:双端队列 deque、受限双端队列,以及「栈和队列都是双端队列的特例」这一统一视角。
- 应用层:杨辉三角、二叉树层序遍历、迷宫最短路、单调队列滑动窗口、图的 BFS 与消息队列。
- 工具层:STL 的
std::queue/std::deque/std::priority_queue速查与常见坑。
4.1 队列的定义与抽象数据类型
先别急着看代码。想象一下中午十二点的食堂:所有同学很自觉地排成一列,新来的人站到队伍最后, 窗口师傅只从队伍最前面叫号。没有人会插队(我们希望如此),也没有人能从中间被叫走。 这个每天都在发生的场景,就是数据结构里最实用的结构之一 —— 队列 queue。
把食堂翻译成术语:队列是只允许在一端插入、在另一端删除的线性表 linear list。 允许插入的那一端叫队尾 rear(tail),允许删除的那一端叫队头 front(head)。 插入操作叫入队 enqueue,删除操作叫出队 dequeue。 由于先来的人先被服务,队列的存取次序是先进先出 First In First Out,FIFO。
4.1.1 FIFO:队列最核心的性质
FIFO 不是一句口号,它有三个可以拿来考试、也可以拿来写代码的等价推论:
- 出队序列 = 入队序列。若元素依次入队
a₁, a₂, …, aₙ,则出队顺序必定是a₁, a₂, …, aₙ,中途出队、入队交错也改变不了这个相对次序。 - 队头元素是「最早到达且尚未离开」的元素。这句话在模拟类题目里就是「谁先来谁先被服务」。
- 队列保证公平性(fairness)。操作系统用队列做进程调度、打印机用队列管理任务,图的就是这个「不饿死」的性质。
反过来问一句:为什么栈和队列都只能操作两端,却感觉队列更「温和」? 因为栈的插入和删除在同一端,后插入的元素压在先插入的元素上面,自然就「后来居上」; 而队列把插入和删除拆到两端,新元素排在队尾,永远不会插到老元素前面,于是顺序被完整保留下来。 这就像排队与叠盘子的区别 —— 排队讲秩序,叠盘子讲效率。
4.1.2 队列的抽象数据类型 ADT
抽象数据类型 abstract data type(ADT)只描述「能做什么」,不描述「怎么做到」。
队列的 ADT 很小,这也是它好用的原因。本讲的顺序队列、循环队列、链队列都按下表写成同名函数;出错时返回 false。
| 操作 | 语义 | 前置条件 | 时间复杂度 |
|---|---|---|---|
InitQueue() | 初始化:构造一个空队列 | — | O(1) |
QueueEmpty() | 判空:空返回 true。出队、取队头之前都要先判空 | — | O(1) |
QueueFull() | 判满:满返回 true | 只有用数组存的队列有;链队列不会满,不提供 | O(1) |
QueueLength() | 求长度:返回元素个数 | — | O(1) |
EnQueue(x) | 入队:把 x 放到队尾,成为新的队尾 | 队不满,否则返回 false | O(1) |
DeQueue(e) | 出队:删除队头元素并用 e 带回 | 队不空,否则返回 false | O(1) |
GetHead(e) | 取队头:用 e 带回,只读不删 | 队不空 | O(1) |
std::deque 的随机访问能力和队列的语义混为一谈了。
4.1.3 队列 vs 栈:一张图看清区别
下面这张对照图建议直接记进脑子:栈是「单口容器」,队列是「双口管道」。 栈的所有动作都发生在同一个口上,队列则在两端各开一个口。
| 对比维度 | 栈 stack | 队列 queue |
|---|---|---|
| 插入位置 | 栈顶 top | 队尾 rear |
| 删除位置 | 栈顶 top(与插入同端) | 队头 front(与插入异端) |
| 存取次序 | LIFO 后进先出 | FIFO 先进先出 |
| 典型比喻 | 叠盘子、弹夹、浏览器后退 | 排队打饭、打印机任务、收费站 |
| 元素个数为 n 时可能的出栈/出队序列数 | 卡特兰数 C(2n,n)/(n+1) | 只有 1 种(即入队序列本身) |
| 典型应用 | 括号匹配、表达式求值、递归、DFS、单调栈 | 层序遍历、BFS、缓冲池、调度、单调队列 |
| 基本操作复杂度 | 入栈 / 出栈均 O(1) | 入队 / 出队均 O(1) |
1 2 3 4,则出队序列有几种?」——答案是 1 种,就是 1 2 3 4。
对比「入栈序列为 1 2 3 4,可能的出栈序列有几种」答案是卡特兰数 14 种。
这个对比是判断题与选择题的高频陷阱,务必分清。
4.2 顺序队列与「假溢出」
队列的逻辑结构定下来了,接下来要决定它在内存里怎么排。最自然的想法是顺序存储:
开一块定长数组,用两个下标 front 与 rear 记录队头队尾位置。
但这里有一个非常经典的陷阱,学队列的人几乎都栽过跟头 —— 假溢出 false overflow。
4.2.1 顺序队列的结构与朴素写法
约定:数组 data[0..MaxSize-1],front 指向队头元素,
rear 指向队尾元素的下一个空位(也就是下一个新元素要落下去的位置)。
初始时两者都为 0,此时队列为空(front == rear)。
- 入队:
data[rear] = x; rear++; - 出队:
x = data[front]; front++; - 元素个数:
rear - front - 判空:
front == rear - 判满:
rear == MaxSize(朴素写法只能这么判)
看起来很干净,对吧?问题就出在最后两条上。
4.2.2 假溢出:明明有空位,为什么说队满?
关键在于 front 和 rear 都只会往后走,从来不回头。
出队让 front 右移,入队让 rear 右移,于是每出队一个元素,
队列前方就多出一个「永远用不到」的空位。等 rear 撞到 MaxSize 时,
程序判定「队满」,可数组前面那些空位其实还能装好几个元素。
下面这张分步图把它画得很直白。设 MaxSize = 8:
把这三步连起来看,问题的根子就清楚了:数组是「线性 + 有限」的,而 front / rear 是单调递增的。
每次出队都在数组头部制造一块「死区」,死区只会变大不会变小,最终把整个数组的前半段全部浪费掉。
此时队列真实占用 = rear - front = 6,而容量是 8,明明还能塞 2 个,却只能报「队满」。
- 真溢出 true overflow:
rear - front == MaxSize,整个数组真的塞满了,任何方案都救不了,只能扩容或拒绝服务。 - 假溢出 false overflow:
rear == MaxSize但front > 0,数组前面还有空位。这是结构设计缺陷,不是容量不足。 - 很多同学看到「队满」就去扩容数组 —— 那是治标不治本,而且会把 O(1) 的入队变成偶尔 O(n)。正确解法是让下标绕回来,即循环队列。
下面这个动画把假溢出的全过程演示一遍。留意 front 是怎么一步步把前面的空位「吃掉」的。
看完动画你应该能自己总结出结论:只要让 rear 在撞到 MaxSize 之后能回到下标 0,
假溢出就自然消失了 —— 这正是下一节循环队列要干的事。
4.2.3 朴素顺序队列的完整 C++ 实现
为了让你亲眼看到假溢出,下面这份代码故意用朴素写法实现,并在 main 里构造出「队满但有空位」的场景。
拷贝下来跑一遍,观察输出里 size=6、数组明明有 8 格,却打印 EnQueue 9 失败(队满) 的那一行。
// seq_queue_naive.cpp —— 朴素顺序队列:用来复现"假溢出"
// 竞赛写法:全局数组 + 自由函数,没有 struct 这层壳。
#include <bits/stdc++.h>
using namespace std;
const int MaxSize = 8;
int q[MaxSize]; // 存放队列元素的数组:q[0 .. MaxSize-1]
int front = 0; // 队头元素下标
int rear = 0; // 队尾元素的下一个空位
void InitQueue() { front = rear = 0; }
bool QueueEmpty() { return front == rear; }
int QueueLength() { return rear - front; }
// 朴素判满:只看 rear 有没有撞到数组末尾(这就是假溢出的源头)
bool QueueFull() { return rear == MaxSize; }
bool EnQueue(int x) {
if (QueueFull()) return false;
q[rear++] = x;
return true;
}
bool DeQueue(int &x) {
if (QueueEmpty()) return false;
x = q[front++];
return true;
}
bool GetHead(int &x) {
if (QueueEmpty()) return false;
x = q[front];
return true;
}
int main() {
InitQueue();
cout << "--- 1) 入队 1 2 3 4 ---\n";
for (int i = 0; i < 4; ++i) {
EnQueue(i + 1);
cout << "EnQueue " << i + 1 << " front=" << front
<< " rear=" << rear << " size=" << QueueLength() << "\n";
}
cout << "--- 2) 出队两个 ---\n";
int x = 0;
for (int i = 0; i < 2; ++i) {
DeQueue(x);
cout << "DeQueue " << x << " front=" << front
<< " rear=" << rear << " size=" << QueueLength() << "\n";
}
cout << "--- 3) 再入队 5 个,看谁失败 ---\n";
for (int i = 5; i <= 9; ++i) {
bool ok = EnQueue(i);
cout << "EnQueue " << i << (ok ? " 成功" : " 失败(队满)")
<< " front=" << front << " rear=" << rear
<< " size=" << QueueLength() << "\n";
}
cout << "--- 结论 ---\n";
cout << "size=" << QueueLength() << " 但 rear==MaxSize 判满,"
<< "前面 " << front << " 个位置白白浪费 —— 这就是假溢出\n";
return 0;
}
QueueFull() 改成 return rear - front == MaxSize; 会怎样?
假设此时 front=2, rear=8,改完后判满会返回 false,
于是 q[8] = x 直接越界写内存(数组下标只到 7)。
所以「只改判满条件」不仅没解决问题,还引入了更危险的越界 —— 必须连下标一起改成循环,这就是下一节的内容。
4.3 循环队列:把数组「掰弯」
假溢出的根源是「下标只增不减」。那么解法就呼之欲出了:给下标加一个上限,越界就回到 0。 物理上数组还是一维的,但逻辑上我们把它的首尾接了起来,构成一个环 —— 这就是循环队列 circular queue, 也叫环形队列 ring buffer。
front 和 rear 可以无限前进,空间利用率做到 100%(方案一略低一点)。
4.3.1 取模运算 (rear + 1) % MaxSize 的原理
取模(模运算 modulo)的含义是「除法的余数」。当 MaxSize = 8 时:
| 当前 rear | 朴素写法 rear+1 | 循环写法 (rear+1)%8 | 说明 |
|---|---|---|---|
| 0 | 1 | 1 | 正常后移 |
| 3 | 4 | 4 | 正常后移 |
| 6 | 7 | 7 | 正常后移 |
| 7 | 8(越界!) | 0(绕回队首) | 关键的一步 |
| 9 | 10 | 1 | 无论走多远都能映射回 0..7 |
为什么 % MaxSize 恰好能实现「绕回」?因为余数的取值范围天然就是 [0, MaxSize-1],
正好是合法下标的集合;而只要没超过 MaxSize,余数就等于原数,不影响正常情形。
一行代码同时兼顾了「前进」和「绕回」两件事,这就是取模的优雅之处。
下图把 MaxSize = 8 的循环队列画成一个环:外圈数字是数组下标,环内是元素值。
注意「队尾」永远在 rear 的逆时针前一格,因为 rear 指向的是下一个空位(下一个要写入的位置)。
front=0, rear=3,元素为 11、22、33,共 3 个4.3.2 三种判满方案及其优缺点
循环队列带来一个新麻烦:队空和队满的判定条件撞车了。
初始时 front == rear == 0 表示空;可当队列绕了一圈塞满时,
rear 又会追上 front,还是 front == rear。
同一个条件既表示空又表示满,程序无法区分 —— 这是循环队列唯一需要动脑筋的地方。
教材与工程上一共有三种主流解法,考试里三种都会考,请务必都掌握。
方案一:牺牲一个存储单元(最常用)
约定「rear 再走一步就撞上 front」时算作队满,
于是数组里永远至少留一个空位。判空仍是 front == rear,
判满变成 (rear + 1) % MaxSize == front。
代价是容量为 MaxSize 的数组最多存 MaxSize - 1 个元素;
好处是不额外花一个变量、不需要额外的分支,代码最短,也是 408 考研与大多数教材的默认方案。
// circular_queue_scheme1.cpp —— 方案一:牺牲一个存储单元判满
//
// 【循环队列三种判满方案的区别(考点,必须分清)】
// 方案一 牺牲一个单元(本文件):full = (rear+1)%M == front,empty = front == rear
// M 个格子最多存 M-1 个;不额外开变量,条件最短,是 408 默认方案。
// 方案二 size 计数器:full = sz == M,empty = sz == 0
// 零浪费,sz 还能直接当长度返回;代价是每次出入队都要同步维护 sz。
// 方案三 tag 标志位:full = front == rear && tag == 1,empty = front == rear && tag == 0
// 零浪费,但只在 front == rear 时有意义,判断条件最长、最容易写错。
// 区别的根源:front == rear 同时可能是"空"也可能是"满",
// 三种方案就是给这个歧义补上不同的信息(留一格 / 记个数 / 记上一次动作)。
#include <bits/stdc++.h>
using namespace std;
const int MaxSize = 8; // 数组容量;方案一牺牲一格,实际最多存 MaxSize-1 = 7 个元素
int q[MaxSize];
int front = 0; // front 指向队头元素
int rear = 0; // rear 指向队尾元素的下一个位置
void InitQueue() { front = rear = 0; }
bool QueueEmpty() { return front == rear; }
// 核心:rear 的下一个位置就是 front ⇒ 再存一个就会与队头重合 ⇒ 判满
bool QueueFull() { return (rear + 1) % MaxSize == front; }
int QueueLength() { return (rear - front + MaxSize) % MaxSize; }
bool EnQueue(int x) {
if (QueueFull()) return false;
q[rear] = x;
rear = (rear + 1) % MaxSize; // 前进一格,越界则回到 0
return true;
}
bool DeQueue(int &x) {
if (QueueEmpty()) return false;
x = q[front];
front = (front + 1) % MaxSize; // 同样要取模
return true;
}
bool GetHead(int &x) {
if (QueueEmpty()) return false;
x = q[front];
return true;
}
int main() {
InitQueue();
cout << "最多可存元素个数 = " << MaxSize - 1 << "\n";
for (int i = 1; i <= 8; ++i) { // 故意多入队一个,触发判满
bool ok = EnQueue(i * 10);
cout << "EnQueue " << i * 10 << (ok ? " 成功" : " 失败(队满)")
<< " front=" << front << " rear=" << rear
<< " size=" << QueueLength() << "\n";
}
int x;
DeQueue(x); cout << "DeQueue -> " << x << " size=" << QueueLength() << "\n";
EnQueue(99); cout << "EnQueue 99 后 size=" << QueueLength()
<< " front=" << front << " rear=" << rear << "\n";
while (DeQueue(x)) cout << x << " ";
cout << "\n队列已清空, empty=" << (QueueEmpty() ? "true" : "false") << "\n";
return 0;
}
方案二:增设 size 计数器
额外维护一个整数 size 记录当前元素个数。入队成功 ++size,出队成功 --size。
于是判空是 size == 0,判满是 size == MaxSize,两种情况再也不会混淆,
而且数组一个位置都不浪费,size 本身还可以直接当作 QueueLength() 返回,
不用再算公式。
// circular_queue_scheme2.cpp —— 方案二:size 计数器,容量不浪费
//
// 【与方案一、方案三的区别】三者的 EnQueue / DeQueue 主体完全一样,只差"判空判满靠什么":
// 方案一:靠"留一格",full = (rear+1)%M == front —— 浪费 1 格,不额外开变量
// 方案二:靠 sz 计数(本文件),full = sz == M —— 零浪费,sz 还能当长度用,
// 代价是每次出入队都必须同步维护它:入队 ++sz、出队 --sz,漏一句就全错
// 方案三:靠 tag 标志位,full = front == rear && tag == 1 —— 零浪费,条件最长
// 共同点:循环队列的下标一律取模 front = (front+1)%M、rear = (rear+1)%M,
// 这一步和判满方案无关,三种方案都必须写。
#include <bits/stdc++.h>
using namespace std;
const int MaxSize = 8; // 方案二不牺牲单元,最多可存满 8 个元素
int q[MaxSize];
int front = 0;
int rear = 0;
int sz = 0; // 当前元素个数,判空判满全靠它
void InitQueue() { front = rear = sz = 0; }
bool QueueEmpty() { return sz == 0; }
bool QueueFull() { return sz == MaxSize; }
int QueueLength() { return sz; } // 直接返回,无需公式
bool EnQueue(int x) {
if (QueueFull()) return false;
q[rear] = x;
rear = (rear + 1) % MaxSize;
++sz; // 与 rear 同步维护
return true;
}
bool DeQueue(int &x) {
if (QueueEmpty()) return false;
x = q[front];
front = (front + 1) % MaxSize;
--sz; // 千万别漏掉这一句
return true;
}
bool GetHead(int &x) { // 取队头:只读不删
if (QueueEmpty()) return false;
x = q[front];
return true;
}
int main() {
InitQueue();
for (int i = 1; i <= MaxSize; ++i) EnQueue(i); // 存满 8 个
cout << "存满后 size=" << QueueLength()
<< " full=" << (QueueFull() ? "true" : "false") << "\n";
cout << "再入队 999 结果=" << (EnQueue(999) ? "成功" : "失败") << "\n";
int x;
DeQueue(x); DeQueue(x);
GetHead(x);
cout << "两次出队后队头 = " << x << "\n";
EnQueue(100); EnQueue(200);
cout << "两次出队两次入队后 size=" << QueueLength()
<< " front=" << front << " rear=" << rear << "\n";
cout << "依次出队: ";
while (DeQueue(x)) cout << x << " ";
cout << "\n";
return 0;
}
方案三:设置 tag 标志位
只在「front == rear」这一瞬间才需要区分空与满,而这两种情况的成因不同:
空是「刚出队造成的」,满是「刚入队造成的」。于是加一个 tag:
最近一次操作是入队则 tag = 1,是出队则 tag = 0。
那么 front == rear && tag == 0 就是空,front == rear && tag == 1 就是满。
它同样不浪费存储单元,代价是每次操作多一次赋值,并且判空判满的判断条件变长了一点。
// circular_queue_scheme3.cpp —— 方案三:tag 标志位区分空与满
//
// 【与方案一、方案二的区别】三者的下标都要取模,差别只在"front == rear 时怎么判断":
// 方案一 牺牲单元:让 front == rear 只表示空,满由 (rear+1)%M == front 提前一步拦住
// 方案二 size 计数:干脆不用 front == rear 判断,直接看 sz == 0 / sz == M
// 方案三 tag(本文件):保留 front == rear 表示"重合",再补一位信息说明是怎么重合的 ——
// tag == 1(最近一次是入队)→ 满;tag == 0(最近一次是出队)→ 空。
// 零浪费,但判断条件最长,且 **只有 front == rear 时 tag 才有意义**,
// 所以 EnQueue / DeQueue 里每次都要记得更新 tag,漏一次判断就全乱。
// 记忆口诀:front == rear 是"空还是满",取决于它俩是"刚分开"还是"刚撞上"。
#include <bits/stdc++.h>
using namespace std;
const int MaxSize = 8;
int q[MaxSize];
int front = 0;
int rear = 0;
int tag = 0; // tag==0: 最近一次是出队(若 front==rear 则为空)
// tag==1: 最近一次是入队(若 front==rear 则为满)
void InitQueue() { front = rear = 0; tag = 0; }
bool QueueEmpty() { return front == rear && tag == 0; }
bool QueueFull() { return front == rear && tag == 1; }
int QueueLength() {
if (front == rear) return tag == 1 ? MaxSize : 0; // 重合时靠 tag 判断
return (rear - front + MaxSize) % MaxSize;
}
bool EnQueue(int x) {
if (QueueFull()) return false;
q[rear] = x;
rear = (rear + 1) % MaxSize;
tag = 1; // 记录"刚刚入队"
return true;
}
bool DeQueue(int &x) {
if (QueueEmpty()) return false;
x = q[front];
front = (front + 1) % MaxSize;
tag = 0; // 记录"刚刚出队"
return true;
}
bool GetHead(int &x) { // 取队头:只读不删
if (QueueEmpty()) return false;
x = q[front];
return true;
}
int main() {
InitQueue();
for (int i = 1; i <= MaxSize; ++i) EnQueue(i);
cout << "存满后 full=" << (QueueFull() ? "true" : "false")
<< " length=" << QueueLength() << "\n";
int x;
for (int i = 0; i < 3; ++i) DeQueue(x);
GetHead(x);
cout << "出队 3 个后队头 = " << x << "\n";
cout << "出队 3 个后 empty=" << (QueueEmpty() ? "true" : "false")
<< " length=" << QueueLength() << "\n";
EnQueue(777);
cout << "再入队一个 length=" << QueueLength() << " front=" << front
<< " rear=" << rear << " tag=" << tag << "\n";
while (DeQueue(x)) cout << x << " ";
cout << "\n清空后 empty=" << (QueueEmpty() ? "true" : "false")
<< " length=" << QueueLength() << "\n";
return 0;
}
| 对比项 | 方案一 牺牲单元 | 方案二 size 计数器 | 方案三 tag 标志位 |
|---|---|---|---|
| 判空条件 | front == rear | size == 0 | front==rear && tag==0 |
| 判满条件 | (rear+1)%M == front | size == MaxSize | front==rear && tag==1 |
| 最大元素数 | MaxSize − 1(浪费 1 格) | MaxSize(零浪费) | MaxSize(零浪费) |
| 额外空间 | 0 | 1 个 int | 1 个 int(可压成 1 bit) |
| 求长度 | 要算 (rear-front+M)%M | 直接返回 size | 重合时要靠 tag 特判 |
| 每次操作成本 | 1 次取模 | 1 次取模 + 1 次自增 | 1 次取模 + 1 次赋值 |
| 实现难度 | 最简单 | 简单,但容易漏维护 size | 判断条件最绕,易写错 |
| 典型出处 | 考研 408、严蔚敏教材默认写法 | 绝大多数工业级 ring buffer | 教材补充、面试手写题 |
| 适用场景 | 元素大小敏感度低、追求代码短 | 需要频繁查长度、容量不能浪费 | 要求「空间零浪费且不加计数器」的场合 |
MaxSize 的数组最多存 MaxSize-1 个元素。
常见问法:「数组 A[0..n-1] 实现循环队列,最多能存放多少个元素?」——答 n-1。
若题目明确给了 size 或 tag,再按对应方案答 n。
4.3.3 元素个数公式的推导
公式 (rear - front + MaxSize) % MaxSize 看着像背下来的,其实推两行就明白。
设 MaxSize = M,只可能出现两种情况:
情况 A:rear >= front(还没绕过圈)
元素分布在 front 到 rear-1 的连续区间里,个数就是 rear - front。
例:front=2, rear=6 → 元素在 data[2..5],共 4 个,而 6-2=4 ✓
情况 B:rear < front(已经绕过圈)
元素分成两段:front 到 M-1 一段,0 到 rear-1 一段。
个数 = (M - front) + rear = rear - front + M。
例:M=8, front=6, rear=2 → 第一段 data[6],data[7] 共 2 个,第二段 data[0],data[1] 共 2 个,
合计 4 个,而 2-6+8=4 ✓
合并:情况 A 里 rear - front + M 落在 [M, 2M-1],
对 M 取余正好剩下 rear - front;情况 B 里 rear - front + M 落在 [1, M-1],取余后不变。
于是两种情况可以统一写成:
也可以写成等价形式 (rear - front) % MaxSize 之后再 + MaxSize 再 % MaxSize,
但没人这么写 —— 先加 MaxSize 保证非负是最省事、最不容易出错的写法。
% 是截断取余(C++11 起规定商向零取整),负数取余会得到负数:
(2 - 6) % 8 == -4,而不是 4。
于是 -4 会被当成元素个数,后续循环全部乱套。
正确写法是 (rear - front + MaxSize) % MaxSize —— 先加后模,保证被除数非负。
顺便说一句:方案一下 front == rear 时公式给出 0(空),这是正确的;
因为「满」的状态永远不会让 front == rear(此时 (rear+1)%M == front)。
4.3.4 循环队列的完整实现(竞赛写法)
把方案一写成竞赛写法:一个全局数组 int q[M],两个全局下标 head / tail,
再加 4.1.2 表里的 InitQueue()、QueueEmpty()、QueueFull()、QueueLength()、EnQueue()、DeQueue()、GetHead() 这些自由函数 ——
不写 class、不写模板,所有结论一眼可见,抄到考卷上也最快。
三种判满方案各自的判空判满条件,一并写进了代码开头的注释里。
// circular_queue.cpp —— 循环队列的竞赛写法:全局数组 + 自由函数(方案一判满)
//
// 【三种判满方案,考试三种都考,结论先摆在这里】
// 方案一(本文件采用):牺牲一个存储单元
// 满 : (tail + 1) % M == head 空 : head == tail
// 容量为 M 的数组最多存 M-1 个元素;不额外开变量、判断最短,408 考研的默认方案。
// 方案二:另外维护一个计数器 cnt
// 满 : cnt == M 空 : cnt == 0
// 一个格子都不浪费,cnt 还能直接当成"元素个数"返回;代价是每次出入队都要同步维护它。
// 方案三:另外维护一个标志位 tag(最近一次操作:入队 1 / 出队 0)
// 满 : head == tail && tag == 1 空 : head == tail && tag == 0
// 同样零浪费,但判空判满的条件最长,最容易写错。
// 三种方案共用的两条结论(本文件的 EnQueue / DeQueue 就是照这个写的):
// * 入队 tail = (tail + 1) % M,出队 head = (head + 1) % M —— 下标必须取模才能"绕回来";
// 不取模就是 4.2 节那个会假溢出的朴素顺序队列。
// * 元素个数 = (tail - head + M) % M —— 先加 M 再取模,保证被除数非负
// (C++ 的 % 是截断取余,(2-6)%8 会得到 -4 而不是 4)。
//
// 【命名对照】竞赛里习惯写 head / tail,教材里写 front / rear,它们是同一对下标:
// head = front(指向队头元素),tail = rear(指向队尾元素的下一个空位)。
#include <bits/stdc++.h>
using namespace std;
const int M = 6; // 数组容量:方案一牺牲一格,实际最多存 M-1 = 5 个元素
int q[M]; // q[0..M-1] 就是那个被"掰弯"的数组
int head = 0; // head 指向队头元素
int tail = 0; // tail 指向队尾元素的下一个空位(下一个新元素要落下的位置)
void InitQueue() { head = tail = 0; }
bool QueueEmpty() { return head == tail; } // 判空:初始 head == tail == 0
bool QueueFull() { return (tail + 1) % M == head; } // ★ 判满:tail 再走一步就撞上 head
int QueueLength() { return (tail - head + M) % M; } // ★ 元素个数:先加 M 再取模
int Capacity() { return M - 1; } // 方案一下的真实可用容量
bool EnQueue(int x) { // 入队 O(1):一次赋值 + 一次取模
if (QueueFull()) return false;
q[tail] = x;
tail = (tail + 1) % M; // 前进一格,走到 M 就绕回 0
return true;
}
bool DeQueue(int &e) { // 出队 O(1):只动 head,一个元素都不搬移
if (QueueEmpty()) return false;
e = q[head];
head = (head + 1) % M; // 一样要取模
return true;
}
bool GetHead(int &e) { // 取队头:只读不删
if (QueueEmpty()) return false;
e = q[head];
return true;
}
bool GetRear(int &e) { // 取队尾:tail 的前一格,也要 +M 防负数
if (QueueEmpty()) return false;
e = q[(tail - 1 + M) % M];
return true;
}
void PrintQueue(const char *tag) {
printf("%s [size=%d/%d head=%d tail=%d] ", tag, QueueLength(), Capacity(), head, tail);
if (QueueEmpty()) { printf("(空)\n"); return; }
// ★ 遍历循环队列不能写 for (i = head; i < tail; ++i):绕过圈时 tail < head,一次都不执行。
// 正确姿势是"先算个数,再走环":
for (int i = 0, k = head; i < QueueLength(); ++i, k = (k + 1) % M)
printf("%d%s", q[k], i + 1 == QueueLength() ? "" : " -> ");
printf("\n");
}
int main() {
InitQueue();
PrintQueue("初始");
for (int i = 1; i <= 5; ++i) EnQueue(i * i);
PrintQueue("入队 1,4,9,16,25");
printf("再入队 36 结果: %s\n", EnQueue(36) ? "成功" : "失败(队满)");
int e = 0;
DeQueue(e); printf("出队 -> %d\n", e);
DeQueue(e); printf("出队 -> %d\n", e);
PrintQueue("出队两次");
EnQueue(36); EnQueue(49); // tail 从 5 绕回 0,亲眼看一下取模
PrintQueue("再入队 36,49");
int h = 0, r = 0;
GetHead(h); GetRear(r);
printf("队头 = %d,队尾 = %d\n", h, r);
printf("全部出队: ");
while (DeQueue(e)) printf("%d ", e);
printf("\n清空后 QueueEmpty=%s\n", QueueEmpty() ? "true" : "false");
for (int i = 1; i <= 3; ++i) EnQueue(i * 100); // 绕圈之后再入队,验证下标依然正确
PrintQueue("再入队 100,200,300");
return 0;
}
下面这个动画把循环队列的入队、出队、判满、判空连起来演示。
请重点观察 rear 从下标 7 绕回 0 的那一步,以及此时长度公式发生了什么变化。
4.3.5 循环队列的复杂度
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| EnQueue 入队 | O(1) | O(1) | 一次赋值 + 一次取模 |
| DeQueue 出队 | O(1) | O(1) | 只移动 front,不搬移元素 |
| GetHead 取队头 | O(1) | O(1) | 直接读 data[front] |
| QueueEmpty / QueueFull | O(1) | O(1) | 一次比较或取模 |
| Length 求长度 | O(1) | O(1) | 方案二更是直接返回 size |
| 遍历 | O(n) | O(1) | 必须按 (i+1)%cap 走,不能简单 i++ |
| 整表 | — | O(MaxSize) 预分配 | 数组容量固定,是典型的静态结构 |
for(i=front; i<rear; i++)
当 rear < front(绕过圈)时,这个循环一次都不执行,队列里的元素一个也访问不到。
正确写法是「先算个数,再走环」:
for (int i = 0, k = front; i < QueueLength(); ++i, k = (k + 1) % MaxSize)。
这一点在考试写代码题里扣分极狠,务必形成肌肉记忆。
4.4 链队列:用链表实现队列
循环队列虽好,但它是静态的:容量一经确定就不能改,存满了只能拒绝服务。 如果元素个数事先无法估计,或者波动很大,就该请出链表 —— 这就是链队列 linked queue。 链队列天生没有「队满」这个概念(除非内存耗尽),长度可以任意增长。
4.4.1 带头结点的链队列:为什么出入队都是 O(1)
链队列需要两个指针:front 指向队头结点,rear 指向队尾结点。
但直接让 front 指向第一个数据结点会带来一个麻烦:
出队时如果是最后一个元素,rear 会变成野指针,必须特判(这正是本节要重点讲的坑)。
更常见的做法是附加一个头结点 head node(也叫哑结点 dummy node),
它不存放有效数据,只用来统一边界情况。
于是约定变成:
front始终指向头结点,真正的队头元素是front->next;rear始终指向队尾结点(它就是最后一个数据结点);- 空队列的判定是
front == rear(此时两者都指向头结点,头结点的next为NULL); - 队列中元素个数 = 从
front->next走到rear的结点数,也可以额外维护一个size。
为什么说「出入队都是 O(1)」?逐条看指针动作:
| 操作 | 指针动作(带头结点) | 是否遍历 | 复杂度 |
|---|---|---|---|
| 入队 EnQueue(x) | rear->next = s; rear = s;(s 是新结点) |
否,rear 已知 | O(1) |
| 出队 DeQueue(x) | p = front->next; x = p->data; front->next = p->next; if (rear == p) rear = front; delete p; |
否,front->next 已知 | O(1) |
| 取队头 GetHead | x = front->next->data; | 否 | O(1) |
| 判空 QueueEmpty | front == rear(或 front->next == NULL) | 否 | O(1) |
| 求长度 Length | 从头结点走一遍到 rear | 是 | O(n),可加 size 优化到 O(1) |
对比一下不带头结点的版本,你立刻能看出头结点的价值:
- 带头结点:入队、出队都只改
next指针,从不修改front本身(除非释放头结点)。空队列和非空队列的代码路径完全一致,不需要特判。 - 不带头结点:入队第一个元素时要同时改
front和rear;出队最后一个元素时要把rear拉回NULL。每个操作都要写「如果队列为空 / 只剩一个元素」的分支,代码丑且容易漏。
4.4.2 带头结点链队列的完整实现(竞赛写法)
竞赛写法同样只有三样东西:struct Node 描述结点长什么样,两个全局指针 head / tail
(就是上面说的 front / rear,竞赛里更习惯这么写),
再加 4.1.2 表里的那几个自由函数(链队列不会满,所以没有 QueueFull())。
特别注意 DeQueue() 里标了 ★★ 的那一行 —— 出队后队列变空时 tail 必须指回头结点。
// link_queue.cpp —— 带头结点的链队列:struct Node + 全局 head/tail + 自由函数
//
// 先把约定记牢,代码就是这四句话的直译:
// * head 始终指向头结点(哨兵,不存有效数据),真正的队头元素是 head->next;
// * tail 始终指向队尾结点,也就是最后一个真正的数据结点;
// * 空队列 ⇔ head == tail,此时两者都指向头结点,且头结点的 next 为 NULL;
// * 元素个数额外用 cnt 维护,把求长度从 O(n) 降到 O(1)。
//
// 【命名对照】竞赛里习惯写 head / tail,教材里写 front / rear,指的是同一对指针:
// head = front(指向头结点),tail = rear(指向队尾结点)。
//
// 为什么入队、出队都是 O(1)?(对比第 02 讲的单链表:那里插入删除要先按位查找前驱)
// * 入队只改 tail->next 和 tail 两个指针,tail 是现成的,不用从头遍历找尾 → O(1);
// * 出队只改 head->next,head 也是现成的,不用遍历找前驱 → O(1)。
// 一句话:用两个指针(head/tail)换掉了单链表里的两次遍历。
//
// 做题时不回收结点也没关系:程序结束时操作系统会一并回收(本文件只为讲清指针动作)。
#include <bits/stdc++.h>
using namespace std;
struct Node { // 结点:数据域 + 指针域
int data;
Node *next;
Node(int v = 0, Node *p = nullptr) : data(v), next(p) {} // 构造函数可留可去
};
Node *head; // 头结点(哨兵)
Node *tail; // 队尾结点
int cnt; // 元素个数
void InitQueue() { // 初始化:head 与 tail 同时指向新造的头结点
head = new Node(); // 头结点不存数据,只用来把"空队列"与"非空队列"两条路径合并成一条
tail = head;
cnt = 0;
}
bool QueueEmpty() { return head == tail; } // 也可以写 head->next == nullptr,两者等价
int QueueLength() { return cnt; }
bool EnQueue(int x) { // 入队:接在队尾,两步指针操作
Node *s = new Node(x);
tail->next = s; // ① 原尾结点的 next 指向新结点
tail = s; // ② tail 后移,成为新的队尾
++cnt;
// 空队列入队走的是同一条路径:head->next 原本是 nullptr,接上 s 即可,
// 全程不需要动 head —— 这就是头结点"消灭 if 分支"的价值。
return true; // 链队列不会满
}
bool DeQueue(int &e) { // 出队:摘掉 head->next,两步指针操作
if (QueueEmpty()) return false; // 出队前必判空,否则 head->next->data 就是空指针解引用
Node *p = head->next; // p 才是真正的队头结点
e = p->data;
head->next = p->next; // 跨过 p —— 必须先摘链,再 delete p,顺序不能颠倒
if (tail == p) tail = head; // ★★ 经典坑:出队后队列变空,tail 必须指回头结点!
// 漏了这一行,tail 就悬空(指向刚被 delete 的内存),
// 下一次 EnQueue 里的 tail->next = s 就会访问已释放的内存。
delete p;
--cnt;
return true;
}
bool GetHead(int &e) { // 取队头:只读不删
if (QueueEmpty()) return false;
e = head->next->data;
return true;
}
bool GetRear(int &e) { // 取队尾:tail 就指着它
if (QueueEmpty()) return false;
e = tail->data;
return true;
}
void PrintQueue(const char *tag) {
printf("%s [size=%d] head -> ", tag, cnt);
for (Node *p = head->next; p; p = p->next) printf("%d -> ", p->data);
printf("NULL\n");
}
int main() {
InitQueue();
PrintQueue("空队列");
for (int i = 1; i <= 5; ++i) EnQueue(i * 10);
PrintQueue("入队 10..50");
int h = 0, r = 0;
GetHead(h); GetRear(r);
printf("队头 = %d,队尾 = %d\n", h, r);
int v = 0;
DeQueue(v); printf("出队 %d\n", v); PrintQueue("出队一次");
DeQueue(v); printf("出队 %d\n", v); PrintQueue("出队两次");
printf("全部出队: ");
while (DeQueue(v)) printf("%d ", v);
printf("\n清空后 QueueEmpty=%s,head == tail ? %s\n",
QueueEmpty() ? "true" : "false", head == tail ? "是(tail 已归位)" : "否");
PrintQueue("空队列的样子");
// 空队列再入队:验证刚才出队清空时 tail 已经归位,这里不会踩悬空指针
EnQueue(999);
PrintQueue("清空后再入队 999");
DeQueue(v);
printf("再出队 %d,程序正常结束(没有悬空指针)\n", v);
return 0;
}
4.4.3 经典易错点:只有一个元素的队列出队后,rear(= tail)去哪了?
这是链队列最著名的坑,没有之一。假设队列里只剩下一个元素,此时
front->next == rear(队头结点就是队尾结点,按下面代码的命名即 head->next == tail)。
执行出队时,如果只写:
// link_queue_bug.cpp —— 反例:出队时忘记处理 rear(=tail),导致队尾指针悬空
// 本程序可以正常编译运行,但它演示的 DeQueueBuggy() 是一个【逻辑错误】的实现:
// 出队最后一个元素后 rear 仍指向已被 delete 的结点,下一次 push 就是 use-after-free。
// ★★ 这里的 bug 是故意留下的教学反例,请勿"顺手修好":补上 tail = nullptr 就变成正确写法了。
// 竞赛写法:struct 只描述结点长什么样,队列用两个全局指针 + 自由函数维护。
// 【命名对照】竞赛习惯写 head / tail,教材写 front / rear,指的是同一对指针:
// head = front(队头),tail = rear(队尾)。下面统一用 head / tail。
#include <bits/stdc++.h>
using namespace std;
struct Node { int data; Node* next; }; // 结点:数据域 + 指针域,保留 struct
Node* head = nullptr; // 不带头结点,直接指向队头元素(= 教材的 front)
Node* tail = nullptr; // 队尾结点(= 教材的 rear)
void InitQueue() { head = tail = nullptr; }
bool QueueEmpty() { return head == nullptr; }
bool EnQueue(int x) {
Node* s = new Node{x, nullptr};
if (QueueEmpty()) head = tail = s;
else { tail->next = s; tail = s; }
return true; // 链队列不会满
}
// ✗ 错误写法:只把 head(=front)后移,忘了处理 tail(=rear)
bool DeQueueBuggy(int& out) {
if (QueueEmpty()) return false;
Node* p = head; // p 就是队头结点
out = p->data;
head = head->next; // head 后移(若只有一个元素则变成 nullptr)
delete p; // p 被释放
// 漏了:if (head == nullptr) tail = nullptr;
// 此刻 tail 仍指向 p 那块已释放的内存 —— 悬空指针 dangling pointer
return true;
}
int main() {
InitQueue();
EnQueue(42); // 队列中只有 1 个元素:head == tail
int v = 0;
DeQueueBuggy(v);
cout << "出队 -> " << v << "\n";
cout << "出队后 head == nullptr ? " << (head == nullptr ? "是" : "否") << "\n";
cout << "出队后 tail == nullptr ? " << (tail == nullptr ? "是" : "否") << "\n";
cout << "结论:队列逻辑上已空,但 tail 仍然悬空。\n";
cout << " 此处若执行 EnQueue(99),就会写已释放内存(未定义行为),\n";
cout << " 所以我们到此为止,不真的去踩这颗雷。\n";
cout << "正确做法:delete p 之前判断 if (head == nullptr) tail = nullptr;\n";
return 0;
}
为什么会漏?因为大多数人的心智模型是「出队只动 front(代码里的 head),
入队只动 rear(代码里的 tail)」,默认两者互不干扰。
但队列空掉的那一刻,这两个指针必须重新会合——
否则 rear 就悬空了,而下一次入队会直接往已释放的内存里写数据。
正确写法(两种都行)
// link_queue_single_elem.cpp —— 正确处理"最后一个元素出队"的两种写法
// 竞赛写法:全局 head / tail / cnt + 自由函数;结点用 struct 描述。
// 【命名对照】竞赛习惯写 head / tail,教材写 front / rear,指的是同一对指针:
// head = front(头结点),tail = rear(队尾结点)。下面统一用 head / tail。
#include <bits/stdc++.h>
using namespace std;
struct Node { int data; Node* next; }; // 结点:数据域 + 指针域,保留 struct
Node* head; // 指向头结点(哨兵,不存有效数据)
Node* tail; // 指向队尾结点
int cnt; // 元素个数
void InitQueue() {
head = tail = new Node{0, nullptr};
cnt = 0;
}
bool QueueEmpty() { return head == tail; }
bool EnQueue(int x) {
Node* s = new Node{x, nullptr};
tail->next = s;
tail = s;
++cnt;
return true; // 链队列不会满
}
// 写法一:先判断"p 是不是队尾",是则把 tail 拉回头结点(推荐,语义最清晰)
bool DeQueueV1(int& out) {
if (QueueEmpty()) return false;
Node* p = head->next;
out = p->data;
head->next = p->next;
if (tail == p) tail = head; // ★ 关键的一行:队列空了,tail 归位
delete p;
--cnt;
return true;
}
// 写法二:先摘链,再判断"出队后队列是否为空",是则 tail 归位(少一次比较?其实一样)
bool DeQueueV2(int& out) {
if (QueueEmpty()) return false;
Node* p = head->next;
out = p->data;
head->next = p->next;
delete p;
if (head->next == nullptr) tail = head; // ★ 用"摘完是否为空"来判断
--cnt;
return true;
}
int main() {
InitQueue();
cout << "初始 Empty = " << (QueueEmpty() ? "true" : "false") << "\n";
EnQueue(7); // 队列中只有 1 个元素
cout << "入队 7 后 Empty = " << (QueueEmpty() ? "true" : "false") << "\n";
int v = 0;
DeQueueV1(v);
cout << "出队 -> " << v << " Empty = " << (QueueEmpty() ? "true" : "false")
<< " head==tail ? " << (head == tail ? "是(tail 已归位)" : "否(tail 悬空!)") << "\n";
// 出队清空后再入队,验证 tail 依然有效
EnQueue(100); EnQueue(200);
cout << "再次入队 100,200 后依次出队: ";
while (DeQueueV2(v)) cout << v << " ";
cout << "\nEmpty = " << (QueueEmpty() ? "true" : "false") << "\n";
EnQueue(999); // 空队列再入队,验证 head/tail 一致性
DeQueueV1(v);
cout << "再入队 999 出队 -> " << v << ",程序正常结束(没有悬空指针)\n";
delete head; // 释放头结点
return 0;
}
- 出队前必判空:
front == rear(或front->next == nullptr;对应代码里的head == tail)时直接返回false,否则p->data就是空指针解引用。 - 摘链顺序不能颠倒:必须先把
front->next(head->next)指向p->next,再delete p。反过来先去delete再读p->next就是 use-after-free。 - 最后一个元素出队后必须
rear = front(tail = head):这是链队列区别于单链表删除的唯一特殊之处,也是最常考的填空点。
4.5 双端队列 Deque:两端都能进出的「加强版」
队列限制「一端只进、一端只出」,栈限制「同一端进出」。 如果我们把这两种限制全部解除,允许在两端都能插入、都能删除,得到的就是双端队列 double-ended queue,简称 deque(读作 "deck")。
- push_front(x)
- 在前端插入元素 x,x 成为新的队头。
- push_back(x)
- 在后端插入元素 x,x 成为新的队尾。等价于普通队列的入队。
- pop_front()
- 删除前端元素。等价于普通队列的出队。
- pop_back()
- 删除后端元素。
四个操作都是 O(1)。用循环数组实现时,只需要把「单侧前进」变成「front 向前退格、rear 向后前进」两个方向都支持取模即可:
注意 front 前移时同样要先加 MaxSize 再取模 —— 和长度公式踩的是同一个坑。
4.5.2 用 C++ std::deque 演示四种操作
std::deque 是 STL 里真正实现了双端队列的容器(也是 std::queue 与 std::stack 的默认底层容器)。
它允许在两端 O(1) 插入删除,同时还支持随机访问 d[i] —— 这一点比 std::queue 强得多。
// std_deque_demo.cpp —— deque 的四种操作与"栈/队列特例"验证
#include <bits/stdc++.h>
using namespace std;
void show(const string& tag, const deque<int>& d) {
cout << tag << " [size=" << d.size() << "] front->back: ";
for (size_t i = 0; i < d.size(); ++i) cout << d[i] << (i + 1 == d.size() ? "" : " ");
cout << "\n";
}
int main() {
deque<int> d;
cout << "=== 1) 四种基本操作 ===\n";
d.push_back(10); show("push_back(10) ", d);
d.push_back(20); show("push_back(20) ", d);
d.push_front(5); show("push_front(5) ", d);
d.push_front(1); show("push_front(1) ", d);
cout << "front() = " << d.front() << " back() = " << d.back() << "\n";
d.pop_front(); show("pop_front() ", d);
d.pop_back(); show("pop_back() ", d);
cout << "随机访问 d[1] = " << d[1] << "(deque 支持下标,queue 不支持)\n\n";
cout << "=== 2) 只用 push_back + pop_front 就是队列 ===\n";
{
deque<int> q;
for (int i = 1; i <= 4; ++i) q.push_back(i);
cout << "FIFO 出队顺序: ";
while (!q.empty()) { cout << q.front() << " "; q.pop_front(); }
cout << "\n";
}
cout << "=== 3) 只用 push_back + pop_back 就是栈 ===\n";
{
deque<int> s;
for (int i = 1; i <= 4; ++i) s.push_back(i);
cout << "LIFO 出栈顺序: ";
while (!s.empty()) { cout << s.back() << " "; s.pop_back(); }
cout << "\n";
}
cout << "=== 4) 用 deque 手工做一个「输出受限」的双端队列 ===\n";
{
deque<int> od;
od.push_front(1); // 两端都能插入
od.push_back(2);
od.push_front(3);
show("插入后 ", od); // 3 1 2
cout << "只能从 back 端删除: ";
while (!od.empty()) { cout << od.back() << " "; od.pop_back(); }
cout << "\n";
}
return 0;
}
下面这个动画可以亲自动手,在前端 / 后端分别做插入与删除,观察 front 与 rear 指针是如何向两侧扩展的。
4.5.3 统一视角:栈和队列都是双端队列的特例
这句话不是修辞,而是严格的包含关系:
- 队列 = 只用
push_back+pop_front的 deque。「一端进、另一端出」正是 FIFO。 - 栈 = 只用
push_back+pop_back的 deque。「同一端进出」正是 LIFO。 - 输入受限 deque ≈ 「
push_back+ (pop_front|pop_back)」,输出受限 deque ≈ 「(push_front|push_back) +pop_front」。
正因为存在这种包含关系,STL 的实现者才敢用 deque 同时作为 queue 和 stack 的默认底层容器 ——
一套经过充分测试的双端队列代码,加一层薄薄的接口限制,就同时得到了栈和队列。
deque 冒充队列,编译器不会阻止你写 pop_back(),
一旦误用就会破坏 FIFO 语义。这就是为什么 STL 宁可为队列单独包一层 std::queue:
把不该用的操作藏起来,让错误在编译期就暴露。
4.6 循环队列 vs 链队列:怎么选
两种实现都能做到 O(1) 的入队出队,那实际项目里到底用哪个?先看对比表:
| 对比维度 | 循环队列(顺序存储) | 链队列(链式存储) |
|---|---|---|
| 存储方式 | 定长数组 + 取模 | 结点 + next 指针 + 头结点 |
| 入队时间 | O(1),一次赋值一次取模 | O(1),一次 new + 两次指针赋值 |
| 出队时间 | O(1) | O(1)(需特判最后一个元素) |
| 长度 | 方案一需算公式;方案二 O(1) 直读 | 需遍历 O(n),加 size 后 O(1) |
| 空间开销 | 无指针开销,但需预分配 | 每元素多 1 个指针(8 字节) |
| 空间浪费 | 方案一浪费 1 格;预分配过大则内存闲置 | 按需分配,几乎零浪费 |
| 扩容能力 | 固定容量,满了只能拒绝或整体搬迁 | 天然无上限(受内存限制) |
| 内存局部性 locality | 极好,元素连续,CPU 缓存友好 | 差,结点分散在堆上,缓存不友好 |
| 内存分配次数 | 0 次(一次性分配) | 每个元素 1 次 new / delete |
| 随机访问 | 可以(但不该暴露) | 不支持,必须从头遍历 |
| 实现难度 | 判空判满与长度公式易错 | 指针操作与边界特判易错 |
| 典型适用场景 | 容量可预估、追求速度:嵌入式串口缓冲、音频采样、日志队列、多线程任务池 | 长度波动极大且无法预估:任务队列、生产者消费者、动态请求缓冲 |
真实系统里还有一种常见折中:用循环队列 + 动态扩容(满了就
new 一个两倍大的数组,把元素按逻辑顺序搬过去)。
这样既有数组的缓存友好,又不像纯循环队列那样被容量卡死。
(std::deque 走的是另一条路:分块存储 + 一张索引表,不用整体搬迁也能两端 O(1) 增删。)
4.8 应用二:杨辉三角
杨辉三角(Pascal 三角形)是队列最经典的教学例题,因为它把「队列保存上一层结果」这一招用得非常漂亮。
三角的递推规则是:每个数等于它肩上两个数之和,两边恒为 1。第 i 行第 j 个数就是组合数 C(i-1, j-1)。
如果用二维数组算,空间是 O(n²);而用队列,我们只需要保存上一行,
边出队边算出下一行,空间降到 O(n)。
核心技巧:在每行末尾补一个 0 作为哨兵。为什么?因为杨辉三角的边界(每行两端的 1)本质上来自
「上一行不存在的元素视为 0」。在队尾压入一个 0,公式 新元素 = 队头 + 队头后面那个 就能统一处理两端,
不需要任何特判。
把上面的过程写成代码,只有十几行核心逻辑:
// yanghui_triangle.cpp —— 用队列逐层生成杨辉三角(空间 O(n),无特判)
#include <bits/stdc++.h>
using namespace std;
// 队列不变式:front 侧是哨兵 0,中间是第 line 行,rear 侧也是哨兵 0
// 即 [0, r1, r2, ..., r_line, 0],共 line+2 个元素
void PascalTriangle(int rows) {
queue<int> q;
q.push(0); q.push(1); q.push(0); // 第 1 行(两端的 0 是哨兵)
for (int line = 1; line <= rows; ++line) {
// ---- 第 1 步:打印第 line 行 ----
// 把 line+2 个元素全部"弹出再塞回",队列内容与顺序完全不变
for (int k = 0; k <= line + 1; ++k) {
int v = q.front(); q.pop();
if (k >= 1 && k <= line) cout << setw(5) << v; // 跳过两个哨兵
q.push(v);
}
cout << "\n";
// ---- 第 2 步:由第 line 行推出第 line+1 行 ----
// 滑动窗口:弹出 a,窥视 b,把 a+b 塞到队尾
for (int k = 0; k <= line; ++k) {
int a = q.front(); q.pop();
int b = q.front(); // queue 只能看队头,不弹出
q.push(a + b);
}
q.push(0); // 新的行尾哨兵
// 此时队列恰好是 [0, 新的一行..., 0],不变式继续成立
}
}
int main() {
cout << "====== 杨辉三角前 8 行(队列法)======\n";
PascalTriangle(8);
cout << "\n====== 校验:第 5 行应是 1 4 6 4 1,第 8 行应是 1 7 21 35 35 21 7 1 ======\n";
cout << "\n====== 副产物:直接得到二项式系数 C(10,k),不用阶乘 ======\n";
const int n = 10;
queue<long long> q;
q.push(1); // C(n,0) = 1
for (int k = 0; k <= n; ++k) {
long long v = q.front(); q.pop();
cout << v << (k == n ? "" : " ");
if (k < n) q.push(v * (n - k) / (k + 1)); // C(n,k+1) = C(n,k)*(n-k)/(k+1),整除
}
cout << "\n(若用阶乘 n!/(k!(n-k)!) 计算,n 稍大就会溢出;这个递推式的中间值最多是答案的 n 倍,能算的 n 大得多)\n";
return 0;
}
| 写法 | 空间 | 时间 | 说明 |
|---|---|---|---|
二维数组 a[i][j]=a[i-1][j-1]+a[i-1][j] | O(n²) | O(n²) | 最直观,但只需要上一行却存了全部 |
滚动数组 a[j] += a[j-1] | O(n) | O(n²) | 必须倒着遍历 j,否则会用到本轮已更新的值 |
| 队列法(本节) | O(n) | O(n²) | 空间与滚动数组相同,但思路更贴合「一层推一层」的语义 |
n+2 个左右,和滚动数组一样是 O(n)。
4.9 应用三:二叉树的层序遍历(第 07 讲预热)
树的遍历有四种:前序、中序、后序、层序。前三种靠递归(也就是栈)就能写出来, 唯独层序不行 —— 因为层序要求「先访问完第 1 层,再访问第 2 层……同一层里从左到右」, 这个顺序和「入队顺序完全一致」,所以它天生就是队列的地盘。
为什么队列天然适合层序?因为 BFS 式的访问有一个关键性质:
先被访问的结点,它的孩子也一定先被访问。
当我们访问结点 x 时把它的左右孩子依次入队,
队列里就自动形成了「上一层剩余结点在前、下一层结点在后」的隐含分层结构。
每次从队头取一个结点,就相当于按层、从左到右地推进。
// binary_tree_level_order.cpp —— 用队列实现二叉树的层序遍历(含按层分组统计)
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
// 基础版:一层一层从左到右打印
void LevelOrder(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root); // 根结点先入队
while (!q.empty()) {
TreeNode* cur = q.front(); q.pop(); // 出队一个结点 = "访问"它
cout << cur->val << " ";
if (cur->left) q.push(cur->left); // 左孩子入队
if (cur->right) q.push(cur->right); // 右孩子入队
}
cout << "\n";
}
// 进阶版:按层分组输出,顺便统计树高(做题高频)
vector<vector<int>> LevelOrderGrouped(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int sz = (int)q.size(); // ★ 关键:先锁定"本层结点数"
vector<int> layer;
for (int i = 0; i < sz; ++i) { // 只处理这 sz 个,就是同一层
TreeNode* cur = q.front(); q.pop();
layer.push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
res.push_back(layer);
}
return res;
}
int main() {
// 1
// / ╲
// 2 3
// / ╲ / ╲
// 4 5 6 7
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2); root->right = new TreeNode(3);
root->left->left = new TreeNode(4); root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6); root->right->right = new TreeNode(7);
cout << "层序遍历: ";
LevelOrder(root);
cout << "按层分组:\n";
vector<vector<int>> layers = LevelOrderGrouped(root);
for (size_t i = 0; i < layers.size(); ++i) {
cout << " 第 " << i + 1 << " 层(" << layers[i].size() << " 个): ";
for (size_t j = 0; j < layers[i].size(); ++j) cout << layers[i][j] << " ";
cout << "\n";
}
cout << "树的高度 = " << layers.size() << "\n";
// 对比:前序遍历用递归(本质是栈),层序用队列,二者代码结构差别一目了然
cout << "\n对比 —— 右视图(每层最右结点): ";
for (size_t i = 0; i < layers.size(); ++i) cout << layers[i].back() << " ";
cout << "\n(这类「每层 XXX」的题目,全部都是层序遍历 + size 锁定层边界的套路)\n";
return 0;
}
while (!q.empty()) { int sz = q.size(); for (int i = 0; i < sz; ++i) { ... } }这个「先记录
sz = q.size(),再循环 sz 次」的写法,
一次性解决了「分层」「求树高」「求每层最大值」「右视图」「之字形遍历」等一整类题目。
记住它,第 07 讲就能直接用。
4.10 应用四:迷宫最短路径(BFS + 队列)
第 03 讲我们用栈解过迷宫:一条路走到黑,撞墙就回退。它能找到一条通路, 但找不到最短的那条。要想求最短路径,就得换成队列 + BFS(广度优先搜索 breadth-first search)。
4.10.1 为什么 BFS 得到的必然是最短路径?
关键在一个词:逐层扩展。BFS 从起点出发,先把「走 1 步能到」的所有格子全部访问完, 再访问「走 2 步能到」的,再访问「走 3 步能到」的……
x 的最短距离是 d,
那么所有距离小于 d 的格子都会在 x 之前入队。
因此当 x 第一次被访问(第一次入队)时,走过的步数一定就是最短步数 ——
第一次到达即最短。这就是 BFS 求无权图最短路的全部原理。
注意前提条件:BFS 求最短路只对边权相等(无权图 / 每条边代价都是 1)的图成立。 如果每条路的代价不同(比如有的地面走得快、有的泥地走得慢),就得用 Dijkstra(第 09 讲)。 这也是考试常考的辨析点。
4.11 应用五:单调队列与滑动窗口最大值
这是队列在算法竞赛里最精彩的应用,也是「把 O(nk) 降到 O(n)」的经典范例。
4.11.1 问题:滑动窗口最大值
给定数组 a[0..n-1] 和一个窗口大小 k。
窗口从左向右滑动,每次移动一格,求每个窗口内的最大值。
暴力做法:每个窗口遍历 k 个元素找最大,一共 n-k+1 个窗口,
时间 O(nk)。当 n = 10⁶, k = 10³ 时就是 10⁹ 次运算,妥妥超时。
浪费在哪?相邻两个窗口有 k-1 个元素是重叠的,
暴力法却把它们的比较完全重做了一遍。更糟的是,如果一个元素比它右边新进来的元素小,
那它在有生之年都不可能成为最大值了 —— 它已经被后面的强者「永久压制」。
我们完全没必要再留着它。
4.11.2 单调递减队列:把「没用的元素」踢出去
维护一个队列,里面存下标(不是数值,因为要靠下标判断是否滑出窗口),并保证:
- 队列里的下标严格递增(天然满足,因为我们从左到右扫描);
- 队列里的数值严格递减(新元素入队前,把所有不比它大的队尾元素全部弹走)。
满足这两条,队头就永远是当前窗口的最大值。三个动作:
① 入队(去尾):新元素 a[i] 到来时,从队尾开始,
把所有 ≤ a[i] 的元素下标弹出去,然后把 i 压入队尾。
为什么可以弹?因为它们既不比 a[i] 大,又比 a[i] 先离开窗口 ——
永远没有翻身的机会。这一操作叫「单调性维护」。
② 出队(去头):检查队头下标是否 < i - k + 1(已经滑出窗口左边界),是则弹出。
③ 取答案:当 i >= k - 1(窗口已经填满)时,
队头下标对应的数值就是本窗口最大值。
为什么整体是 O(n)?这是最容易被问到的一点,答案是均摊分析 amortized analysis:
每个下标最多入队一次、出队一次(要么因为被新元素顶掉,要么因为滑出窗口),
所以 while 循环在整个算法中总共只执行 O(n) 次。
虽然有嵌套循环,但总工作量是线性的。
下面这个动画让你逐步观察窗口移动、队尾淘汰与队头过期,是最值得反复看的一个演示。
// sliding_window_max.cpp —— 单调队列 O(n) 求滑动窗口最大值
#include <bits/stdc++.h>
using namespace std;
// 返回每个长度为 k 的窗口的最大值;窗口数 = n-k+1
vector<int> MaxSlidingWindow(const vector<int>& a, int k) {
vector<int> res;
deque<int> dq; // ★ 单调递减队列,存放【下标】
if (k <= 0 || (int)a.size() < k) return res;
for (int i = 0; i < (int)a.size(); ++i) {
// ① 去尾:队尾元素如果 ≤ 当前元素,就永远不可能成为最大值,弹出
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
// ② 去头:队头下标如果已经滑出窗口左边界,弹出
if (dq.front() <= i - k) dq.pop_front();
// ③ 取答案:窗口填满后,队头就是本窗口最大值
if (i >= k - 1) res.push_back(a[dq.front()]);
}
return res;
}
// 对照用:暴力法 O(nk)
vector<int> MaxSlidingWindowBrute(const vector<int>& a, int k) {
vector<int> res;
for (int i = 0; i + k <= (int)a.size(); ++i) {
int mx = a[i];
for (int j = i + 1; j < i + k; ++j) mx = max(mx, a[j]);
res.push_back(mx);
}
return res;
}
int main() {
vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
cout << "数组: ";
for (size_t i = 0; i < a.size(); ++i) cout << a[i] << " ";
cout << " 窗口大小 k = " << k << "\n\n";
vector<int> fast = MaxSlidingWindow(a, k);
vector<int> slow = MaxSlidingWindowBrute(a, k);
cout << "单调队列 O(n) 结果: ";
for (size_t i = 0; i < fast.size(); ++i) cout << fast[i] << " ";
cout << "\n暴力法 O(nk) 结果: ";
for (size_t i = 0; i < slow.size(); ++i) cout << slow[i] << " ";
cout << "\n两种方法结果一致: " << (fast == slow ? "是" : "否") << "\n\n";
// ---- 变形 1:滑动窗口最小值(把比较符号反过来即可)----
{
deque<int> dq; vector<int> mn;
for (int i = 0; i < (int)a.size(); ++i) {
while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back(); // 改成单调递增
dq.push_back(i);
if (dq.front() <= i - k) dq.pop_front();
if (i >= k - 1) mn.push_back(a[dq.front()]);
}
cout << "变形:滑动窗口最小值 = ";
for (size_t i = 0; i < mn.size(); ++i) cout << mn[i] << " ";
cout << "\n";
}
// ---- 变形 2:求长度不超过 k 的连续子数组最大和 ----
{
vector<long long> pre(a.size() + 1, 0);
for (size_t i = 0; i < a.size(); ++i) pre[i + 1] = pre[i] + a[i];
deque<int> dq; long long best = LLONG_MIN;
for (int i = 0; i <= (int)a.size(); ++i) {
if (!dq.empty() && dq.front() < i - k) dq.pop_front(); // 左端点 j 必须 ≥ i-k
if (i > 0) best = max(best, pre[i] - pre[dq.front()]); // 子数组 a[j..i-1],长度 1..k
while (!dq.empty() && pre[dq.back()] >= pre[i]) dq.pop_back(); // 维护前缀和最小
dq.push_back(i); // 先算答案再入队,保证子数组非空
}
cout << "变形:长度不超过 " << k << " 的最大子数组和 = " << best << "\n";
}
cout << "\n复杂度对比:暴力法每个窗口比较 k-1 次,共 " << (a.size() - k + 1) * (k - 1)
<< " 次;单调队列 O(n),每个下标最多进出各一次。\n";
return 0;
}
- 为什么弹出队尾?因为它们比新元素小(或相等)且更早离开窗口,永远不可能成为答案。
- 为什么弹出队头?因为它的下标已经滑出窗口范围,虽然值可能很大,但已经「不在场」了。
- 为什么是 O(n)?每个下标至多入队一次、出队一次,均摊 O(1);不是 O(nk),尽管代码里有嵌套的 while。
<= 改成 >=,队列变成单调递增,队头即最小值。就这么简单。
dq.front() <= i - k(或 < i - k + 1),
写成 < i - k + 1 与 <= i - k 是等价的。别图省事写成 dq.front() == i - k ——
窗口每次只滑一格时它碰巧也对,但到了窗口一次跳好几格的变形题里就会漏判;写 <= 永远安全。
4.13 C++ STL 中的队列家族
C++ 标准库提供了三个和队列直接相关的容器适配器 / 容器。它们的关系是:
std::queue 和 std::stack 都是「容器适配器」,默认底层容器就是 std::deque;
而 std::priority_queue 是「带优先级的队列」,底层是堆。
std::queue 接口速查
| 操作 | 含义 | 复杂度 | 备注 |
|---|---|---|---|
q.push(x) | 入队 | O(1) | 等价于 emplace,但 emplace 是原地构造,更省一次拷贝 |
q.pop() | 出队 | O(1) | 返回 void,不返回元素值! |
q.front() | 取队头 | O(1) | 空队列调用是未定义行为 |
q.back() | 取队尾 | O(1) | 空队列调用是未定义行为 |
q.empty() | 判空 | O(1) | 取元素前必须先判 |
q.size() | 元素个数 | O(1) | 返回 size_t(无符号!) |
q = q2 | 赋值 | O(n) | 元素可拷贝即可 |
q.swap(q2) | 交换 | O(1) | 常用于「清空队列」的惯用法 |
| 遍历 / 下标 / 迭代器 | 不支持 | — | queue 有意不提供 begin():只能访问两端 |
q.clear() | 不存在 | — | 要清空只能循环 pop() 或与空队列 swap |
std::deque 接口速查
| 操作 | 含义 | 复杂度 | 备注 |
|---|---|---|---|
d.push_back(x) / d.push_front(x) | 两端插入 | O(1) | deque 的核心价值 |
d.pop_back() / d.pop_front() | 两端删除 | O(1) | 同样返回 void |
d.front() / d.back() | 取两端元素 | O(1) | — |
d[i] / d.at(i) | 随机访问 | O(1) | queue 没有这个能力,别混用 |
d.insert(pos, x) / d.erase(pos) | 中间插删 | O(n) | 要移动元素,尽量别用 |
d.clear() | 清空 | O(n) | deque 有,queue 没有 |
| 迭代器失效 | — | — | 两端插入会使全部迭代器失效(但指向元素的引用仍有效);两端删除只让被删元素的迭代器失效;中间插删则全部失效 |
std::priority_queue:优先队列(第 11 讲预热)
优先队列出队的不是「最早进来的」,而是「优先级最高的」。
它不满足 FIFO,所以严格来说不是队列,只是名字里带 queue。
底层用二叉堆 binary heap 实现,入队出队都是 O(log n),
取堆顶是 O(1) —— 这正是第 11 讲堆排序与第 09 讲 Dijkstra 优化的基础工具。
| 操作 | 含义 | 复杂度 | 备注 |
|---|---|---|---|
pq.push(x) | 插入 | O(log n) | 向上调整 sift-up |
pq.pop() | 弹出堆顶 | O(log n) | 向下调整 sift-down |
pq.top() | 取堆顶 | O(1) | 默认是最大值(大顶堆) |
priority_queue<int, vector<int>, greater<int>> | 小顶堆写法 | — | 三个模板参数一个都不能少(第三个是「比较器」) |
STL 队列的六个常见坑
pop()不返回元素值。必须写成int v = q.front(); q.pop();。 为什么这么设计?因为「返回值 + 删除」在异常安全与效率上都有麻烦,标准库选择了最朴素的语义。- 对空队列调用
front()/back()/pop()是未定义行为。 编译器和运行时都不会提醒你,常见后果是读到垃圾值或者直接段错误(Runtime Error)。 queue不能遍历、不能下标、没有迭代器。 想打印队列内容,只能「边出队边打印」,或者改用deque。 这不是缺陷,而是刻意的封装(见 4.1.2 节的讨论)。size()返回无符号数。写for (int i = 0; i < q.size() - 1; ++i)时, 若q.size()为 0,q.size() - 1会回绕成一个巨大的正数 —— 经典死循环来源。 正确写法是先转int:int sz = (int)q.size();。priority_queue默认是大顶堆。想取最小值必须写全三个模板参数, 而且比较器用的是greater(与自己写operator<的直觉相反)。queue没有clear()。 清空的惯用法是queue<int>().swap(q);(与临时空队列交换),一行搞定。
// stl_queue_family.cpp —— queue / deque / priority_queue 三大件实操
#include <bits/stdc++.h>
using namespace std;
struct Task {
string name;
int priority; // 数字越大优先级越高
// priority_queue 默认用 less<Task>,也就是「谁的 operator< 为真谁排在后面」
bool operator<(const Task& o) const { return priority < o.priority; }
};
int main() {
/* ================= 1. queue:普通 FIFO ================= */
cout << "=========== 1. queue ===========\n";
queue<string> q;
q.push("客户A");
q.push("客户B");
q.push("客户C");
cout << "队头 = " << q.front() << ",队尾 = " << q.back()
<< ",大小 = " << q.size() << "\n";
while (!q.empty()) { // 想遍历 queue?只能边出队边看
string s = q.front(); // ★ 先取
q.pop(); // ★ 再弹(pop 不返回值)
cout << "出队: " << s << " 剩余 " << q.size() << "\n";
}
cout << "queue 没有 clear(),惯用清空写法: queue<string>().swap(q);\n";
queue<string>().swap(q);
cout << "清空后 empty = " << (q.empty() ? "true" : "false") << "\n\n";
/* ================= 2. deque:两端都能动 ================= */
cout << "=========== 2. deque ===========\n";
deque<int> d;
d.push_back(3); d.push_back(4);
d.push_front(2); d.push_front(1); // 前端插入
cout << "deque 内容: ";
for (size_t i = 0; i < d.size(); ++i) cout << d[i] << " "; // 支持随机访问
cout << "\n";
// 单调队列:用 deque 从两端操作,是它的经典用法
vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
deque<int> mono; // 存下标,保持数值单调递减
cout << "滑动窗口最大值(k=" << k << "): ";
for (int i = 0; i < (int)a.size(); ++i) {
while (!mono.empty() && a[mono.back()] <= a[i]) mono.pop_back(); // 去尾
mono.push_back(i);
if (mono.front() <= i - k) mono.pop_front(); // 去头
if (i >= k - 1) cout << a[mono.front()] << " ";
}
cout << "\n\n";
/* ================= 3. priority_queue:堆 ================= */
cout << "=========== 3. priority_queue ===========\n";
priority_queue<int> maxHeap; // 默认大顶堆
for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) maxHeap.push(x);
cout << "大顶堆依次弹出: ";
while (!maxHeap.empty()) { cout << maxHeap.top() << " "; maxHeap.pop(); }
cout << "\n";
priority_queue<int, vector<int>, greater<int>> minHeap; // 小顶堆:三个参数都要写
for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) minHeap.push(x);
cout << "小顶堆依次弹出: ";
while (!minHeap.empty()) { cout << minHeap.top() << " "; minHeap.pop(); }
cout << "\n";
priority_queue<Task> tasks; // 自定义类型:按 priority 排序
tasks.push({"写作业", 2});
tasks.push({"打游戏", 1});
tasks.push({"交论文", 9});
tasks.push({"回消息", 5});
cout << "按优先级处理任务: ";
while (!tasks.empty()) {
Task t = tasks.top(); tasks.pop();
cout << t.name << "(" << t.priority << ") ";
}
cout << "\n";
cout << "\n小结:queue 只能先进先出;deque 两端 O(1) 且能随机访问;\n";
cout << " priority_queue 是堆,O(log n) 取最值,不保证 FIFO。\n";
return 0;
}