Skip to main content

Chapter 22: Stack

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

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() 之前,确保多余右括号不会对空栈执行未定义操作。

排查顺序

  1. 空栈前提:调用 top() 或 pop() 前是否已确认 !empty()。
  2. 引用捕获:是否缓存了 top() 返回的引用/指针,并在随后执行了 push() 或 pop()。
  3. 异常边界:值提取与 pop() 是否分离,避免读取失败导致元素丢失。
  4. 容器代价:当前 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 或回溯中,若每个栈元素复制大对象,性能瓶颈会从递归栈溢出转移到底层容器分配与对象拷贝。

核心判断

  1. 确认访问模式:是否严格只接触栈顶元素,不需要遍历、随机访问或中间删除。
  2. 控制元素代价:评估对象拷贝、移动与析构开销,按需选用 emplace 或瘦身后的最小恢复状态。
  3. 选定底层容器:默认用 std::deque;容量可预估且重局部性时用 std::vector(构造前先 reserve);必须保节点地址稳定时用 std::list。
  4. 核查安全边界:确认所有 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 访问,再评估元素代价与底层容器特性,最后核查空栈守卫、引用有效期与外部线程同步。