队列及其应用

4.1 队列的定义与抽象数据类型

先别急着看代码。想象一下中午十二点的食堂：所有同学很自觉地排成一列，新来的人站到队伍最后， 窗口师傅只从队伍最前面叫号。没有人会插队（我们希望如此），也没有人能从中间被叫走。 这个每天都在发生的场景，就是数据结构里最实用的结构之一 —— 队列 queue。

把食堂翻译成术语：队列是只允许在一端插入、在另一端删除的线性表 linear list。 允许插入的那一端叫队尾 rear（tail），允许删除的那一端叫队头 front（head）。 插入操作叫入队 enqueue，删除操作叫出队 dequeue。 由于先来的人先被服务，队列的存取次序是先进先出 First In First Out，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 非常小，小到只有五个操作，这也是它好用的原因：

InitQueue(&Q)

初始化。构造一个空队列。对循环队列来说是 front = rear = 0；对带头结点的链队列来说是 front = rear = new Node。

QueueEmpty(Q)

判空。空队列返回 true。所有出队、取队头操作之前都必须先判空，这是本章最容易漏掉的一步。

EnQueue(&Q, x)

入队。若队列未满，把元素 x 放到队尾，成为新的队尾。失败（队满）时一般返回 false 而不是抛异常，方便上层做「缓冲池满」的流控。

DeQueue(&Q, &x)

出队。若队列非空，删除队头元素并用 x 「带回」它的值。注意这个「带回」是通过引用参数实现的 —— 这是 C 风格 ADT 的写法，C++ 里也可以让 DeQueue() 直接返回元素值。

GetHead(Q, &x)

取队头元素。只读不删，队列状态不变。它和出队的区别，就像「看一眼排队叫号屏」和「真的被叫走」。

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

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

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 个，却只能报「队满」。

下面这个动画把假溢出的全过程演示一遍。留意 front 是怎么一步步把前面的空位「吃掉」的。

看完动画你应该能自己总结出结论：只要让 rear 在撞到 MaxSize 之后能回到下标 0， 假溢出就自然消失了 —— 这正是下一节循环队列要干的事。

4.2.3 朴素顺序队列的完整 C++ 实现

为了让你亲眼看到假溢出，下面这份代码故意用朴素写法实现，并在 main 里构造出「队满但有空位」的场景。 拷贝下来跑一遍，观察输出里 size=6, MaxSize=8 却 EnQueue failed 的那一行。

// 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) 入队 A B C D ---\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;
    for (int i = 0; i < 2; ++i) {
        deQueue(x);
        cout << "DeQueue " << x << "  front=" << front
             << " rear=" << rear << " size=" << queueLength() << "\n";
    }

    cout << "--- 3) 再入队 4 个，看谁失败 ---\n";
    for (int i = 5; i <= 8; ++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;
}

4.3 循环队列：把数组「掰弯」

假溢出的根源是「下标只增不减」。那么解法就呼之欲出了：给下标加一个上限，越界就回到 0。 物理上数组还是一维的，但逻辑上我们把它的首尾接了起来，构成一个环 —— 这就是循环队列 circular queue， 也叫环形队列 ring buffer。

4.3.1 取模运算 (rear + 1) % MaxSize 的原理

取模（模运算 modulo）的含义是「除法的余数」。当 MaxSize = 8 时：

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

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

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 计数器，容量不浪费
//
// 【与方案一、方案三的区别】三者的 push/pop 主体完全一样，只差"判空判满靠什么"：
//   方案一：靠"留一格"，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;
}

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);
    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 才有意义**，
//          所以 push/pop 里每次都要记得更新 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;
}

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);
    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;
}

4.3.3 元素个数公式的推导

公式 (rear - front + MaxSize) % MaxSize 看着像背下来的，其实推两行就明白。 设 MaxSize = M，只可能出现两种情况：

4.3.4 循环队列的完整实现（竞赛写法）

把方案一写成竞赛写法：一个全局数组 int q[M]，两个全局下标 head / tail， 再加 empty()、full()、size()、push()、pop() 这些自由函数 —— 不写 class、不写模板，所有结论一眼可见，抄到考卷上也最快。 三种判满方案各自的判空判满条件，一并写进了代码开头的注释里。

// circular_queue.cpp —— 循环队列的竞赛写法：全局数组 + 自由函数（方案一判满）
//
// 【三种判满方案，考试三种都考，结论先摆在这里】
//   方案一（本文件采用）：牺牲一个存储单元
//       full : (tail + 1) % M == head        empty : head == tail
//       容量为 M 的数组最多存 M-1 个元素；不额外开变量、判断最短，408 考研的默认方案。
//   方案二：另外维护一个计数器 cnt
//       full : cnt == M                      empty : cnt == 0
//       一个格子都不浪费，cnt 还能直接当成"元素个数"返回；代价是每次出入队都要同步维护它。
//   方案三：另外维护一个标志位 tag（最近一次操作：入队 1 / 出队 0）
//       full : head == tail && tag == 1      empty : head == tail && tag == 0
//       同样零浪费，但判空判满的条件最长，最容易写错。
//   三种方案共用的两条结论（本文件的 push / pop 就是照这个写的）：
//     * 入队 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 指向队尾元素的下一个空位（下一个新元素要落下的位置）

bool empty() { return head == tail; }             // 判空：初始 head == tail == 0
bool full()  { return (tail + 1) % M == head; }   // ★ 判满：tail 再走一步就撞上 head
int  size()  { return (tail - head + M) % M; }    // ★ 元素个数：先加 M 再取模
int  cap()   { return M - 1; }                    // 方案一下的真实可用容量

bool push(int x) {              // 入队 O(1)：一次赋值 + 一次取模
    if (full()) return false;
    q[tail] = x;
    tail = (tail + 1) % M;      // 前进一格，走到 M 就绕回 0
    return true;
}

int pop() {                     // 出队 O(1)：只动 head，一个元素都不搬移
    if (empty()) return -1;     // 竞赛约定：元素都是非负时，用 -1 表示"队列为空"
    int v = q[head];
    head = (head + 1) % M;      // 一样要取模
    return v;
}

int front() { return q[head]; }                  // 取队头（调用前自己保证非空）
int back()  { return q[(tail - 1 + M) % M]; }    // 队尾就是 tail 的前一格，也要 +M 防负数

void print(const char *tag) {
    printf("%s  [size=%d/%d head=%d tail=%d] ", tag, size(), cap(), head, tail);
    if (empty()) { printf("(空)\n"); return; }
    // ★ 遍历循环队列不能写 for (i = head; i < tail; ++i)：绕过圈时 tail < head，一次都不执行。
    //   正确姿势是"先算个数，再走环"：
    for (int i = 0, k = head; i < size(); ++i, k = (k + 1) % M)
        printf("%d%s", q[k], i + 1 == size() ? "" : " -> ");
    printf("\n");
}

int main() {
    print("初始");
    for (int i = 1; i <= 5; ++i) push(i * i);
    print("入队 1,4,9,16,25");

    printf("再入队 36 结果: %s\n", push(36) ? "成功" : "失败(队满)");

    printf("出队 -> %d\n", pop());
    printf("出队 -> %d\n", pop());
    print("出队两次");

    push(36); push(49);                         // tail 从 5 绕回 0，亲眼看一下取模
    print("再入队 36,49");

    printf("队头 = %d，队尾 = %d\n", front(), back());

    printf("全部出队: ");
    while (!empty()) printf("%d ", pop());
    printf("\n清空后 empty=%s\n", empty() ? "true" : "false");

    for (int i = 1; i <= 3; ++i) push(i * 100); // 绕圈之后再入队，验证下标依然正确
    print("再入队 100,200,300");
    return 0;
}

下面这个动画把循环队列的入队、出队、判满、判空连起来演示。 请重点观察 rear 从下标 7 绕回 0 的那一步，以及此时长度公式发生了什么变化。

4.3.5 循环队列的复杂度

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)」？逐条看指针动作：

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

• 带头结点：入队、出队都只改 next 指针，从不修改 front 本身（除非释放头结点）。空队列和非空队列的代码路径完全一致，不需要特判。
• 不带头结点：入队第一个元素时要同时改 front 和 rear；出队最后一个元素时要把 rear 拉回 NULL。每个操作都要写「如果队列为空 / 只剩一个元素」的分支，代码丑且容易漏。

