第 04 讲

队列及其应用

从食堂打饭的队形讲到操作系统的调度队列:搞懂 FIFO 的本质、循环队列的取模技巧、 链队列的指针细节,再用队列解决杨辉三角、层序遍历、迷宫最短路和滑动窗口最大值。

预计 100 分钟 前置:第 02 讲 线性表 · 第 03 讲 栈 关键词:FIFO · 循环队列 · 假溢出 · 单调队列 · BFS
本章导读
  • 概念层:队列的定义、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。

一句话本质 队列 = 加了「两端分工」约束的线性表:一端只进、另一端只出,于是元素的出队顺序与入队顺序完全一致。 栈是「后进先出 LIFO」,队列是「先进先出 FIFO」,这一字之差决定了它们能解决完全不同的问题。

4.1.1 FIFO:队列最核心的性质

FIFO 不是一句口号,它有三个可以拿来考试、也可以拿来写代码的等价推论:

  1. 出队序列 = 入队序列。若元素依次入队 a₁, a₂, …, aₙ,则出队顺序必定是 a₁, a₂, …, aₙ,中途出队、入队交错也改变不了这个相对次序。
  2. 队头元素是「最早到达且尚未离开」的元素。这句话在模拟类题目里就是「谁先来谁先被服务」。
  3. 队列保证公平性(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 放到队尾,成为新的队尾队不满,否则返回 falseO(1)
DeQueue(e)出队:删除队头元素并用 e 带回队不空,否则返回 falseO(1)
GetHead(e)取队头:用 e 带回,只读不删队不空O(1)
ADT 里「没有」的操作才是重点 队列的 ADT 里故意不提供「按位置查找」「遍历」「从中间删除」。 这不是偷懒,而是信息隐藏:一旦允许随便访问中间元素,队列的 FIFO 语义就守不住了。 考试里若有人写「队列支持随机访问」,那是把 std::deque 的随机访问能力和队列的语义混为一谈了。

4.1.3 队列 vs 栈:一张图看清区别

下面这张对照图建议直接记进脑子:栈是「单口容器」,队列是「双口管道」。 栈的所有动作都发生在同一个口上,队列则在两端各开一个口。

栈 stack | 后进先出 LIFO 30 20 10 5 ← top 入栈 push 出栈 pop 插入与删除都在同一端(栈顶) 队列 queue | 先进先出 FIFO 5 10 20 30 front rear 出队 dequeue 入队 enqueue 入队在队尾(右),出队在队头(左),两端分工 先入队的 5 一定先出队,次序不会被后来的元素打乱
图 4-1 栈与队列对照:栈单口进出(LIFO),队列双口分工(FIFO)
对比维度栈 stack队列 queue
插入位置栈顶 top队尾 rear
删除位置栈顶 top(与插入同端)队头 front(与插入异端)
存取次序LIFO 后进先出FIFO 先进先出
典型比喻叠盘子、弹夹、浏览器后退排队打饭、打印机任务、收费站
元素个数为 n 时可能的出栈/出队序列数卡特兰数 C(2n,n)/(n+1)只有 1 种(即入队序列本身)
典型应用括号匹配、表达式求值、递归、DFS、单调栈层序遍历、BFS、缓冲池、调度、单调队列
基本操作复杂度入栈 / 出栈均 O(1)入队 / 出队均 O(1)
考点 4-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)。

看起来很干净,对吧?问题就出在最后两条上。

4.2.2 假溢出:明明有空位,为什么说队满?

关键在于 front 和 rear 都只会往后走,从来不回头。 出队让 front 右移,入队让 rear 右移,于是每出队一个元素, 队列前方就多出一个「永远用不到」的空位。等 rear 撞到 MaxSize 时, 程序判定「队满」,可数组前面那些空位其实还能装好几个元素。

下面这张分步图把它画得很直白。设 MaxSize = 8:

① 入队 A B C D 四个元素 A B C D — — — — 01 23 45 67 front=0 rear=4 元素个数 = 4 − 0 = 4 ② 出队 A B 两个元素(front 右移,但空位留在最前面) 空 空 C D — — — — front=2 rear=4 元素个数 = 4 − 2 = 2 ③ 再入队 E F G H —— rear 撞到 MaxSize,被判定「队满」 空 空 C D E F G H front=2 rear=8 == MaxSize 这两个空位永远用不到了 → 假溢出 元素个数 = 8 − 2 = 6
图 4-2 顺序队列的假溢出:rear 撞到 MaxSize 时,前面仍有 2 个空位无法使用

