第 51 章排队与叠盘子——stack 与 queue

🏗️ 前情回顾：第 52 章你学会了 vector——一个可以随意在末尾增减数据的动态数组。但有些场景不适合用 vector：比如"撤销操作"需要回到上一步（最近加的最先用），比如"打印队列"需要先来先服务（最早加的最先用）。这两种特殊顺序，各有专门的容器来高效处理——stack（栈）和 queue（队列）。

🎯 本章目标

学完这一章，你能：

理解 LIFO（后进先出）和 FIFO（先进先出）的区别
用 stack 的 push、pop、top、empty、size 操作
用 queue 的 push、pop、front、back、empty、size 操作
在合适的场景中选择 stack 或 queue 解决问题
了解 deque（双端队列）的基本概念

📖 故事引入

场景一：叠盘子

食堂阿姨洗好一摞盘子，一个一个往上叠。你来拿盘子的时候，拿的一定是最上面那个——也就是最后一个放上去的。

这就是**栈（stack）**的规则：后进先出（LIFO — Last In, First Out）。最后进去的，最先出来。

场景二：食堂排队打饭

中午下课，你冲进食堂排队。排在你前面的人先打到饭，排在你后面的人后打到饭。

这就是**队列（queue）**的规则：先进先出（FIFO — First In, First Out）。最早进去的，最早出来。

生活中有无数场景对应这两种规则。编程里也一样——选择正确的容器，代码会变得极其简洁。

🧱 知识讲解

51.1 stack：后进先出的"盘子堆"

stack 像一个只有顶部开口的盒子。你只能操作最顶上的元素。

cpp

#include <stack>       // stack 需要这个头文件
using namespace std;

stack<int> s;           // 声明一个存 int 的栈

s.push(10);             // 放入 10（在顶部）
s.push(20);             // 放入 20（新顶部）
s.push(30);             // 放入 30（新顶部）

// 此时栈从顶到底：30 → 20 → 10

cout << s.top() << endl;  // 查看顶部元素 → 30
cout << s.size() << endl; // 元素个数 → 3

s.pop();                   // 移除顶部元素（30 被拿走）
cout << s.top() << endl;   // 新顶部 → 20

cout << s.empty() << endl; // 判断是否为空 → 0（false，非空）

stack 的五个核心操作：

操作	含义	说明
`s.push(x)`	压栈	把 x 放到栈顶
`s.pop()`	弹栈	移除栈顶元素（无返回值）
`s.top()`	查看栈顶	返回栈顶元素的引用
`s.empty()`	判空	空返回 true，非空返回 false
`s.size()`	大小	返回元素个数

⚠️ pop() 没有返回值！如果你需要被弹出的值，先用 top() 取值，再 pop()。

51.2 stack 的经典应用

应用一：判断括号匹配

这是 stack 最经典的练习题。原理很简单：

遇到左括号 ( → 入栈
遇到右括号 ) → 检查栈顶是否有左括号，有就弹出一个，没有就说明不匹配

cpp

bool isBalanced(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') {
            st.push(c);
        } else if (c == ')') {
            if (st.empty()) return false;  // 多了右括号
            st.pop();
        }
    }
    return st.empty();  // 栈为空 → 全部匹配，否则多了左括号
}

应用二：模拟递归/回溯

许多递归问题可以用 stack 来模拟（避免递归爆栈）——走路走不通时"回退到上一步"，就是典型的栈行为。本章练习中你会见到。

51.3 queue：先进先出的"排队"

queue 是两端开口的管道——一头进，一头出。

cpp

#include <queue>       // queue 需要这个头文件
using namespace std;

queue<int> q;           // 声明一个存 int 的队列

q.push(10);             // 入队（从队尾）
q.push(20);
q.push(30);

// 此时队列从队首到队尾：10 → 20 → 30

cout << q.front() << endl;  // 查看队首 → 10
cout << q.back() << endl;   // 查看队尾 → 30
cout << q.size() << endl;   // 元素个数 → 3

q.pop();                     // 出队（移除队首 10）
cout << q.front() << endl;   // 新队首 → 20

queue 的六个核心操作：

操作	含义	说明
`q.push(x)`	入队	把 x 放到队尾
`q.pop()`	出队	移除队首元素（无返回值）
`q.front()`	查看队首	返回队首元素的引用
`q.back()`	查看队尾	返回队尾元素的引用
`q.empty()`	判空	空返回 true，非空返回 false
`q.size()`	大小	返回元素个数

和 stack 一样，pop() 也没有返回值——先用 front() 取值再 pop()。

51.4 queue 的经典应用

应用一：广度优先搜索（BFS）的骨架

这是 queue 在竞赛中最常见的用途——逐层扩展搜索范围：

cpp

queue<int> q;
q.push(start);           // 起点入队