4.4.2 带头结点链队列的完整实现（竞赛写法）

竞赛写法同样只有三样东西：struct Node 描述结点长什么样，两个全局指针 head / tail （就是上面说的 front / rear，竞赛里更习惯这么写）， 再加 push() / pop() 两个自由函数。 特别注意 pop() 里标了 ★★ 的那一行 —— 出队后队列变空时 tail 必须指回头结点。

// link_queue.cpp —— 带头结点的链队列：struct Node + 全局 head/tail + 自由函数
//
// 先把约定记牢，代码就是这四句话的直译：
//   * head 始终指向头结点（哨兵，不存有效数据），真正的队头元素是 head->nxt；
//   * tail 始终指向队尾结点，也就是最后一个真正的数据结点；
//   * 空队列 ⇔ head == tail，此时两者都指向头结点，且头结点的 nxt 为 NULL；
//   * 元素个数额外用 cnt 维护，把求长度从 O(n) 降到 O(1)。
//
// 【命名对照】竞赛里习惯写 head / tail，教材里写 front / rear，指的是同一对指针：
//   head = front（指向头结点），tail = rear（指向队尾结点）。
//
// 为什么入队、出队都是 O(1)？（对比第 02 讲的单链表：那里插入删除要先按位查找前驱）
//   * 入队只改 tail->nxt 和 tail 两个指针，tail 是现成的，不用从头遍历找尾 → O(1)；
//   * 出队只改 head->nxt，head 也是现成的，不用遍历找前驱 → O(1)。
//   一句话：用两个指针（head/tail）换掉了单链表里的两次遍历。
//
// 竞赛里不写析构、不回收结点：程序结束操作系统一并回收（本文件只为讲清指针动作）。
#include <bits/stdc++.h>
using namespace std;

struct Node {                 // 结点：数据域 + 指针域
    int   val;
    Node *nxt;
    Node(int v = 0, Node *n = nullptr) : val(v), nxt(n) {}   // 构造函数可留可去
};

Node *head;    // 头结点（哨兵）
Node *tail;    // 队尾结点
int   cnt;     // 元素个数

void initQueue() {             // 初始化：head 与 tail 同时指向新造的头结点
    head = new Node();         // 头结点不存数据，只用来把"空队列"与"非空队列"两条路径合并成一条
    tail = head;
    cnt  = 0;
}

bool empty() { return head == tail; }     // 也可以写 head->nxt == nullptr，两者等价
int  size()  { return cnt; }

void push(int x) {             // 入队：接在队尾，两步指针操作
    Node *s = new Node(x);
    tail->nxt = s;             // ① 原尾结点的 nxt 指向新结点
    tail = s;                  // ② tail 后移，成为新的队尾
    ++cnt;
    // 空队列入队走的是同一条路径：head->nxt 原本是 nullptr，接上 s 即可，
    // 全程不需要动 head —— 这就是头结点"消灭 if 分支"的价值。
}

bool pop(int &out) {           // 出队：摘掉 head->nxt，两步指针操作
    if (empty()) return false; // 出队前必判空，否则 head->nxt->val 就是空指针解引用
    Node *p = head->nxt;       // p 才是真正的队头结点
    out = p->val;
    head->nxt = p->nxt;        // 跨过 p —— 必须先摘链，再 delete p，顺序不能颠倒
    if (tail == p) tail = head;   // ★★ 经典坑：出队后队列变空，tail 必须指回头结点！
                                  //    漏了这一行，tail 就悬空（指向刚被 delete 的内存），
                                  //    下一次 push 里的 tail->nxt = s 就是 use-after-free。
    delete p;
    --cnt;
    return true;
}

int front() { return head->nxt->val; }   // 取队头：只读不删（调用前自己保证非空）
int back()  { return tail->val; }        // 取队尾：tail 就指着它

void print(const char *tag) {
    printf("%s  [size=%d] head -> ", tag, cnt);
    for (Node *p = head->nxt; p; p = p->nxt) printf("%d -> ", p->val);
    printf("NULL\n");
}

int main() {
    initQueue();
    print("空队列");

    for (int i = 1; i <= 5; ++i) push(i * 10);
    print("入队 10..50");
    printf("队头 = %d，队尾 = %d\n", front(), back());

    int v;
    pop(v); printf("出队 %d\n", v); print("出队一次");
    pop(v); printf("出队 %d\n", v); print("出队两次");

    printf("全部出队: ");
    while (!empty()) { pop(v); printf("%d ", v); }
    printf("\n清空后 empty=%s，head == tail ? %s\n",
           empty() ? "true" : "false", head == tail ? "是（tail 已归位）" : "否");
    print("空队列的样子");

    // 空队列再入队：验证刚才出队清空时 tail 已经归位，这里不会踩悬空指针
    push(999);
    print("清空后再入队 999");
    pop(v);
    printf("再出队 %d，程序正常结束（没有悬空指针）\n", v);
    return 0;
}

4.4.3 经典易错点：只有一个元素的队列出队后，rear（= tail）去哪了？

这是链队列最著名的坑，没有之一。假设队列里只剩下一个元素，此时 front->next == rear（队头结点就是队尾结点，按下面代码的命名即 head->next == tail）。 执行出队时，如果只写：

// link_queue_bug.cpp —— 反例：出队时忘记处理 rear（=tail），导致队尾指针悬空
// 本程序可以正常编译运行，但它演示的 popBuggy() 是一个【逻辑错误】的实现：
// 出队最后一个元素后 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 empty() { return head == nullptr; }

void push(int x) {
    Node* s = new Node{x, nullptr};
    if (empty()) head = tail = s;
    else { tail->next = s; tail = s; }
}

