Chapter 22: Stack
核心问题与阅读主线
std::stack 通过裁剪序列容器的公开接口,将底层序列收窄为严格的 LIFO 操作表面:语义约束归适配器,而存储布局、扩容代价与引用生命周期完全归底层容器。本章拆解接口转发模型、std::deque/std::vector/std::list 选型边界与状态路径。
全章共用代码样本(下文各节持续拆解)
本章的贯穿材料是一段括号匹配代码:程序只需保存“尚未匹配的左括号”,每逢右括号仅检查并移除最近压入的左括号,接口需求收敛为 push、top、pop、empty。
#include <stack>
#include <string>
bool balanced_parentheses(const std::string& input) {
std::stack<char> pending;
for (char ch : input) {
if (ch == '(') {
pending.push(ch);
} else if (ch == ')') {
if (pending.empty()) {
return false;
}
pending.pop();
}
}
return pending.empty();
}
这段代码全程不遍历 pending,也不访问栈底元素,只关心最后一个尚未匹配的左括号。
关键事实
std::stack 定义于 <stack>,属于 container adaptor,本身不管理内存与节点布局。依据 C++ 工作草案 stack.general 与 std::stack 参考页,默认底层容器为 std::deque<T>,任何提供 back()、push_back()、pop_back() 的序列容器均可替代;C++23 补充了 push_range 与 std::formatter 支持,C++26 进一步支持 constexpr。
22.1 LIFO 语义与容器适配器目标
LIFO 的工作定义是:任意时刻可访问和可移除的元素,始终是最近进入且尚未移除的元素。凡是“历史顺序存在,但当前动作只触碰最新状态”的问题都符合这一模型:
- 括号匹配:最新读到的左括号最先等待当前右括号闭合。
- 函数调用栈:最新进入的函数帧最先完成并返回。
- 操作撤销:最近一次提交的编辑动作最先回退。
std::stack<T, Container> 是一层薄适配器:它在内部持有受保护成员 Container c,屏蔽底层容器的索引、迭代、任意插入与擦除接口,只把后端动作映射为 LIFO 操作表面:
empty()/size()→ 转发至c.empty()/c.size()top()→ 转发至c.back()(返回栈顶引用)push()/emplace()→ 转发至c.push_back()/c.emplace_back()pop()→ 转发至c.pop_back()(销毁并移除栈顶)
下面的教学简化版展示了这一接口转发形状:
#include <cstddef>
#include <deque>
#include <utility>
template<class T, class Container = std::deque<T>>
class MiniStack {
public:
bool empty() const { return c_.empty(); }
std::size_t size() const { return c_.size(); }
T& top() { return c_.back(); }
const T& top() const { return c_.back(); }
void push(const T& value) { c_.push_back(value); }
void push(T&& value) { c_.push_back(std::move(value)); }
void pop() { c_.pop_back(); }
private:
Container c_;
};
回到贯穿代码:pending.push('(') 压入左括号;遇 ')' 先查 pending.empty() 拦截孤立右括号,再调用 pop() 闭合最近左括号,正对应“内层先闭合”的 LIFO 约束。
核心判断
std::stack 自己不发明节点布局也不接管分配,核心工程价值在于用类型接口封死非栈顶访问,防止后续维护误写出“读写中间元素后继续当栈用”的逻辑。
22.2 默认 deque 与可替换底层容器条件
std::stack 的第二个模板参数为底层容器类型,默认为 std::deque<T>,也可替换为 std::vector<T> 或 std::list<T>。判断容器是否适任,需依次核对两层条件:
- 标准接口条件:
Container::value_type与T一致,提供正常语义的back()、push_back()、pop_back(),并满足构造、empty()、size()、swap()等序列容器基础要求。 - 工程成本条件:后端增删的分配次数、扩容迁移行为、缓存局部性与引用稳定性匹配当前负载特征。
三种常用底层容器的取舍集中在存储布局与扩容路径:
| 底层容器 | 存储形状 | push 扩容与分配 | 局部性与引用稳定性 | 适用栈负载 |
|---|---|---|---|---|
std::deque<T> | 分段连续存储 | 按块分配,后端增长不触发全量搬移 | 局部性较好;跨 push/pop 保存栈顶引用仍需防栈顶移除失效 | 默认选择,适合大小波动、无需整段连续内存的栈 |
std::vector<T> | 单段连续存储 | 容量不足时整段重分配并移动或拷贝已有元素 | 缓存局部性最优;重分配会使所有旧引用与指针失效 | 上限可预估、可提前 reserve 且重视局部性的栈 |
std::list<T> | 双向链表节点 | 每次 push/pop 触发单节点独立分配或释放 | 局部性差、指针追踪明显;未删节点的地址与引用全程稳定 | 元素移动代价极高、必须保持节点地址稳定的场景 |
默认选用 std::deque<T> 的原因在于折中均衡:既规避了 std::vector 扩容时的整段迁移峰值,也免去了 std::list 逐节点堆分配和指针追踪的常态开销。
std::vector<int> 满足 back()、push_back()、pop_back(),可直接实例化 std::stack<int, std::vector<int>>。但 std::stack 不暴露 reserve(),预留容量需先构造底层 vector 再移动入栈:
#include <stack>
#include <utility>
#include <vector>
std::vector<int> storage;
storage.reserve(1024);
std::stack<int, std::vector<int>> history(std::move(storage));
边界与误区
容量策略归属底层容器而非 std::stack。即便预先 reserve 了底层 vector,后续 push() 超过预留容量仍会触发整段重分配,导致此前保存的 top() 引用或指针悬垂;任何底层容器下都不应跨修改操作长期缓存栈顶引用。
22.3 push、pop 与 top 的状态路径
push/emplace、top、pop 构成 LIFO 的最小状态循环——写入新栈顶、原地观察或修改栈顶、提交销毁栈顶:
| 操作 | 转发目标 | 核心行为与返回值 | 前置条件与失效/异常边界 |
|---|---|---|---|
push(v) | c.push_back(...) | 拷贝或移动已有元素到后端;返回 void | 若构造/扩容抛异常,异常安全级别由底层容器决定 |
emplace(args...) | c.emplace_back(...) | 将参数完美转发到底层容器后端原位构造;返回 void | 省去临时对象构造与移动;构造失败时栈状态取决于底层容器 |
top() | c.back() | 返回当前栈顶左值引用(T& 或 const T&) | 栈必须非空;后续 pop() 或底层扩容可使其失效 |
pop() | c.pop_back() | 销毁并移除当前栈顶;返回 void | 栈必须非空;不返回值,需在 pop() 前通过 top() 读取 |
push("parse") 先构造临时 std::string 再移动或拷贝入栈,emplace("evaluate") 则在底层容器后端原位构造,工程上按构造成本取舍:
#include <stack>
#include <string>
std::stack<std::string> calls;
calls.push("parse"); // 构造临时 string,再移动或拷贝进底层容器
calls.emplace("evaluate"); // 在底层容器后端直接原位构造 string
top() 返回引用意味着既可只读拷贝也可原地改写;而标准故意让 pop() 返回 void,是为了把“读取或拷贝栈顶值”与“移除栈顶”拆成两步——若在按值返回期间发生拷贝异常,栈顶尚未被销毁,异常边界更清晰:
#include <stack>
void update_top_demo() {
std::stack<int> values;
values.push(10);
values.push(20);
int latest = values.top(); // 拷贝当前值(latest == 20)
values.top() = 21; // 直接改写底层容器后端元素
}
int take_top(std::stack<int>& values) {
int result = values.top(); // 先读取(若拷贝抛异常,元素仍在栈中)
values.pop(); // 再移除(底层执行 c.pop_back())
return result;
}
贯穿代码中的右括号分支正体现了这组前置守卫:if (pending.empty()) return false; 将失败路径放在 pending.pop() 之前,确保多余右括号不会对空栈执行未定义操作。
排查顺序
- 空栈前提:调用
top()或pop()前是否已确认!empty()。 - 引用捕获:是否缓存了
top()返回的引用/指针,并在随后执行了push()或pop()。 - 异常边界:值提取与
pop()是否分离,避免读取失败导致元素丢失。 - 容器代价:当前
push/emplace是否会触发底层容器重分配、元素搬移或单节点堆分配。
22.4 iterator 封装边界与顺序语义
std::stack 刻意不提供 begin()、end()、下标访问或中间擦除,将“只操作栈顶”固化为编译期约束。在 balanced_parentheses 中,算法只判别最近左括号能否闭合;若出现以下需求,说明已超出 LIFO 语义,应改用 std::vector 或 std::deque:
- 收集并输出所有未匹配括号的下标位置。
- 按从栈底到栈顶的顺序遍历或检索历史状态。
- 从容器中间擦除元素或随机改写非栈顶元素。
标准定义中底层容器 c 是 protected 成员,派生类在语法上确实可以将其公开:
#include <stack>
#include <vector>
template<class T>
class ExposedStack : public std::stack<T, std::vector<T>> {
public:
using std::stack<T, std::vector<T>>::c;
};
边界与误区
一旦业务代码依赖 c.begin()、c[0] 或中间擦除,它实际依赖的是底层序列容器的全局顺序而非栈语义,继续保留 stack 命名只会误导维护者。标准库为 std::stack 提供的关系比较、push_range 与 std::formatter 都是围绕底层容器补齐的外围能力,并未放开中间位置访问。
若仅用于调试或日志快照,可按值传参复制副本并循环读取弹出,按“从顶到底”输出而不改动原始栈:
#include <iostream>
#include <stack>
void print_from_top(std::stack<int> values) {
while (!values.empty()) {
std::cout << values.top() << '\n';
values.pop();
}
}
按值传参的代价是完整复制底层容器元素;若元素数量大、复制成本高或需要频繁遍历展示,改用原生序列容器更直接。
22.5 工程使用场景
只要问题可归纳为“压入当前上下文、仅查看或消费最近一条、完成后弹出”,std::stack 就能准确收敛操作表面:
| 工程场景 | 栈顶保存的状态 | 选用 std::stack 的收益 | 超出 LIFO 边界的转折点 |
|---|---|---|---|
| 多括号/语法嵌套匹配 | 待匹配的期望闭合符或作用域 | 强制内层先于外层闭合,分支简洁 | 需汇总全部错位位置或生成诊断路径时改用 std::vector |
| 显式 DFS / 回溯搜索 | 待访问节点、路径增量或恢复点 | 将深度受限的调用栈转移到堆容器,可控状态体积 | 需按层遍历(BFS)或随机剪枝时改用 std::queue / std::deque |
| 操作撤销 / 状态回退 | 逆操作命令或增量快照 | 严格消费最近一次提交的逆操作 | 需分支历史、任意版本跳转或时间线查询时改用树/日志结构 |
| 表达式求值 | 操作数或待归约运算符 | 按优先级与结合性连续归约最近操作项 | 需保留完整 AST 供多遍优化时改用树结构 |
将贯穿场景扩展到多种括号时,栈中可以不存原始左括号,而是直接压入“未来期望匹配的右括号”,进一步压缩消费分支:
#include <stack>
#include <string>
bool balanced_brackets(const std::string& input) {
std::stack<char> expected;
for (char ch : input) {
if (ch == '(') expected.push(')');
if (ch == '[') expected.push(']');
if (ch == '{') expected.push('}');
if (ch == ')' || ch == ']' || ch == '}') {
if (expected.empty() || expected.top() != ch) {
return false;
}
expected.pop();
}
}
return expected.empty();
}
这里栈内存储的是后续动作所需的最小预期状态而非原始输入,同理也适用于显式 DFS 与撤销栈的状态瘦身。
边界与误区
std::stack 本身不提供并发同步,多线程共享读写必须由外部加锁或改用专门的并发结构;在显式 DFS 或回溯中,若每个栈元素复制大对象,性能瓶颈会从递归栈溢出转移到底层容器分配与对象拷贝。
核心判断
- 确认访问模式:是否严格只接触栈顶元素,不需要遍历、随机访问或中间删除。
- 控制元素代价:评估对象拷贝、移动与析构开销,按需选用
emplace或瘦身后的最小恢复状态。 - 选定底层容器:默认用
std::deque;容量可预估且重局部性时用std::vector(构造前先reserve);必须保节点地址稳定时用std::list。 - 核查安全边界:确认所有
top()/pop()都有!empty()守卫,且不跨修改操作缓存栈顶引用。
最小自检任务
阅读下面代码,判断它是否适合继续使用 std::stack,并说明 top() 返回引用在这段代码中的风险边界。要求按“访问模式 → 底层容器 → 状态修改 → 引用有效期”的顺序回答。
#include <stack>
#include <vector>
std::stack<int, std::vector<int>> values;
void append_many() {
values.push(1);
int& current = values.top();
for (int i = 0; i != 10000; ++i) {
values.push(i);
}
current = 42;
}
本章知识点总结
- 适配器本质
std::stack不管理存储与节点布局,仅通过裁剪底层容器接口并转发至back()、push_back()、pop_back()建立 LIFO 约束。 - 底层容器条件
任何
value_type一致且提供back()、push_back()、pop_back()的序列容器均可替代,默认std::deque<T>兼顾增长平稳与局部性。 - 容器替换取舍
std::vector<T>局部性最优但未暴露reserve()且扩容会使旧引用失效;std::list<T>节点地址稳定但逐节点分配开销显著。 - 状态路径边界
push/emplace入栈,top()返回栈顶左值引用,pop()仅移除栈顶且返回void以分离读取与状态变更;调用top()/pop()前必须保证非空。 - 封装与调试边界
不提供 iterator 与中间访问,一旦需要遍历或修改非栈顶元素就应改用底层序列容器;调试输出可按值拷贝副本并循环
top()/pop()。 - 典型适用场景
括号匹配、显式 DFS、回溯与单线撤销均属只触碰栈顶的场景,栈元素应保存最小预期或恢复状态而非原始大对象。
- 工程审查顺序
先确认严格 LIFO 访问,再评估元素代价与底层容器特性,最后核查空栈守卫、引用有效期与外部线程同步。