while (!q.empty()) {
    int cur = q.front(); // 取出队首
    q.pop();

    // 处理 cur...
    // 把 cur 的"邻居"入队
    for (每个邻居 next) {
        q.push(next);
    }
}

这个骨架是 BFS 的核心，以后学图和搜索时会大量使用。

应用二：模拟排队系统

cpp

queue<string> line;          // 排队的人

line.push("小明");
line.push("小红");
line.push("小刚");

while (!line.empty()) {
    cout << line.front() << " 打完饭了" << endl;
    line.pop();              // 打完饭离开队伍
}
// 输出顺序：小明 → 小红 → 小刚（先来的先服务）

51.5 stack vs queue 对比

对比维度	stack	queue
规则	LIFO（后进先出）	FIFO（先进先出）
类比	叠盘子	排队
插入	`push(x)` 到顶部	`push(x)` 到队尾
查看	`top()` 看顶部	`front()` 看队首，`back()` 看队尾
删除	`pop()` 删顶部	`pop()` 删队首
典型用途	括号匹配、撤销操作、递归模拟	排队模拟、BFS

51.6 deque 简介：两头都能操作的双端队列

除了 stack 和 queue，STL 还有一个更灵活的容器——deque（double-ended queue，双端队列）。它两头都能插入和删除：

cpp

#include <deque>
deque<int> dq;

dq.push_back(1);     // 尾部插入
dq.push_front(2);    // 头部插入
dq.pop_back();       // 尾部删除
dq.pop_front();      // 头部删除

// 和 vector 一样支持下标访问
dq[0] = 42;

deque 用得不如 vector、stack、queue 频繁。现阶段了解它"两头都能操作"即可，需要时再查文档。

✋ 动手试试

试试 1：创建一个 stack<int>，依次压入 1、2、3、4、5，然后依次弹出并输出每个值。观察输出顺序——和压入顺序一样还是相反？

试试 2：同样创建 queue<int>，同样 1~5 入队，依次出队并输出。观察顺序——和 stack 有什么区别？

试试 3：写一个括号匹配程序，支持 ()、[]、{} 三种括号。输入一个字符串，判断括号是否匹配。

示例：