// ✗ 错误写法：只把 head（=front）后移，忘了处理 tail（=rear）
bool popBuggy(int& out) {
    if (empty()) 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();
    push(42);                             // 队列中只有 1 个元素：head == tail

    int v = 0;
    popBuggy(v);
    cout << "出队 -> " << v << "\n";
    cout << "出队后 head == nullptr ? " << (head == nullptr ? "是" : "否") << "\n";
    cout << "出队后 tail == nullptr ? " << (tail == nullptr ? "是" : "否") << "\n";
    cout << "结论：队列逻辑上已空，但 tail 仍然悬空。\n";
    cout << "      此处若执行 push(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 empty() { return head == tail; }

void push(int x) {
    Node* s = new Node{x, nullptr};
    tail->next = s;
    tail = s;
    ++cnt;
}

// 写法一：先判断"p 是不是队尾"，是则把 tail 拉回头结点（推荐，语义最清晰）
bool popV1(int& out) {
    if (empty()) 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 popV2(int& out) {
    if (empty()) 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 = " << (empty() ? "true" : "false") << "\n";

    push(7);                                     // 队列中只有 1 个元素
    cout << "入队 7 后 Empty = " << (empty() ? "true" : "false") << "\n";

    int v = 0;
    popV1(v);
    cout << "出队 -> " << v << "  Empty = " << (empty() ? "true" : "false")
         << "  head==tail ? " << (head == tail ? "是（tail 已归位）" : "否（tail 悬空！）") << "\n";

    // 出队清空后再入队，验证 tail 依然有效
    push(100); push(200);
    cout << "再次入队 100,200 后依次出队: ";
    while (popV2(v)) cout << v << " ";
    cout << "\nEmpty = " << (empty() ? "true" : "false") << "\n";

    push(999);                                   // 空队列再入队，验证 head/tail 一致性
    popV1(v);
    cout << "再入队 999 出队 -> " << v << "，程序正常结束（没有悬空指针）\n";

    delete head;                                 // 释放头结点
    return 0;
}

4.4.4 不带头结点的链队列对比

教材上也能见到不带头结点的写法。它的结构更「紧凑」（省一个结点）， 但每一个操作都要多写分支。下表把两者的差异摆在一起：

// link_queue_no_head.cpp —— 不带头结点的链队列：两处特判一个都不能少
// 和 link_queue.cpp（带头结点）对比着看最清楚：
//   省下了 1 个头结点的空间，代价是 push / pop 里各多出一条 if 分支。
//   这正是"哨兵不解决算法问题，它只消灭 if 分支"的反面例证。
#include <bits/stdc++.h>
using namespace std;

struct Node {                 // 结点：数据域 + 指针域
    int   val;
    Node *nxt;
    Node(int v = 0, Node *n = nullptr) : val(v), nxt(n) {}
};

Node *head = nullptr;   // 没有哨兵，head 直接指向队头元素
Node *tail = nullptr;   // tail 直接指向队尾元素
int   cnt  = 0;         // 元素个数，免得求长度时还要遍历

bool empty() { return head == nullptr; }   // 也可以写 tail == nullptr：两者同进同退
int  size()  { return cnt; }

void push(int x) {          // 入队：空 / 非空两条路径
    Node *s = new Node(x);
    if (empty()) {          // ★ 特判一：往空队列里入队，两个指针都要改
        head = tail = s;
    } else {                //   非空时才是常规的"接在队尾"
        tail->nxt = s;
        tail = s;
    }
    ++cnt;
}

bool pop(int &out) {        // 出队：只剩一个元素时要特判
    if (empty()) return false;
    Node *p = head;         // 不带头结点，队头结点就是 head 自己
    out = p->val;
    if (head == tail) {     // ★ 特判二：队列里只剩一个元素，出队后队列就空了
        head = tail = nullptr;   //   两个指针必须同时置空；
                                 //   只把 head 后移（变成 nullptr）而不管 tail，tail 就悬空了
    } else {
        head = head->nxt;   //   还有多个元素，只需 head 后移
    }
    delete p;
    --cnt;
    return true;
}

int front() { return head->val; }   // 取队头，只读不删（调用前自己保证非空）

void print(const char *tag) {
    printf("%s  [size=%d] ", tag, cnt);
    if (empty()) { printf("(空)\n"); return; }
    for (Node *p = head; p; p = p->nxt) printf("%d -> ", p->val);
    printf("NULL\n");
}

int main() {
    print("空队列");
    push(1); print("入队 1");       // 走的是"空队列入队"的特判分支
    push(2); print("入队 2");       // 走的是常规分支

    int v;
    pop(v); printf("出队 %d\n", v); print("出队一次");
    pop(v); printf("出队 %d\n", v); print("出队两次（已空）");
    printf("出队后 head == nullptr && tail == nullptr ? %s\n",
           (head == nullptr && tail == nullptr) ? "是（两指针同时置空，tail 没悬空）"
                                               : "否（tail 悬空了！）");

    printf("空队列再入队 8：\n");
    push(8); print("");             // 出队清空后再入队，验证特判一依旧正确
    pop(v);
    printf("出队 -> %d，empty=%s\n", v, empty() ? "true" : "false");
    return 0;
}

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.1 受限双端队列：输入受限与输出受限

考试里还常考两种「半限制」的 deque，它们的出题点在于判断某个输出序列是否合法：

4.5.2 用 C++ std::deque 演示四种操作

std::deque 是 STL 里真正实现了双端队列的容器（也是 std::queue 与 std::stack 的默认底层容器）。 它允许在两端 O(1) 插入删除，同时还支持随机访问 d[i] —— 这一点比 std::queue 强得多。

// std_deque_demo.cpp —— std::deque 的四种操作与"栈/队列特例"验证
#include <iostream>
#include <deque>
#include <string>
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 的默认底层容器 —— 一套经过充分测试的双端队列代码，加一层薄薄的接口限制，就同时得到了栈和队列。

4.6 循环队列 vs 链队列：工程上怎么选

两种实现都能做到 O(1) 的入队出队，那实际项目里到底用哪个？先看对比表：

4.7 应用一：银行排队模拟（离散事件模拟）

前面都是「结构怎么实现」，从这一节开始讲「结构能干什么」。 队列最有代表性的应用，就是模拟排队系统。这是本章的重头戏，请一定动手跑一遍代码。

4.7.1 问题描述：一个窗口，随机到达的顾客

场景：银行只开 1 个窗口。顾客陆续到来，到达的时间间隔是随机的； 每个顾客办理业务所需的服务时长也是随机的。窗口同一时刻只能服务一个人， 后面来的人自动排到队尾。我们想回答这些问题：

• 顾客平均要等多久？（平均等待时间）
• 最倒霉的那位等了多久？（最大等待时间）
• 队伍最长排到多少人？（队列最大长度，决定要不要加隔离带）
• 窗口有多长时间是空闲的？（空闲率，决定要不要裁撤窗口）

这些问题没有解析公式（除非假设到达服从泊松分布、服务时间服从指数分布，才轮到排队论出场）， 但用计算机模拟却非常简单 —— 这就是离散事件模拟 discrete event simulation。

4.7.2 离散事件模拟的三个核心概念

事件 event

让系统状态发生突变的那一刻。本问题里只有两类：顾客到达 arrival 与 服务完成 departure。 注意时间只在事件发生的瞬间才「跳一下」，中间那些没人来也没人走的「空档」不需要逐秒模拟。

时间推进 time advance

把仿真时钟直接拨到「下一个事件发生的时间」，而不是 t = t + 1 逐个时间单位试探。 本问题里下一个事件时间 = min(下一位顾客的到达时刻, 当前顾客的服务完成时刻)。

状态 state

用来描述系统此刻处境的全部变量：clock（当前时刻）、queue（排队的顾客）、 serverBusy（窗口是否占用）、各项累计统计量。

4.7.3 手工推演：模拟的判定规则

在写代码之前，我们先人工模拟 4 个顾客，把规则彻底搞明白。 设 MaxSize 足够大，数据如下（时间单位：分钟）：

推演的关键只有一条判定规则，请务必记住：

队列在模拟里的作用非常明确：它存放「已经到达但还没轮到自己」的顾客。 顾客到达时 push 进队列；窗口空闲时从队列 front 取出下一位 pop。 FIFO 保证了「先到先服务 first come first served，FCFS」，也就是现实中的排队公平性 —— 这正是队列不可替代的地方：换任何别的结构，都会破坏先来后到。

4.7.4 随机数：到达间隔与服务时长怎么来

模拟离不开随机数。C++11 提供了 <random> 库，写法如下：

// random_interval.cpp —— 用 C++11 <random> 生成"随机间隔"与"随机服务时长"
#include <iostream>
#include <random>
using namespace std;

int main() {
    // 固定种子 → 每次运行结果完全一致，方便调试与对照答案；
    // 换成 random_device{}() 就能得到真正的随机结果。
    mt19937 gen(20240501u);

    // 到达间隔：1~6 分钟均匀分布（平均 3.5 分钟来一位）
    uniform_int_distribution<int> arriveGap(1, 6);
    // 服务时长：2~8 分钟均匀分布（平均 5 分钟服务一位）
    uniform_int_distribution<int> serveTime(2, 8);

    cout << "前 10 位顾客的到达间隔与到达时刻：\n";
    int t = 0;
    for (int i = 0; i < 10; ++i) {
        int gap = arriveGap(gen);
        t += gap;
        cout << "顾客" << i + 1 << ": 间隔=" << gap
             << " 到达时刻=" << t
             << " 预计服务=" << serveTime(gen) << " 分钟\n";
    }

    cout << "\n注意：平均到达间隔 " << 3.5
         << " 分钟 < 平均服务时长 5 分钟，\n"
         << "      说明顾客来得比服务得快 → 队伍会越排越长（系统不稳定）。\n";
    return 0;
}

4.7.5 版本 A：用 std::queue 实现完整模拟

这是推荐写法：短、清晰、不容易出错。程序会输出每一位顾客的到达 / 开始服务 / 等待 / 离开时刻， 最后给出统计指标。

// bank_sim_stl.cpp —— 银行单窗口排队模拟（std::queue 版本，可直接编译运行）
#include <iostream>
#include <queue>
#include <random>
#include <iomanip>
#include <algorithm>      // std::max
using namespace std;

struct Customer {
    int id;         // 编号
    int arrive;     // 到达时刻
    int serve;      // 需要服务多久
    int start;      // 实际开始服务时刻
    int leave;      // 离开时刻
    int wait() const { return start - arrive; }
};

struct Stat {
    double totalWait = 0;   // 累计等待时间
    int    maxWait   = 0;   // 最大等待时间
    int    maxQueue  = 0;   // 队列最大长度
    int    idleTime  = 0;   // 窗口空闲总时长
    int    done      = 0;   // 已完成人数
};

// 单窗口模拟：n 位顾客，窗口 1 个
Stat simulate(int n, unsigned seed) {
    mt19937 gen(seed);
    uniform_int_distribution<int> arriveGap(1, 6);   // 到达间隔 1~6
    uniform_int_distribution<int> serveTime(2, 8);   // 服务时长 2~8

    queue<Customer> q;          // ★ 队列：已到达但还没轮到服务的顾客
    Stat st;
    int clock = 0;              // 仿真时钟
    int freeAt = 0;             // 窗口变为空闲的时刻（0 表示一开始就空闲）
    int nextArrive = arriveGap(gen);

    for (int i = 1; i <= n; ++i) {
        clock = nextArrive;                     // 时间推进到「下一位顾客到达」
        q.push(Customer{i, clock, serveTime(gen), 0, 0});
        if ((int)q.size() > st.maxQueue) st.maxQueue = (int)q.size();

        // 只要窗口在 clock 之前（或正好）已经空出来，队头就可以立刻开始服务。
        // 服务一个人耗时 > 0，所以每来一位新顾客，最多只会消耗掉队头一个人。
        while (!q.empty() && freeAt <= clock) {
            Customer w = q.front(); q.pop();
            w.start = max(w.arrive, freeAt);    // ★ 核心公式：max(到达时刻, 窗口空闲时刻)
            if (w.start > freeAt) st.idleTime += w.start - freeAt;  // 窗口空等了一段时间
            w.leave = w.start + w.serve;
            freeAt  = w.leave;                  // 窗口下一次空闲的时刻
            st.totalWait += w.wait();
            if (w.wait() > st.maxWait) st.maxWait = w.wait();
            ++st.done;
            cout << "顾客" << setw(3) << w.id
                 << "  到达 " << setw(3) << w.arrive
                 << "  服务 " << w.serve << " 分钟"
                 << "  开始 " << setw(3) << w.start
                 << "  等待 " << setw(3) << w.wait()
                 << "  离开 " << setw(3) << w.leave << "\n";
        }

        nextArrive = clock + arriveGap(gen);     // 下一位顾客的到达时刻
    }

    // 收尾：不会再有新顾客了，把队列里剩下的人依次服务完
    while (!q.empty()) {
        Customer w = q.front(); q.pop();
        w.start = max(w.arrive, freeAt);
        if (w.start > freeAt) st.idleTime += w.start - freeAt;
        w.leave = w.start + w.serve;
        freeAt  = w.leave;
        st.totalWait += w.wait();
        if (w.wait() > st.maxWait) st.maxWait = w.wait();
        ++st.done;
        cout << "顾客" << setw(3) << w.id
             << "  到达 " << setw(3) << w.arrive
             << "  服务 " << w.serve << " 分钟"
             << "  开始 " << setw(3) << w.start
             << "  等待 " << setw(3) << w.wait()
             << "  离开 " << setw(3) << w.leave << "\n";
    }

    cout << "\n================ 模拟结果 ================\n";
    cout << fixed << setprecision(2);
    cout << "顾客总数       : " << n << "\n";
    cout << "总耗时         : " << freeAt << " 分钟\n";
    cout << "平均等待时间   : " << (n ? st.totalWait / n : 0.0) << " 分钟\n";
    cout << "最大等待时间   : " << st.maxWait << " 分钟\n";
    cout << "队列最大长度   : " << st.maxQueue << " 人\n";
    cout << "窗口空闲时长   : " << st.idleTime << " 分钟（占用率 "
         << (freeAt ? 100.0 * (freeAt - st.idleTime) / freeAt : 0.0) << "%）\n";
    return st;
}

int main() {
    cout << "=========== 银行单窗口排队模拟（20 位顾客）===========\n";
    Stat a = simulate(20, 20240501u);

    cout << "\n=========== 换一批随机数据（200 位顾客）===========\n";
    Stat b = simulate(200, 987654321u);

    cout << "\n=========== 对比分析 ============\n";
    cout << "20 人  : 平均等待 " << a.totalWait / 20 << " 分钟, 最长队伍 " << a.maxQueue << " 人\n";
    cout << "200 人 : 平均等待 " << b.totalWait / 200 << " 分钟, 最长队伍 " << b.maxQueue << " 人\n";
    cout << "结论：样本越大统计越稳定，队伍长度随人数增加而变长，说明服务能力不足。\n";
    return 0;
}

4.7.6 版本 B：把 std::queue 换成自写循环队列

版本 A 用的是 STL。但考试要你自己写，工程上也常需要把队列控制在自己手里 （比如要统计队列最大长度、要不加锁、要固定内存）。 下面这份程序把我们自己写的循环队列（全局数组 + head/tail + 自由函数）塞进模拟器， 并且顺便把「窗口数」做成参数 —— 于是它同时也是一个多窗口模拟器。

// bank_sim_circular.cpp —— 自写循环队列版银行排队模拟（1~N 个窗口）
// 竞赛写法：全局状态 + 自由函数，没有 class / template；
//           队列就是"全局数组 + head/tail 取模"，与 circular_queue.cpp 完全一致。
#include <bits/stdc++.h>
using namespace std;

/* ---------- 1. 自写的循环队列（方案一：牺牲一个存储单元判满） ---------- */
const int QM = 4096;              // 队列容量：真实最多排 QM-1 = 4095 人

struct Customer {                 // 一位顾客：编号、到达、服务时长、开始服务、离开
    int id, arrive, serve, start, leave;
};

Customer q[QM];
int qHead = 0, qTail = 0;         // qHead 指向队头元素，qTail 指向队尾的下一个空位

bool qEmpty() { return qHead == qTail; }              // 判空
bool qFull()  { return (qTail + 1) % QM == qHead; }   // ★ 判满：qTail 再走一步就撞上 qHead
int  qSize()  { return (qTail - qHead + QM) % QM; }   // ★ 元素个数：先加 QM 再取模

bool qPush(const Customer &c) {   // 入队 O(1)
    if (qFull()) return false;
    q[qTail] = c;
    qTail = (qTail + 1) % QM;     // 取模推进，走到 QM 就绕回 0
    return true;
}
bool qPop(Customer &out) {        // 出队 O(1)
    if (qEmpty()) return false;
    out = q[qHead];
    qHead = (qHead + 1) % QM;
    return true;
}
void qClear() { qHead = qTail = 0; }

int waitOf(const Customer &c) { return c.start - c.arrive; }   // 等待 = 开始 - 到达

/* ---------- 2. 全局统计量：模拟过程中一路累加 ---------- */
double totalWait, totalIdle;      // 累计等待时间 / 累计窗口空闲时间
int    maxWait, maxQueue;         // 最大单人等待 / 队列长度峰值
int    served, rejected;          // 已服务人数 / 因队满被拒人数
int    finishTime;                // 全部服务完的总耗时

const int MAXW = 16;              // 最多支持 16 个窗口
int freeAt[MAXW];                 // 每个窗口下一次空闲的时刻

/* ---------- 3. 模拟器：windows 个窗口，共享一条等待队列 ---------- */
void simulate(int n, unsigned seed, int windows, bool verbose) {
    if (windows > MAXW) windows = MAXW;

    // ---- 先把全局状态清零，保证多次调用互不影响 ----
    qClear();
    totalWait = totalIdle = 0;
    maxWait = maxQueue = served = rejected = 0;
    for (int k = 0; k < windows; ++k) freeAt[k] = 0;

    mt19937 gen(seed);                                 // 固定种子 → 结果可复现，方便对答案
    uniform_int_distribution<int> arriveGap(1, 6);     // 到达间隔 1~6 分钟
    uniform_int_distribution<int> serveTime(2, 8);     // 服务时长 2~8 分钟

    int clock = 0, nextArrive = arriveGap(gen);

    for (int i = 1; i <= n; ++i) {
        clock = nextArrive;                            // 时间推进到下一位顾客到达
        Customer c{i, clock, serveTime(gen), 0, 0};
        if (!qPush(c)) {                               // ★ 循环队列满了就拒绝服务
            ++rejected;
            if (verbose) printf("队列已满，顾客 %d 被拒绝\n", i);
            continue;
        }
        // ★ 队列峰值必须在"入队之后"统计：队伍只会在两次到达之间变短，出队时统计会漏掉峰值
        if (qSize() > maxQueue) maxQueue = qSize();

        // 有空闲窗口就持续叫号：每次挑"最早空闲"的那个窗口，保证负载均衡
        while (!qEmpty()) {
            int best = -1;
            for (int k = 0; k < windows; ++k)
                if (freeAt[k] <= clock && (best == -1 || freeAt[k] < freeAt[best])) best = k;
            if (best == -1) break;                     // 所有窗口都忙 → 继续排队

            Customer w;
            qPop(w);
            w.start = max(w.arrive, freeAt[best]);     // ★★ 核心公式：开始 = max(到达, 窗口空闲)
            if (w.start > freeAt[best]) totalIdle += w.start - freeAt[best];   // 窗口白等了一段
            w.leave = w.start + w.serve;               // 离开 = 开始 + 服务时长
            freeAt[best] = w.leave;                    // 该窗口下一次空闲的时刻
            totalWait += waitOf(w);                    // 等待 = 开始 - 到达（不是"离开 - 到达"）
            if (waitOf(w) > maxWait) maxWait = waitOf(w);
            ++served;

            if (verbose)
                printf("顾客%3d  窗口%d  到达 %3d  开始 %3d  等待 %3d  离开 %3d\n",
                       w.id, best + 1, w.arrive, w.start, waitOf(w), w.leave);
        }
        nextArrive = clock + arriveGap(gen);           // 下一位顾客的到达时刻
    }

    // 收尾：不会再有新顾客了，把队列里剩下的人依次服务完
    while (!qEmpty()) {
        int best = 0;
        for (int k = 1; k < windows; ++k) if (freeAt[k] < freeAt[best]) best = k;
        Customer w;
        qPop(w);
        w.start = max(w.arrive, freeAt[best]);
        if (w.start > freeAt[best]) totalIdle += w.start - freeAt[best];
        w.leave = w.start + w.serve;
        freeAt[best] = w.leave;
        totalWait += waitOf(w);
        if (waitOf(w) > maxWait) maxWait = waitOf(w);
        ++served;
    }

    finishTime = 0;
    for (int k = 0; k < windows; ++k) finishTime = max(finishTime, freeAt[k]);
}

int main() {
    printf("=========== 单窗口详细过程（前 15 位顾客）===========\n");
    simulate(15, 20240501u, 1, true);

    printf("\n=========== 单窗口 vs 多窗口：各模拟 300 位顾客 ===========\n");
    printf("窗口数   平均等待(分)   最大等待(分)   队列峰值   总耗时(分)   占用率(%%)\n");
    for (int w = 1; w <= 4; ++w) {
        simulate(300, 20240501u, w, false);
        double busy = finishTime
                    ? 100.0 * (w * (double)finishTime - totalIdle) / (w * (double)finishTime)
                    : 0.0;
        printf("%4d %14.2f %14d %11d %12d %12.2f\n",
               w, served ? totalWait / served : 0.0, maxWait, maxQueue, finishTime, busy);
    }

    printf("\n结论：\n");
    printf("  1) 窗口越多，平均等待与最大等待下降得非常快（近似成反比）；\n");
    printf("  2) 但窗口占用率同时下降 —— 加到一定数量后，再加窗口就是浪费人力；\n");
    printf("  3) 用这个模拟器反复调整参数，就能找到「等待可接受 && 占用率不过低」的平衡点。\n");
    return 0;
}

下面这个动画把模拟过程可视化了：顾客从右边不断到达并排队，窗口服务完一个人就立刻叫下一位。 留意左侧统计面板里平均等待、最大等待与队列峰值的变化。

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 <iostream>
#include <queue>
#include <iomanip>
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();                    // std::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";
    return 0;
}

4.9 应用三：二叉树的层序遍历（第 07 讲预热）

树的遍历有四种：前序、中序、后序、层序。前三种靠递归（也就是栈）就能写出来， 唯独层序不行 —— 因为层序要求「先访问完第 1 层，再访问第 2 层……同一层里从左到右」， 这个顺序和「入队顺序完全一致」，所以它天生就是队列的地盘。

为什么队列天然适合层序？因为 BFS 式的访问有一个关键性质： 先被访问的结点，它的孩子也一定先被访问。 当我们访问结点 x 时把它的左右孩子依次入队， 队列里就自动形成了「上一层剩余结点在前、下一层结点在后」的隐含分层结构。 每次从队头取一个结点，就相当于按层、从左到右地推进。

// binary_tree_level_order.cpp —— 用队列实现二叉树的层序遍历（含按层分组统计）
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct TreeNode {
    int       val;
    TreeNode* left;
    TreeNode* right;
    explicit 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.10 应用四：迷宫最短路径（BFS + 队列）

第 03 讲我们用栈解过迷宫：一条路走到黑，撞墙就回退。它能找到一条通路， 但找不到最短的那条。要想求最短路径，就得换成队列 + BFS（广度优先搜索 breadth-first search）。

4.10.1 为什么 BFS 得到的必然是最短路径？

关键在一个词：逐层扩展。BFS 从起点出发，先把「走 1 步能到」的所有格子全部访问完， 再访问「走 2 步能到」的，再访问「走 3 步能到」的……

注意前提条件：BFS 求最短路只对边权相等（无权图 / 每条边代价都是 1）的图成立。 如果每条路的代价不同（比如有的地面走得快、有的泥地走得慢），就得用 Dijkstra（第 09 讲）。 这也是考试常考的辨析点。

4.10.2 栈求迷宫 vs 队列求迷宫：一张表看清差别

下面这个动画把 BFS 逐圈铺开的过程完整演示出来，可以看到队列里始终只有「当前层 + 下一层」的格子。

// maze_bfs.cpp —— BFS + 队列求迷宫最短路径（无权图最短路标准模板）
#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;

const int R = 5, C = 7;
int maze[R][C] = {
    {0, 0, 0, 0, 1, 0, 0},
    {0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0, 0, 0},   // 0 可走，1 是墙
};

struct Point { int r, c; };

int main() {
    Point start{0, 0}, target{2, 6};

    vector<vector<int>> dist(R, vector<int>(C, -1));   // -1 表示未访问
    vector<vector<Point>> parent(R, vector<Point>(C, Point{-1, -1}));
    const int dr[4] = {-1, 1, 0, 0};                   // 上 下 左 右
    const int dc[4] = {0, 0, -1, 1};

    queue<Point> q;                                    // ★ 队列：BFS 的边界
    q.push(start);
    dist[start.r][start.c] = 0;                        // 起点距离为 0

    while (!q.empty()) {
        Point cur = q.front(); q.pop();                // 取出队头 = 按距离从小到大扩展
        // 这里不做"遇到终点就 break"的提前退出，为的是把完整距离场打出来观察；
        // 实际做题时加上 if (cur == target) break; 可以省掉后半程的搜索。

        for (int k = 0; k < 4; ++k) {
            int nr = cur.r + dr[k], nc = cur.c + dc[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;  // 越界
            if (maze[nr][nc] == 1) continue;                        // 撞墙
            if (dist[nr][nc] != -1) continue;                       // 已访问（第一次访问即最短）
            dist[nr][nc] = dist[cur.r][cur.c] + 1;                  // 距离 = 上一层 + 1
            parent[nr][nc] = cur;                                   // 记录前驱，用于回溯路径
            q.push(Point{nr, nc});
        }
    }

    cout << "========== BFS 距离场（. 表示从起点不可达）==========\n";
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (maze[i][j] == 1) cout << "  #";
            else if (dist[i][j] < 0) cout << "  .";
            else printf("%3d", dist[i][j]);
        }
        cout << "\n";
    }

    if (dist[target.r][target.c] < 0) {
        cout << "\n起点到终点不可达！\n";
        return 0;
    }

    cout << "\n最短路径长度 = " << dist[target.r][target.c] << " 步\n";

    // 从终点沿 parent 反向回溯到起点，再反过来输出
    vector<Point> path;
    for (Point p = target; p.r != -1; p = parent[p.r][p.c]) path.push_back(p);
    cout << "最短路径（起点 → 终点）: ";
    for (int i = (int)path.size() - 1; i >= 0; --i) {
        cout << "(" << path[i].r << "," << path[i].c << ")";
        if (i) cout << " -> ";
    }
    cout << "\n";

    cout << "\n========== 可视化（* 是路径，# 是墙，. 是空地）==========\n";
    vector<string> grid(R, string(C, '.'));
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            if (maze[i][j] == 1) grid[i][j] = '#';
    for (size_t i = 0; i < path.size(); ++i) grid[path[i].r][path[i].c] = '*';
    grid[start.r][start.c] = 'S';
    grid[target.r][target.c] = 'T';
    for (int i = 0; i < R; ++i) cout << "  " << grid[i] << "\n";

    cout << "\n结论：队列的 FIFO 保证了「距离小的先出队」，所以第一次到达终点时\n";
    cout << "      走过的步数一定最少 —— 这就是 BFS 求无权图最短路的原理。\n";
    return 0;
}

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. 队列里的数值严格递减（新元素入队前，把所有比它小的队尾元素全部弹走）。

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

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

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

// sliding_window_max.cpp —— 单调队列 O(n) 求滑动窗口最大值
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>      // std::max
#include <climits>       // LLONG_MIN
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) {
            while (!dq.empty() && pre[dq.back()] >= pre[i]) dq.pop_back();  // 维护前缀和最小
            dq.push_back(i);
            if (dq.front() < i - k) dq.pop_front();
            if (i > 0) best = max(best, pre[i] - pre[dq.front()]);
        }
        cout << "变形：长度不超过 " << k << " 的最大子数组和 = " << best << "\n";
    }

    cout << "\n复杂度对比：暴力 O(nk) = " << a.size() * k
         << " 次比较；单调队列 O(n)，每个下标最多进出各一次。\n";
    return 0;
}