把这三步连起来看,问题的根子就清楚了:数组是「线性 + 有限」的,而 front / rear 是单调递增的。 每次出队都在数组头部制造一块「死区」,死区只会变大不会变小,最终把整个数组的前半段全部浪费掉。 此时队列真实占用 = rear - front = 6,而容量是 8,明明还能塞 2 个,却只能报「队满」。

易错点 4-1 假溢出 ≠ 真溢出
  • 真溢出 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说明
011正常后移
344正常后移
677正常后移
78(越界!)0(绕回队首)关键的一步
9101无论走多远都能映射回 0..7

为什么 % MaxSize 恰好能实现「绕回」?因为余数的取值范围天然就是 [0, MaxSize-1], 正好是合法下标的集合;而只要没超过 MaxSize,余数就等于原数,不影响正常情形。 一行代码同时兼顾了「前进」和「绕回」两件事,这就是取模的优雅之处。

下图把 MaxSize = 8 的循环队列画成一个环:外圈数字是数组下标,环内是元素值。 注意「队尾」永远在 rear 的逆时针前一格,因为 rear 指向的是下一个空位(下一个要写入的位置)。

11 22 33 — — — — — data[0] data[1] data[2] data[3] data[4] data[5] data[6] data[7] front = 0 rear = 3 共 3 个元素 (3-0+8)%8 = 3 rear 前进方向 (rear+1)%8 到 7 之后回 0 环外是物理下标,环内是元素值;rear 指向下一个空位,所以队尾元素在 rear 的前一格
图 4-3 循环队列的环形视图: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 == rearsize == 0front==rear && tag==0
判满条件(rear+1)%M == frontsize == MaxSizefront==rear && tag==1
最大元素数MaxSize − 1(浪费 1 格)MaxSize(零浪费)MaxSize(零浪费)
额外空间01 个 int1 个 int(可压成 1 bit)
求长度要算 (rear-front+M)%M直接返回 size重合时要靠 tag 特判
每次操作成本1 次取模1 次取模 + 1 次自增1 次取模 + 1 次赋值
实现难度最简单简单,但容易漏维护 size判断条件最绕,易写错
典型出处考研 408、严蔚敏教材默认写法绝大多数工业级 ring buffer教材补充、面试手写题
适用场景元素大小敏感度低、追求代码短需要频繁查长度、容量不能浪费要求「空间零浪费且不加计数器」的场合
考点 4-2 题目若只说「循环队列」而不指定方案,默认按方案一(牺牲一个单元)作答: 容量为 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],取余后不变。 于是两种情况可以统一写成:

Length = (rear − front + MaxSize) % MaxSize

也可以写成等价形式 (rear - front) % MaxSize 之后再 + MaxSize 再 % MaxSize, 但没人这么写 —— 先加 MaxSize 保证非负是最省事、最不容易出错的写法。

易错点 4-2 为什么必须先加 MaxSize? 因为 C++ 的 % 是截断取余(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 / QueueFullO(1)O(1)一次比较或取模
Length 求长度O(1)O(1)方案二更是直接返回 size
遍历O(n)O(1)必须按 (i+1)%cap 走,不能简单 i++
整表—O(MaxSize) 预分配数组容量固定,是典型的静态结构
易错点 4-3 遍历循环队列时不能用 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), 它不存放有效数据,只用来统一边界情况。

于是约定变成:

非空队列(带头结点) head next 头结点(不存数据) 5 next 10 next 20 ∧ front rear ← 真正的队头 front->next 空队列 head ∧ front rear 空队列时 front == rear,都指向头结点,头结点的 next 为 NULL
图 4-4 带头结点的链队列:front 指向头结点,rear 指向尾结点,空队列时两者重合

为什么说「出入队都是 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)
取队头 GetHeadx = front->next->data;否O(1)
判空 QueueEmptyfront == rear(或 front->next == NULL)否O(1)
求长度 Length从头结点走一遍到 rear是O(n),可加 size 优化到 O(1)

对比一下不带头结点的版本,你立刻能看出头结点的价值:

头结点的通用思想 「加一个不存数据的哨兵结点,把边界情况变成一般情况」是链表类题目的万能套路: 单链表的插入删除、链栈、链队列、双向链表都用它。 记住一句话:哨兵不解决算法问题,它只消灭 if 分支。

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;
}
易错点 4-4 链队列出队的三条铁律
  1. 出队前必判空:front == rear(或 front->next == nullptr;对应代码里的 head == tail)时直接返回 false,否则 p->data 就是空指针解引用。
  2. 摘链顺序不能颠倒:必须先把 front->next(head->next)指向 p->next,再 delete p。反过来先去 delete 再读 p->next 就是 use-after-free。
  3. 最后一个元素出队后必须 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 = (front − 1 + MaxSize) % MaxSize  rear = (rear + 1) % MaxSize