输入：{ [ ( ) ] }      →  匹配
输入：{ [ ( ] ) }      →  不匹配
输入：( ( ( ) )        →  不匹配

试试 4：用两个 stack 模拟一个 queue。也就是说，写一个结构体 MyQueue，内部用两个 stack，对外提供 push 和 pop（FIFO 行为）。

⚠️ 容易犯的错

错 1：pop() 前不检查 empty()

❌ stack<int> s; s.pop(); // s 是空的，pop() 行为未定义

✅ 操作前先判断 if (!s.empty()) { ... }

错 2：把 pop() 当成有返回值

❌ int x = s.pop(); // pop() 返回 void，不是弹出的值

✅ int x = s.top(); s.pop(); // 先取后弹

错 3：stack 和 queue 的操作名搞混

❌ stack<int> s; s.front(); // stack 没有 front()，只有 top()

✅ stack → top()，queue → front() 和 back()

错 4：用 stack 做 queue 的活（或反过来）

❌ 需要 FIFO 行为却用了 stack → 逻辑完全错误

✅ 先想清楚场景：后进先出 → stack；先进先出 → queue

📝 练习

基础题

1. 填空题

（1）stack 的规则是 ____（后进先出 / 先进先出），queue 的规则是 ____。

（2）查看 stack 顶部元素用 ____()，查看 queue 队首用 ____()，查看队尾用 ____()。

（3）pop() 操作 ____（有 / 没有）返回值。

（4）使用 stack 需要 #include \_\_\_\_，使用 queue 需要 #include \_\_\_\_。

2. 读代码写结果

cpp

stack<int> s;
s.push(1); s.push(2); s.push(3);
s.pop();
s.push(4);
while (!s.empty()) {
    cout << s.top() << " ";
    s.pop();
}

输出是什么？

提高题

3. 编程题 — 进制转换（栈版）

输入一个十进制整数 N，将其转换为二进制。用 stack 存储每一步的余数，利用"后进先出"的特性实现逆序输出。

示例：

输入：13
输出：1101

（提示：N % 2 得到余数入栈，N /= 2 继续，重复直到 N 为 0。最后依次弹栈输出。）

4. 编程题 — 约瑟夫问题（队列版）

N 个人围成一圈，从第 1 个人开始报数，报到 M 的人出列。下一个人继续从 1 报数，直到所有人都出列。用 queue 模拟这个过程。

（提示：把 1~N 入队。每次把队首的人移到队尾，重复 M-1 次；然后队首的人就是出列的人。输出出列顺序。）

挑战题

5. 编程题 — 后缀表达式求值

后缀表达式（逆波兰表示法）是一种不需要括号的表达式写法。例如 "3 4 + 5 *" 的意思是 (3 + 4) * 5 = 35。

规则：遇到数字入栈；遇到运算符，弹出两个数字计算，结果入栈。最后栈顶就是结果。

请实现后缀表达式求值程序。输入一个空格分隔的后缀表达式字符串（只有 +、-、*、/ 四种运算，操作数都是整数），输出计算结果。

输入：3 4 + 5 *       输出：35
输入：10 3 5 * +      输出：25

6. 编程题 — 滑动窗口最大值

给定一个整数数组和一个窗口大小 K，求每个窗口内的最大值。

输入第一行是数组长度 N 和窗口大小 K，第二行是 N 个整数。输出每个窗口的最大值，空格分隔。

（提示：用 deque 维护"可能成为最大值的候选元素"，保持 deque 递减。这就是经典的"单调队列"优化。）

🧠 本章小结

stack（栈）：后进先出 LIFO —— 叠盘子
    push(x)  top()  pop()  empty()  size()

queue（队列）：先进先出 FIFO —— 排队
    push(x)  front()  back()  pop()  empty()  size()

共同点：pop() 都没有返回值 → 先取值再弹

deque（双端队列）：两头都能操作
    push_back / push_front / pop_back / pop_front

选择规则：
    撤销、回溯、括号匹配 → stack
    排队模拟、BFS → queue

📝 配套练习

共7题。stack(3题: 括号/后缀/栈序列) + queue(2题: 约瑟夫/翻译) + 单调栈启蒙(1题) + deque(1题)。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1739	https://hydro.ac/p/luogu-P1739	stack、括号匹配
◆ 拓展	luogu-P1449	https://hydro.ac/p/luogu-P1449	stack、后缀表达式求值
◆ 拓展	luogu-P1996	https://hydro.ac/p/luogu-P1996	queue、约瑟夫环
◆ 拓展	luogu-P1160	https://hydro.ac/p/luogu-P1160	数组模拟链表、队列安排
◆ 拓展	luogu-P1540	https://hydro.ac/p/luogu-P1540	queue、机器翻译、FIFO
◆ 拓展	luogu-P4387	https://hydro.ac/p/luogu-P4387	stack、验证栈序列
◆ 拓展	luogu-P5788	https://hydro.ac/p/luogu-P5788	单调栈启蒙、下一个更大元素

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 6 道◆拓展题，覆盖不同变式和细节。

配套练习

共7题。stack(3题: 括号/后缀/栈序列) + queue(2题: 约瑟夫/翻译) + 单调栈启蒙(1题) + deque(1题)。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1739	https://hydro.ac/p/luogu-P1739	stack、括号匹配
◆ 拓展	luogu-P1449	https://hydro.ac/p/luogu-P1449	stack、后缀表达式求值
◆ 拓展	luogu-P1996	https://hydro.ac/p/luogu-P1996	queue、约瑟夫环
◆ 拓展	luogu-P1160	https://hydro.ac/p/luogu-P1160	数组模拟链表、队列安排
◆ 拓展	luogu-P1540	https://hydro.ac/p/luogu-P1540	queue、机器翻译、FIFO
◆ 拓展	luogu-P4387	https://hydro.ac/p/luogu-P4387	stack、验证栈序列
◆ 拓展	luogu-P5788	https://hydro.ac/p/luogu-P5788	单调栈启蒙、下一个更大元素

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 6 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我能说出 LIFO 和 FIFO 分别代表什么
[ ] 我会使用 stack 的 push / pop / top / empty / size
[ ] 我会使用 queue 的 push / pop / front / back / empty / size
[ ] 我知道 pop() 不返回值，要先 top()/front() 再 pop()
[ ] 我知道括号匹配是 stack 的经典应用
[ ] 我知道 BFS 骨架是 queue 的经典应用
[ ] 我了解 deque 双端都能操作

🚀 下章预告

到目前为止，你的程序一直在"内存"里干活——数据从键盘进来，结果往屏幕输出。但程序一关，什么痕迹都没留下。能不能把数据存进文件，下次打开还能读出来？下一章我们学习文件操作，让你的程序拥有"持久记忆"。

第 51 章 排队与叠盘子——stack 与 queue ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

51.1 stack：后进先出的"盘子堆" ​

51.2 stack 的经典应用 ​

51.3 queue：先进先出的"排队" ​

51.4 queue 的经典应用 ​

51.5 stack vs queue 对比 ​

51.6 deque 简介：两头都能操作的双端队列 ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1：pop() 前不检查 empty() ​

错 2：把 pop() 当成有返回值 ​

错 3：stack 和 queue 的操作名搞混 ​

错 4：用 stack 做 queue 的活（或反过来） ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​

🚀 下章预告 ​