4.12 应用六：队列还在这些地方出现

队列是计算机科学里出现频率最高的数据结构之一。前面五个应用都能写出代码， 下面这四个场景你现在只需要「知道它在用队列」，等学到对应章节时自然水到渠成。

4.13 C++ STL 中的队列家族

C++ 标准库提供了三个和队列直接相关的容器适配器 / 容器。它们的关系是： std::queue 和 std::stack 都是「容器适配器」，默认底层容器就是 std::deque； 而 std::priority_queue 是「带优先级的队列」，底层是堆。

std::queue 接口速查

std::deque 接口速查

std::priority_queue：优先队列（第 11 讲预热）

优先队列出队的不是「最早进来的」，而是「优先级最高的」。 它不满足 FIFO，所以严格来说不是队列，只是名字里带 queue。 底层用二叉堆 binary heap 实现，入队出队都是 O(log n)， 取堆顶是 O(1) —— 这正是第 11 讲堆排序与第 09 讲 Dijkstra 优化的基础工具。

STL 队列的六个常见坑

// stl_queue_family.cpp —— std::queue / std::deque / std::priority_queue 三大件实操
#include <iostream>
#include <queue>
#include <deque>
#include <vector>
#include <string>
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. std::queue：普通 FIFO ================= */
    cout << "=========== 1. std::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. std::deque：两端都能动 ================= */
    cout << "=========== 2. std::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. std::priority_queue：堆 ================= */
    cout << "=========== 3. std::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;
}