注意 front 前移时同样要先加 MaxSize 再取模 —— 和长度公式踩的是同一个坑。

双端队列 deque:两端均可插入、均可删除 12 7 25 3 front 端 back 端 push_front 前端插入 pop_front 前端删除 push_back 后端插入 pop_back 后端删除 只允许 push_back / pop_front 使用 → 退化为普通队列(FIFO) 只允许 push_back / pop_back 使用 → 退化为栈(LIFO)
图 4-6 双端队列:两端都能进出,因此栈与队列都是它的特例

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 统一视角:栈和队列都是双端队列的特例

这句话不是修辞,而是严格的包含关系:

正因为存在这种包含关系,STL 的实现者才敢用 deque 同时作为 queue 和 stack 的默认底层容器 —— 一套经过充分测试的双端队列代码,加一层薄薄的接口限制,就同时得到了栈和队列。

设计启示:约束即价值 从数据结构的能力上看,deque ⊃ 受限 deque ⊃ 队列 / 栈(单调队列只用 push_back、pop_front、pop_back,恰好是一个输入受限 deque); 但能力越强的结构,越难保证语义。用 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) 增删。)
本节从略 银行排队模拟从略:队列的应用保留层序遍历、BFS 最短路与单调队列;这三块已经覆盖队列的主要用法。

4.8 应用二:杨辉三角

杨辉三角(Pascal 三角形)是队列最经典的教学例题,因为它把「队列保存上一层结果」这一招用得非常漂亮。

三角的递推规则是:每个数等于它肩上两个数之和,两边恒为 1。第 i 行第 j 个数就是组合数 C(i-1, j-1)。 如果用二维数组算,空间是 O(n²);而用队列,我们只需要保存上一行, 边出队边算出下一行,空间降到 O(n)。

核心技巧:在每行末尾补一个 0 作为哨兵。为什么?因为杨辉三角的边界(每行两端的 1)本质上来自 「上一行不存在的元素视为 0」。在队尾压入一个 0,公式 新元素 = 队头 + 队头后面那个 就能统一处理两端, 不需要任何特判。

杨辉三角:每个数 = 肩上两数之和 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1+1=2 用队列逐层生成(以第 3 行 → 第 4 行为例) 队列 = 哨兵 0 + 第 3 行 + 哨兵 0: 0 1 2 1 0 ① 取队头 a=0,看下一个 b=1 → 入队 0+1 = 1 ② 取队头 a=1,看下一个 b=2 → 入队 1+2 = 3 ③ 取队头 a=2,看下一个 b=1 → 入队 2+1 = 3 ④ 取队头 a=1,看下一个 b=0 → 入队 1+0 = 1 新一行 = 1 3 3 1,队尾再补一个哨兵 0 供下一轮使用 0 1 3 3 1 0 ← 生成结束后的队列(旧前导哨兵被吃掉,旧尾哨兵变成新前导哨兵) 每一步只做「弹出 a、窥视 b、入队 a+b」,循环体里没有一个 if 分支。 哨兵 0 的作用:把"行首与行尾要特殊处理"变成统一的加法运算,循环体里一个 if 都不需要。
图 4-8 杨辉三角:用队列保存上一行,队尾补 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;
}
易错点 4-6 杨辉三角的三种写法与空间对比
写法空间时间说明
二维数组 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 时把它的左右孩子依次入队, 队列里就自动形成了「上一层剩余结点在前、下一层结点在后」的隐含分层结构。 每次从队头取一个结点,就相当于按层、从左到右地推进。

一棵二叉树(结点里标的是访问序号) A1 B2 C3 D4 E5 F6 G7 访问顺序:A → B → C → D → E → F → G(正是入队顺序) 队列在每个时刻的内容(front 在左) 访问 A 前: A 根结点先入队 弹出 A,压入 B C: B C ← 第 2 层到齐 弹出 B,压入 D E: C D E 弹出 C,压入 F G: D E F G ← 第 3 层到齐 关键不变式:同一层的结点在队列里一定是连续的一段,且不跨层交错。 想统计"树有几层""每层有多少结点"?只需在每轮开始前记下 size = q.size(), 这批 size 个结点就正好是同一层 —— 这是层序题目的万能套路。 时间 O(n)、空间 O(最宽一层的结点数),最坏(满二叉树最后一层)为 O(n)。
图 4-9 二叉树层序遍历:队列中同一层结点连续排列,出队顺序就是层序
// 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;
}
考点 4-5 层序题的万能模板 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 单调递减队列:把「没用的元素」踢出去

