【信奥业余科普】C++ 的奇妙之旅 | 23：主动限制的艺术——栈（stack）与队列（queue）
上一篇文章我们介绍了 vector 动态数组。vector 支持末尾追加、下标随机访问、中间插入删除等操作，功能非常灵活。
既然 vector 已经足够通用，为什么 STL 中还要专门提供 stack（栈）和 queue（队列）？
这就引出了软件工程中一个重要的设计思想：主动限制权限。在”撤销操作”或”排队处理”等场景中，过于自由的接口反而容易导致数据被意外修改。如果从接口层面关闭随机访问，只允许数据按固定规则进出，代码的意图会更清晰，出错的可能性也更低。
往期回顾：
一、 深入本质：什么是容器适配器？
在介绍用法之前，先澄清一个设计概念。在 STL 中，stack 和 queue 并不属于独立的基础”容器（Containers）”，而是被归类为 “容器适配器（Container Adapters）”。
什么是适配器？简单来说就是”套壳”。 stack 和 queue 底层并没有自己实现内存管理逻辑，而是直接复用了一个现成的容器（默认是 deque，双端队列）。然后，适配器将底层容器上的下标访问 []、中间插入等接口全部隐藏掉，只暴露出符合自身规则的少量操作。
1.1 套壳的具体方式：接口转发
适配器内部的实现非常直接——每个对外暴露的方法，本质上只是调用了底层容器的某个对应方法，自己几乎不做额外的计算。
stack 的接口转发：
| stack 对外方法 | 实际调用的底层容器方法 | 说明 |
|---|---|---|
s.push(x) | c.push_back(x) | 往底层容器的末尾追加元素 |
s.pop() | c.pop_back() | 删除底层容器的最后一个元素 |
s.top() | c.back() | 读取底层容器的最后一个元素 |
s.size() | c.size() | 直接转发 |
s.empty() | c.empty() | 直接转发 |
可以看到，stack 把底层容器的”尾部”当作”栈顶”。所有操作都集中在尾部，自然就实现了后进先出的规则。至于底层容器本身支持的 push_front()、operator[] 等方法，stack 不转发也不暴露，外部代码无法调用，因此也就无法破坏栈的规则。
queue 的接口转发：
| queue 对外方法 | 实际调用的底层容器方法 | 说明 |
|---|---|---|
q.push(x) | c.push_back(x) | 往末尾追加（入队） |
q.pop() | c.pop_front() | 删除第一个元素（出队） |
q.front() | c.front() | 读取第一个元素 |
q.back() | c.back() | 读取最后一个元素 |
queue 的入队操作在尾部（push_back），出队操作在头部（pop_front），两端配合，实现了先进先出。
1.2 为什么默认用 deque 而不是 vector？
既然 stack 只用到了尾部操作，用 vector 做底层似乎也可以。事实上，C++ 标准确实允许你手动指定底层容器：
1
std::stack<int, std::vector<int>> s; // 用 vector 作为底层
但默认选择 deque 是有原因的：
queue需要头部删除（pop_front）：vector不支持高效的头部删除（需要把后面的元素逐个前移，时间复杂度 $O(n)$），而deque的头尾操作都是 $O(1)$。为了让stack和queue使用统一的默认底层容器，标准选择了deque。deque无需整体搬迁：vector扩容时需要把所有数据拷贝到新内存（参见第 22 篇的扩容机制）。deque采用分段存储的方式（内部维护多个固定大小的小数组块），扩容时只需新增一个块，已有数据不需要移动。
理解了这种”通过隐藏接口来实现专项功能”的设计后，再来看它们的具体规则就很自然了。
二、 栈（stack）：后进先出（LIFO）
stack 的核心规则是 LIFO（Last In, First Out，后进先出）。
可以把 stack 想象成一摞叠起来的盘子：新盘子只能放在最上面（压栈），取盘子时也只能从最顶上拿（出栈），无法从中间抽取。
我们在第 18 篇介绍的”函数调用栈（Call Stack）”，底层用的就是这种数据结构：最后被调用的函数，最先执行完毕并退栈。
2.1 基本操作演示
在 C++ 中使用 stack 需要引入头文件 <stack>：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
// 压栈操作 (push)：将元素放入栈顶
s.push(10);
s.push(20);
s.push(30);
// 此时栈内的状态（从顶到底）：30, 20, 10
// 查看当前有多少个元素
std::cout << "当前栈大小：" << s.size() << std::endl;
while (!s.empty()) { // 只要栈不为空就继续循环
// 第一步：查看栈顶元素 (top)
int current_top = s.top();
std::cout << "取出栈顶元素：" << current_top << std::endl;
// 第二步：将栈顶元素弹出删除 (pop)
s.pop();
}
return 0;
}
2.2 注意事项：pop() 不返回值
这里需要注意 C++ 与许多其他语言的一个重要区别：C++ STL 的 pop() 不返回被弹出的元素（返回类型为 void）。
在其他语言中，你可能习惯用 int value = s.pop(); 一行代码同时完成”读取并弹出”。但 C++ 出于异常安全性的考虑，将读取和删除设计为两步独立操作：
- 先通过
s.top()读取栈顶元素的值（不删除）。 - 再调用
s.pop()将栈顶元素删除。
三、 队列（queue）：先进先出（FIFO）
queue 的核心规则是 FIFO（First In, First Out，先进先出），类似食堂排队：新来的人排在队尾，只有队头的人才能离开。
新数据从队尾入队，处理时从队头出队。操作系统中多任务的调度，底层也是基于这种先来先服务的模型。
3.1 基本操作演示
使用 queue 需要引入头文件 <queue>：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <queue>
int main() {
std::queue<int> q;
// 入队操作 (push)：元素排到队尾
q.push(1);
q.push(2);
q.push(3);
// 此时队伍状态（从队头到队尾）：1, 2, 3
while (!q.empty()) {
// 第一步：查看队头元素 (front)
int current_front = q.front();
std::cout << "取出队头元素：" << current_front << std::endl;
// 第二步：将队头元素弹出删除 (pop)
q.pop();
}
return 0;
}
与栈一样，队列的 pop() 同样不返回值。必须先调用 q.front() 读取队头元素，再调用 q.pop() 将其删除。 (注：q.back() 可以查看队尾元素，但在实际解题中较少用到。)
四、 信奥中的典型应用场景
正因为接口被严格限制，stack 和 queue 在信奥竞赛中反而成为了构建核心算法的基础组件。
stack（栈）的典型场景：- 括号匹配：遇到左括号就压栈，遇到右括号就检查栈顶是否匹配，匹配则弹出。
- DFS（深度优先搜索）：利用栈的后进先出特性，实现”走到尽头再回退”的搜索逻辑。
queue（队列）的典型场景：- BFS（广度优先搜索）：例如求迷宫最短路径时，将新发现的节点按顺序入队，保证”先发现的先探索”的逐层扩展逻辑。
结语与下期预告
通过主动限制底层容器的接口，stack 和 queue 提供了意图清晰、不易误用的标准组件。相比用原生数组手动模拟栈和队列，它们从接口层面就杜绝了下标越界和随意插入的风险。
在本篇中，我们多次提到 stack 和 queue 底层默认使用的容器是 deque（双端队列），并且提到它能同时做到头尾操作 $O(1)$ 和下标随机访问 $O(1)$。这比 vector 灵活得多，但它的底层结构也更复杂。
下一篇文章，我们将深入 deque 的内部，拆解它独特的”分段连续存储”设计——理解了这个底层机制，也就真正看清了 stack 和 queue 脚下的地基是什么样的。
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