4.14 工程视角：队列是系统的「缓冲层」

4.12 节只把队列出现的地方「点名」了一遍。这一节换个更高的角度：把队列当成系统里的 缓冲层 buffer —— 上游按自己的节奏塞数据，下游按自己的速度取走，队列吸收两边的速度差。 看清这一层你会发现：操作系统、网络协议栈、消息中间件、垃圾回收器，都在反复实现同一个东西 —— 一块有界的、会阻塞的、先进先出的环形内存。

4.14.1 消息队列：解耦、异步、削峰，同一副骨架

Kafka、RabbitMQ、RocketMQ、Redis 的 List，名字与协议都不同，骨架却完全一样： 生产者把消息追加到队尾，消费者从队头取走并确认。4.12 只说它们「是队列」， 这里要说清：队列凭什么值得单独做成一个中间件 —— 因为它同时给了三个别处拿不到的能力。

1. 解耦：下单服务只写一条「订单已创建」，不需要知道后面还有库存、积分、通知三个下游； 明天要加一个风控消费者，上游一行代码都不用改 —— 生产者与消费者互相不认识，接口越小，依赖越少。
2. 异步：同步调三个下游、每个 100 ms，用户要等 300 ms；改成写一条消息（约 5 ms）就返回， 主链路立刻降到 5 ms。那 295 ms 没有消失，只是搬到了队列另一侧。
3. 削峰填谷：这是最值钱的一条。秒杀入口 10 万 QPS 打进来，数据库只扛得住 5 万 QPS， 队列把「瞬时高峰」摊平成「持续输出」，让下游按自己舒服的速度跑。