维护一个队列,里面存下标(不是数值,因为要靠下标判断是否滑出窗口),并保证:

  1. 队列里的下标严格递增(天然满足,因为我们从左到右扫描);
  2. 队列里的数值严格递减(新元素入队前,把所有不比它大的队尾元素全部弹走)。

满足这两条,队头就永远是当前窗口的最大值。三个动作:

① 入队(去尾):新元素 a[i] 到来时,从队尾开始, 把所有 ≤ a[i] 的元素下标弹出去,然后把 i 压入队尾。
为什么可以弹?因为它们既不比 a[i] 大,又比 a[i] 先离开窗口 —— 永远没有翻身的机会。这一操作叫「单调性维护」。

② 出队(去头):检查队头下标是否 < i - k + 1(已经滑出窗口左边界),是则弹出。

③ 取答案:当 i >= k - 1(窗口已经填满)时, 队头下标对应的数值就是本窗口最大值。

为什么整体是 O(n)?这是最容易被问到的一点,答案是均摊分析 amortized analysis: 每个下标最多入队一次、出队一次(要么因为被新元素顶掉,要么因为滑出窗口), 所以 while 循环在整个算法中总共只执行 O(n) 次。 虽然有嵌套循环,但总工作量是线性的。

数组 a = [1, 3, -1, -3, 5, 3, 6, 7],k = 3 1 3 -1 -3 5 3 6 7 012 345 67 窗口 [0,2] 最大值 = 3 窗口 [4,6] 最大值 = 6 扫描过程中单调队列(存下标)的变化 i=0, a=1 0(1) 队尾没有更小的元素,直接入队 i=1, a=3 0 弹出 1(3) 1 ≤ 3 且更早离开 → 永久淘汰 i=2, a=-1 1(3) 2(-1) 3 > -1,保留;-1 入队 → 输出 3 i=3, a=-3 1(3) 2(-1) 3(-3) 输出 3 i=4, a=5 1 滑出 2 弹出 3 弹出 4(5) 5 比它们都大 → 全部清空,输出 5 i=5, a=3 4(5) 5(3) 输出 5 i=6, a=6 4(5) 5 弹出 6(6) 输出 6 最终答案 窗口 [0,2] → 3 窗口 [1,3] → 3 窗口 [2,4] → 5 窗口 [3,5] → 5 窗口 [4,6] → 6 窗口 [5,7] → 7 结果数组:[3, 3, 5, 5, 6, 7] 每个下标最多进队一次、出队一次 → 总时间 O(n) 暴力法:6 个窗口 × 每窗比较 2 次 = 12 次;单调队列每个下标只进出一次。
图 4-11 单调递减队列求滑动窗口最大值:被淘汰的下标再无翻身机会

下面这个动画让你逐步观察窗口移动、队尾淘汰与队头过期,是最值得反复看的一个演示。

// 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;
}
考点 4-6 单调队列三连问
  1. 为什么弹出队尾?因为它们比新元素小(或相等)且更早离开窗口,永远不可能成为答案。
  2. 为什么弹出队头?因为它的下标已经滑出窗口范围,虽然值可能很大,但已经「不在场」了。
  3. 为什么是 O(n)?每个下标至多入队一次、出队一次,均摊 O(1);不是 O(nk),尽管代码里有嵌套的 while。
追问:「如果要求窗口最小值呢?」把 <= 改成 >=,队列变成单调递增,队头即最小值。就这么简单。
易错点 4-8 单调队列存的是下标,不是数值 如果队列里只存数值,就无法判断「队头是否已经滑出窗口」。 这是单调队列实现中最常见的错误。同理,去头判断写的是 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 队列的六个常见坑

易错点 4-9 这六个坑几乎每个人都踩过
  1. pop() 不返回元素值。必须写成 int v = q.front(); q.pop();。 为什么这么设计?因为「返回值 + 删除」在异常安全与效率上都有麻烦,标准库选择了最朴素的语义。
  2. 对空队列调用 front() / back() / pop() 是未定义行为。 编译器和运行时都不会提醒你,常见后果是读到垃圾值或者直接段错误(Runtime Error)。
  3. queue 不能遍历、不能下标、没有迭代器。 想打印队列内容,只能「边出队边打印」,或者改用 deque。 这不是缺陷,而是刻意的封装(见 4.1.2 节的讨论)。
  4. size() 返回无符号数。写 for (int i = 0; i < q.size() - 1; ++i) 时, 若 q.size() 为 0,q.size() - 1 会回绕成一个巨大的正数 —— 经典死循环来源。 正确写法是先转 int:int sz = (int)q.size();。
  5. priority_queue 默认是大顶堆。想取最小值必须写全三个模板参数, 而且比较器用的是 greater(与自己写 operator< 的直觉相反)。
  6. 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;
}