削峰可以算得很具体：生产者每秒写 10 万条、消费者每秒只取 5 万条， 积压就以每秒 5 万条的速度线性增长。持续 10 分钟的秒杀会堆下 5 万 × 600 = 3000 万条消息，按每条 1 KB 算是 30 GB； 消费者要追平还得再花 600 秒。用户看到的「下单成功」与后台真正扣库存之间，隔了十分钟。

Kafka 凭什么每秒吞几十万条？因为它对磁盘只做顺序追加写：机械盘顺序写能到 100 MB/s 以上， 按 1 KB 一条算就是每秒 10 万条，随机写却只有一两百次每秒。

4.14.2 削峰的代价：积压、重复、顺序性与消费者滞后

队列不是免费的午餐：把流量塞进队列，等于把「下游处理不过来」从立刻报错换成延后暴露。 四个指标必须盯住，它们恰好是队列的四项代价：

• 积压 backlog：那 3000 万条并没有消失，只是在排队。队列不会让系统变快， 只会把故障从「请求超时」变成「结果迟到十分钟」。
• 消费者滞后 lag：lag = 最新消息位点 − 消费者已提交位点，即「还欠多少条」。 100 万条 lag 在 5 万条/秒的消费能力下要 20 秒消化。运维盯的就是这条曲线： lag 只涨不跌，说明消费者死了或被下游拖住 —— 这时入口成功率反而一切正常。
• 消息重复：网络抖动、消费者重启、确认丢失都会导致「至少一次 at-least-once」投递， 同一条消息被处理两遍。所以消费者必须幂等：用订单号去重，或把「余额加 1」改成「余额置为 1」。
• 顺序性：为了吞吐，队列会被拆成多个分区并行消费，全局顺序随之消失。 要保序，就得让同一个业务键（如同一订单号）落进同一个分区，且只被一个线程处理 —— 吞吐与顺序天生互斥。

4.14.3 生产者-消费者与有界缓冲区：满和空两个条件

把前面所有系统的内核剥出来，剩下的就是「生产者-消费者 + 有界缓冲区」这一个模型。 为什么强调有界？因为内存有限，无界队列只是把 OOM 推迟到更难排查的时刻。 有界之后缓冲区只剩三种状态：空、满、既不空也不满，两个角色各自只需盯住一个条件：

• 队列满时生产者不能再写 —— 必须阻塞（或按策略丢弃最老的数据）；
• 队列空时消费者不能读 —— 必须阻塞等待；
• 一次 push 成功要唤醒等数据的消费者，一次 pop 成功要唤醒等空位的生产者。

这正是「信号量 / 条件变量」的经典用法：empty（空位数，初值等于容量）与 full（数据个数，初值 0） 两个信号量，生产者先 P(empty) 再写、写完 V(full)，消费者反过来。 两个 P 写反就是著名的死锁：两边各占一把锁互等。用条件变量时同理，等待要写成 while (条件不满足) wait(); —— 被唤醒时条件可能已被别人抢走。

图里这两种状态值得盯住：空和满时 head == tail 都成立，必须再维护一个 count （或像 4.3.2 节那样牺牲一个存储单元）。下面这段代码用 count 方案， 把「写满后 push 失败、读空后 pop 失败」真跑一遍：

// ring_buffer.cpp —— 有界环形缓冲区：生产者-消费者模型的最小可用内核
// 结构：数组 + head/tail + count；判空判满只比计数，入队出队都是 O(1)。
// 满则 push 返回 false（真实系统在此阻塞生产者），空则 pop 返回 false（阻塞消费者）。
#include <cstdio>

const int CAP = 8;                 // 缓冲区容量：真实系统里取 1024、4096 这类 2 的幂

int buf[CAP];                      // 环形缓冲区本体：连续内存，缓存友好
int head  = 0;                     // 队头：消费者取数据的位置
int tail  = 0;                     // 队尾：生产者写数据的位置
int count = 0;                     // ★ 当前元素个数：区分「空」与「满」的唯一依据

long long pushOk = 0, pushFail = 0;   // 生产者侧：成功 / 因满被拒
long long popOk  = 0, popFail  = 0;   // 消费者侧：成功 / 因空被拒

bool isFull()  { return count == CAP; }   // 判满：计数器方案，不浪费存储单元
bool isEmpty() { return count == 0; }     // 判空

bool push(int x) {                        // 生产者调用
    if (isFull()) { ++pushFail; return false; }
    buf[tail] = x;
    tail = (tail + 1) % CAP;              // ★ 循环队列的取模回绕
    ++count; ++pushOk;
    return true;
}

bool pop(int& x) {                        // 消费者调用
    if (isEmpty()) { ++popFail; return false; }
    x = buf[head];
    head = (head + 1) % CAP;
    --count; ++popOk;
    return true;
}

void show(const char* tag) {
    printf("      %-10s count=%d  head=%d  tail=%d  %s%s\n", tag, count, head, tail,
           isFull() ? "[满]" : "", isEmpty() ? "[空]" : "");
}

int main() {
    printf("缓冲区容量 CAP = %d\n\n", CAP);

    printf("--- 第 1 步：生产者连写 10 条，容量只有 %d ---\n", CAP);
    for (int i = 1; i <= 10; ++i) {
        int v = i * 10;
        if (push(v)) printf("push(%3d) 成功\n", v);
        else         printf("push(%3d) 失败  <- 缓冲区已满，生产者必须阻塞或丢弃\n", v);
    }
    show("写满后");
    printf("      注意 head 与 tail 都回到了 0：只有 count 能区分空与满\n\n");

    printf("--- 第 2 步：消费者取走 3 条，腾出 3 个空位 ---\n");
    int v = 0;
    for (int i = 0; i < 3; ++i)
        if (pop(v)) printf("pop() -> %3d\n", v);

    printf("\n--- 第 3 步：生产者再写 3 条，这次全部成功 ---\n");
    for (int i = 1; i <= 3; ++i) {
        v = 100 + i * 10;
        int t0 = tail;
        bool ok = push(v);              // 先写，再打印：printf 的实参求值顺序是未指定的
        printf("push(%3d) %s   tail: %d -> %d\n", v, ok ? "成功" : "失败", t0, tail);
    }

    printf("\n--- 第 4 步：把剩下的 8 条全部取空，顺序仍是 FIFO ---\n");
    while (pop(v)) printf("pop() -> %3d\n", v);
    show("取空后");
    printf("      最后一次 pop 返回 false：缓冲区已空，消费者必须阻塞等待\n\n");

    printf("=== 统计 ===\n");
    printf("push 成功 %lld 次，因满失败 %lld 次\n", pushOk, pushFail);
    printf("pop  成功 %lld 次，因空失败 %lld 次\n", popOk, popFail);
    printf("守恒检查：push 成功 - pop 成功 = %lld，当前 count = %d —— %s\n",
           pushOk - popOk, count, (pushOk - popOk == count) ? "一致" : "不一致");
    return 0;
}

在 g++ -std=c++17 下编译运行，关键输出如下：

push( 90) 失败  <- 缓冲区已满，生产者必须阻塞或丢弃
      写满后  count=8  head=0  tail=0  [满]
      注意 head 与 tail 都回到了 0：只有 count 能区分空与满
push(110) 成功   tail: 0 -> 1
      取空后  count=0  head=3  tail=3  [空]
push 成功 11 次，因满失败 2 次
pop  成功 11 次，因空失败 1 次

三处细节值得停下来看：①写满 8 条后 head 与 tail 都等于 0， 只靠「两下标相等」判空判满在这里会彻底懵掉 —— 这就是 4.3.2 节「计数器方案」存在的理由； ②第 3 步的 3 次写入从 0 绕回 3，没有假溢出，这正是 4.3 节循环队列的全部价值； ③取空后的顺序是 40 50 60 70 80 110 120 130，绕一圈仍严格 FIFO —— FIFO 是语义承诺，取模回绕只是实现手段。

push / pop 只报成败、不擅自决定（同样是「满」，Kafka 攒批重发、Redis 的 BRPOP 阻塞等待、 网关丢掉最老请求返回 503），这正是缓冲区能适配各种策略的前提。

4.14.4 操作系统：三张队列和一个电梯

① 就绪队列与等待队列。工程上要分清两条队列：就绪队列 ready queue 里全是「只等 CPU」的进程， 调度器每次挑一个上 CPU；等待队列 wait queue 里的进程在等磁盘 IO、等锁，CPU 空着也不会被选中。 磁盘中断到来时，内核把进程从等待队列搬到就绪队列 —— 这个「搬家」就是唤醒（V 操作）。

就绪队列若严格 FIFO，就是先来先服务 FCFS。它公平，却有个致命毛病叫护航效应： 一个要跑 10 秒的编译任务排在前面，后面 100 个只要 10 ms 的交互式任务就得一起干等 10 秒。 于是有了多级反馈队列 MLFQ：就绪队列拆成多层，优先级从高到低、时间片从短到长 （如 8 ms / 16 ms / 32 ms）；新进程进最高层，一个时间片没跑完就降一层，高层全空才轮到低层； 再加一条防饿死规则：定时把所有进程提升回最高层（老化 aging）。 结论：单一 FIFO 不够用，真实调度是「多条队列 + 优先级 + 老化」的组合。

② IO 请求队列与电梯算法。一块磁盘同一时刻只能服务一个请求，于是排队顺序直接决定性能。 按 FIFO，磁头会在盘面上来回横跳：一次机械寻道约 10 ms，一次内存访问约 100 ns，差了 5 个数量级， 1000 个随机请求光是寻道就要 10 秒。电梯算法 SCAN 把请求按磁道号排序，磁头只朝一个方向扫 （像电梯只往上开），到最远处再折返；总行程从「1000 次随机跳跃」变成「大约走完全程一遍」， 随机 IO 被改造成近似顺序 IO —— 和 Kafka 靠顺序写提速是同一个道理。SSTF 每次挑最近的请求， 效果像优先队列（第 11 讲的堆可以 O(log n) 取最小），代价是最远的磁道会饿死。 SSD 没有寻道，IO 队列换成了「按优先级与权重分配带宽」（Linux 的 blk-mq）。

③ 打印假脱机 spooling。4.12 说过打印任务要排队，工程上这条队列叫假脱机（SPOOL）。 为什么不干脆在内存里排个队？因为任务可能要等几小时才轮到，10 个用户各提交 50 MB 文档， 就是 500 MB 内存被「排队」占着。所以 spooling 的做法是：作业本体先完整写到磁盘的 spool 目录 （Windows 下是 System32\spool\PRINTERS），内存里只留一条「作业控制块」队列，指向磁盘文件。 这是一条极重要的工程惯例：队列元素要小，真实数据放别处，队列里只存句柄或指针。 第 02 讲的链表结点演示过这个思路；Kafka 的内存索引、网卡的接收描述符，都是同一个套路。

4.14.5 网络：从端口队列到缓冲区膨胀

① 端口出队列与缓冲区膨胀 bufferbloat。路由器和交换机的每个端口都有一条出队列： 多个入口的包要往同一个出口走，出口线速固定，排队无法避免。为了让「不丢包」好看， 家用路由器的缓冲区被做得很大（几百 KB 到几 MB），但大缓冲区会把延迟顶上去： 家宽上行 10 Mbps 约合 1.25 MB/s，2 MB 的缓冲区排满就是 1.6 秒的额外延迟 —— 游戏 ping 从 20 ms 变成 1600 ms 就是这么来的。更麻烦的是 TCP 靠丢包判断拥塞：缓冲区太大、 包迟迟不丢，发送方以为链路很空而继续加速，队列越排越长。解法是主动队列管理 AQM（CoDel、FQ-CoDel）： 延迟超过 5 ms 就主动丢包或打 ECN 标记，让 TCP 早点减速。缓冲区换来的吞吐，是用延迟买的。

② TCP 滑动窗口本质上也是一条队列。发送方维护「已发送但未确认」的窗口，接收方维护 「已收到但未交给应用」的接收缓冲区；窗口为 0 时发送方必须停下等待，这就是标准的「队列满则阻塞」， SO_RCVBUF 设的就是这条队列的容量。选小了吞吐上不去，选大了延迟变高， 所以现代内核干脆让窗口自动调节。

③ 网卡环形缓冲区：4.3 节的循环队列跑在硬件旁边。网卡通过 DMA 把收到的包写进内存里 一圈固定大小的描述符，驱动从另一头取走。为什么非用循环队列不可？因为网卡是硬件， 它不能调用 malloc，只能操作地址和大小都固定的内存：用普通数组，tail 几秒钟就撞墙 （4.2 节的假溢出）；取模回绕之后，一块 4096 个描述符 × 2 KB ≈ 8 MB 的内存就能永远转下去。 8 MB 听着不少，可 10 Gbps 线速就是 1.25 GB/s，只够缓冲 6.4 ms —— 环的大小直接决定网卡能容忍多长的中断延迟。ethtool -g eth0 看的就是这个环， ifconfig 里的 RX dropped / overrun 说的正是「环满了，包被硬件丢掉了」。

4.14.6 BFS 的另一面：人脉、爬虫与垃圾回收

4.10 和 4.12 里的 BFS 都还在网格图与图的遍历范围内。跳出课本看，还有三类系统其实是同一件事： 一层一层向外扩散，引擎就是队列。

• N 度人脉：「你和某人的最短关系链」就是无权图最短路，标准解法是 BFS。 Facebook 在 2016 年公布过一个数字：当时 15.9 亿用户之间的平均距离是 3.57 跳， BFS 只需扩三四层。真实系统不会从你一个人 BFS 到全网，而是用双向 BFS： 两边各扩一层，中途相遇即最短 —— 正是 4.10 迷宫最短路在大图上的工程版本。
• 爬虫的待抓队列 frontier：爬虫就是「取 URL → 下载 → 解析出新 URL → 入队」。 与课本 BFS 最大的差别在去重：网页互相链接，不判重队列会无限膨胀， 所以每个 URL 入队前都要查一次「抓过没有」—— 靠的正是第 10 讲的哈希表。 工业爬虫还会按域名把队列拆成多条并限速（礼貌性 polite）。
• 垃圾回收的标记阶段：主流 GC 用三色标记 —— 白（没访问过）、灰（发现未扫描）、黑（扫描完）。 灰色对象的集合就是一条队列：从 GC Roots 入队，每出队一个灰对象，就把它引用的白对象染灰并入队。 用队列还是用栈，决定了这是 BFS 还是 DFS：标记结果一样，但队列版本的灰色集合规模正比于图的宽度， 栈版本却可能把一整条路径压住。这就是 G1、Go 都用标记队列而非递归的原因。

4.14.7 工程选型对比表：五种「队列」，五个现实维度

最后把本节的结构压成一张表，比的是工程师真正会卡的五个现实维度（不是复杂度，那些都是 O(1)）。

选型心法只有三问：容量能不能在创建时定死？有几个人同时碰它？要不要按优先级取？ 能定死 + 单生产单消费者 → 无锁环形队列；必须动态增长 → 链队列（补上容量上限和拒绝策略）； 要按优先级取 → 优先队列（第 11 讲的堆是底座）；两端都要动 → 双端队列。

4.15 本章小结

应用的统一视角

把本章五个应用串起来看，队列在不同场景里扮演的角色其实只有三种：

1. 「缓冲」角色：银行排队、打印任务、消息队列、I/O 缓冲池。 队列把「生产者」和「消费者」的节奏解耦，起到削峰填谷的作用。
2. 「分层推进」角色：迷宫 BFS、图的 BFS、二叉树层序遍历。 队列保证了「近的先处理」，于是天然形成一层一层向外扩展的顺序。
3. 「维护候选集」角色：单调队列求滑动窗口最大值。 队列不再只是被动排队，而是主动淘汰「不可能成为答案」的元素，把复杂度从 O(nk) 压到 O(n)。

看清这三种角色，以后再遇到新问题，你会先问自己：这里的「先来后到」是什么？有没有「近的先处理」的需求？ 有没有元素已经彻底没用了、可以安全丢掉？ 只要有一个答案是肯定的，队列大概率就是你要找的工具。

4.16 易错点清单与考点

高频易错点汇总

考点提示

4.17 自测题

先自己动笔算，再展开答案对照。四道题分别覆盖概念、公式、指针与算法设计。

第 1 题（循环队列公式）

一个循环队列存放在数组 data[0..9] 中（MaxSize = 10）， 采用「牺牲一个存储单元」判满。当前 front = 7、rear = 3。请回答：

1. 队列中有多少个元素？
2. 队列是空、是满，还是既不为空也不为满？
3. 最多还能再入队几个元素？
4. 若连续出队 3 个元素，front 变成多少？

第 2 题（假溢出辨析）

某同学用数组 data[0..7] 实现队列，front 指向队头元素、rear 指向队尾元素的下一个位置， 判满条件是 rear == MaxSize，判空条件是 front == rear。 他说：「我的队列最多只能存 8 个元素，存满后出队一个再入队一个完全没问题。」请指出他错在哪里，并给出两种正确的修改方案。

第 3 题（链队列指针）

带头结点的链队列中，front 指向头结点，rear 指向队尾结点，队列中当前只有一个元素。 请写出出队操作的完整代码（含判空），并说明为什么不能省略其中的某一行。

// q3_answer.cpp —— 第 3 题参考答案：带头结点链队列的出队操作（含最小验证）
// 竞赛写法：全局 head / tail + 自由函数；struct 只用来描述结点。
// 【命名对照】head = front（头结点），tail = rear（队尾结点），同一对指针换个名字。
#include <bits/stdc++.h>
using namespace std;

struct Node { int data; Node* next; };   // 结点：数据域 + 指针域，保留 struct

Node* head;   // 指向头结点（哨兵）
Node* tail;   // 指向队尾结点

void initQueue() { head = tail = new Node{0, nullptr}; }
bool empty() { return head == tail; }

void enQueue(int x) {
    Node* s = new Node{x, nullptr};
    tail->next = s;
    tail = s;
}

bool deQueue(int& x) {
    if (head == tail) return false;     // 1. 判空：空队列直接返回 false
    Node* p = head->next;               // 2. p 指向真正的队头结点
    x = p->data;                        // 3. 取值
    head->next = p->next;               // 4. 摘链：必须先接好再释放
    if (tail == p) tail = head;         // 5. ★ 出队的是最后一个元素：tail 必须归位
    delete p;                           // 6. 释放结点
    return true;
}

int main() {
    initQueue();
    enQueue(7);                         // 队列中只有一个元素

    int v = 0;
    deQueue(v);
    cout << "出队 -> " << v << "\n";
    cout << "出队后 head == tail ? " << (head == tail ? "是（tail 已归位）" : "否（tail 悬空！）") << "\n";

    enQueue(100); enQueue(200);         // 再次入队，验证 tail 依然有效
    cout << "再次出队: ";
    while (deQueue(v)) cout << v << " ";
    cout << "\n程序正常结束：没有悬空指针，没有内存越界。\n";

    delete head;                        // 释放头结点
    return 0;
}

第 4 题（算法设计：单调队列）

给定数组 a = [2, 1, 4, 5, 3, 7]，窗口大小 k = 3。 请手工写出用单调队列求每个窗口最大值的完整过程（每步的队列内容 + 输出）， 并说明为什么该算法的时间复杂度是 O(n) 而不是 O(nk)。