Skip to main content

Chapter 22: Stack

std::stack 讨论的核心问题是：当代码只需要“最后放入的元素最先被处理”时，标准库怎样把一个普通序列容器收窄成稳定的 LIFO 操作表面。读完本章后，读者应能判断一个场景是否适合 std::stack，能追踪 push、pop、top 到底层容器的状态变化，并能解释为什么 std::stack 默认使用 std::deque，但仍允许换成 std::vector 或 std::list。

本章的贯穿材料是一段括号匹配代码。它只需要保存“尚未被匹配的左括号”，每读到一个右括号，就检查最后一个左括号。这个场景要求访问最近一次压入的元素，并在确认匹配后移除它。std::stack 的接口正好把这个需求限制到 push、top、pop、empty 这几个动作。

标准层面，std::stack 是 container adaptor。适配器的意思是：它自己提供新的接口形状，元素存储和生命周期管理交给底层容器。C++ 工作草案的 stack.general 说明，任何支持 back()、push_back()、pop_back() 的序列容器都可用于实例化 stack；std::stack 参考页 也把默认模板参数列为 std::deque<T>。这两个事实给出本章的主线：stack 的语义来自接口限制，性能和对象状态来自底层容器。

先看贯穿材料：

#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，也没有读取底层容器的第一个元素。它只关心最后一个尚未匹配的左括号。后文每一节都会回到这段代码：先解释 LIFO 语义，再追踪底层容器条件，再分析 push、pop、top 的状态路径，最后给出工程选型顺序。

22.1 LIFO 语义与容器适配器目标​

LIFO 是 Last-In First-Out，工作定义是：一组元素按时间顺序进入结构，下一次可访问和可移除的元素始终是最近一次进入且尚未移除的元素。括号匹配中，最新读到的左括号最先等待当前右括号匹配；函数调用栈中，最新进入的函数帧最先返回；撤销栈中，最近一次操作最先撤销。这些场景的共同点是“历史顺序”存在，但当前动作只允许触碰栈顶。

std::stack 的目标是把底层容器的宽接口收窄成 LIFO 表面。底层的 std::deque、std::vector、std::list 都能保存一串元素，但它们分别提供索引、迭代、插入、擦除等操作。std::stack 只保留后端相关动作：向顶部插入、读取顶部、移除顶部、查询数量和空状态。接口被收窄后，调用者很难在正常代码中写出“从中间拿一个元素再继续当栈使用”的逻辑。

可以把 std::stack<T, Container> 理解成一个很薄的包装层。标准定义中有一个受保护成员 Container c，成员函数基本转发到底层容器：empty() 调用 c.empty()，size() 调用 c.size()，top() 调用 c.back()，push() 调用 c.push_back()，pop() 调用 c.pop_back()。这说明 stack 自己不发明节点布局，也不重新管理元素内存；它通过接口裁剪表达“只能操作后端”。

一个教学简化版本能看出这个形状：

#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_;
};

这个简化代码只展示接口转发关系，真实标准库还包含构造、分配器、比较、交换、C++23 push_range、C++26 constexpr 支持等细节。它已经足够解释本章主问题：stack 的 LIFO 语义由“只暴露后端操作”建立，元素存储由底层容器承担。

回到括号匹配代码，pending.push('(') 把一个未匹配左括号追加到后端。遇到 ')' 时，算法只需要知道有没有可匹配的最近左括号。若 pending.empty() 为真，说明当前右括号没有前置左括号；若为假，pending.pop() 移除最近的左括号。这里的正确性依赖 LIFO：内层括号必须先闭合，最近的左括号必须最先被匹配掉。

22.2 默认 deque 与可替换底层容器条件​

std::stack 的第二个模板参数是底层容器类型。默认是 std::deque<T>，但 std::vector<T> 和 std::list<T> 也满足常用实例化条件。判断一个容器能否作为 stack 底层容器，应先看两个层级：标准接口条件和工程成本条件。接口条件决定代码是否合法，工程成本条件决定这个选择在当前负载下是否合适。

标准接口条件可以压缩成一句：底层容器的 value_type 要和 T 一致，并且要提供普通语义的 back()、push_back()、pop_back()。back() 给 top() 提供引用，push_back() 给 push() 提供插入路径，pop_back() 给 pop() 提供销毁路径。容器还要满足序列容器的基础要求，因为 stack 需要使用它的构造、大小、空状态和交换等能力。

三种常见底层容器的差异体现在内存布局和扩容路径上：

底层容器存储形状push 成本特征top / pop 成本特征适合的栈负载
std::deque<T>分段连续存储两端增长友好，后端增长通常不搬移全部元素后端访问和移除稳定默认选择，适合大小波动、无需连续内存的栈
std::vector<T>单段连续存储容量不足时重新分配并移动或拷贝元素后端访问和移除局部成本低元素数量可预估、重视局部性、可提前 reserve 的栈
std::list<T>双向链表节点每个元素通常独立分配节点后端访问和移除稳定，但分配和指针追踪开销更明显需要稳定节点地址、元素移动成本很高的少数场景

默认使用 deque 的原因在于它给 stack 提供均衡行为。stack 只操作后端，vector 在容量充足时表现很好，但容量不足会触发整段存储迁移。list 的单次后端插入和删除能保持节点稳定，但每个节点通常需要单独分配，连续访问局部性较差。deque 通过分段存储降低整段迁移压力，同时保持常量时间的后端访问和移除，因此适合作为一般默认。

换底层容器时，语义仍然是 LIFO，但引用、指针、分配次数和缓存局部性会变化。以下代码把底层容器换成 vector：

#include <stack>
#include <vector>

std::stack<int, std::vector<int>> history;

void record(int value) {
    history.push(value);
}

这段代码合法，因为 std::vector<int> 提供 back()、push_back()、pop_back()。不过 std::stack 没有直接暴露 reserve()，调用者无法通过 history.reserve(...) 预留容量。若需要显式控制容量，可以先构造底层 vector，再移动进 stack：

#include <stack>
#include <vector>

std::vector<int> storage;
storage.reserve(1024);

std::stack<int, std::vector<int>> history(std::move(storage));

这个写法的判断点是：容量策略属于底层容器，stack 只负责 LIFO 表面。若后续负载超过预留容量，vector 仍会扩容并移动或拷贝已有元素。若代码保存了 top() 返回的引用，随后 push() 触发扩容，该引用可能失效。使用 deque 时，后端扩展的失效规则和实现细节不同，但仍应把“跨修改操作长期保存栈顶引用”视为需要审查的写法。

22.3 push、pop 与 top 的状态路径​

push、top、pop 是 stack 的核心状态路径。push 让一个新元素进入栈顶，top 返回当前栈顶引用，pop 销毁并移除当前栈顶。三者共同形成 LIFO 的最小循环：写入新状态，观察最新状态，提交移除最新状态。

先看 push。当代码执行 pending.push('(') 时，字符对象被传给底层容器的 push_back。底层容器在后端创建一个新元素，栈的大小增加一，新的后端元素成为 top() 的返回对象。若元素类型较重，push 可能执行拷贝或移动；若使用 C++11 之后的 emplace，参数会转发给底层容器的 emplace_back，元素可在后端原位构造。

#include <stack>
#include <string>

std::stack<std::string> calls;

calls.push("parse");              // 构造临时 string，再移动或拷贝进底层容器
calls.emplace("evaluate");        // 在底层容器后端直接构造 string

这段代码的关键点在对象生命周期。push("parse") 需要把输入值转换成 std::string，再交给容器保存；emplace("evaluate") 把构造参数交给底层容器，在栈顶位置创建元素。两者结束后，calls.top() 都指向最新保存的字符串。工程上应根据元素构造成本和可读性选择 push 或 emplace，并把异常安全交给底层容器的插入路径判断。

再看 top。top() 返回的是栈顶元素引用，通常等价于底层容器的 back()。它不复制元素，也不移除元素，因此适合在 pop() 前读取或修改当前栈顶。调用 top() 前必须确认栈非空，因为空容器的 back() 没有可返回对象。

#include <stack>

std::stack<int> values;
values.push(10);
values.push(20);

int latest = values.top();  // latest == 20
values.top() = 21;          // 修改当前栈顶元素

这个例子展示了 top() 的引用语义。latest 是拷贝出来的整数，后续修改栈顶不会改变它；values.top() = 21 修改的是底层容器后端元素。若元素类型持有资源，top() 返回引用可以减少复制，但引用的有效期受后续 push、pop、底层容器扩容和栈对象自身生命周期约束。

最后看 pop。pop() 只移除栈顶，返回类型是 void。这个设计要求调用者先用 top() 获取需要的值，再调用 pop() 提交移除动作。这样可以把“读取栈顶”和“改变栈状态”拆开，异常边界也更清晰：读取或拷贝元素可能失败，移除元素走底层容器的 pop_back() 路径。

#include <stack>

int take_top(std::stack<int>& values) {
    int result = values.top();
    values.pop();
    return result;
}

这段代码的前提是 values 非空。更稳妥的调用顺序是先在外层检查 empty()。括号匹配代码正是这样写的：遇到右括号后先检查 pending.empty()，确认存在可移除元素后再 pop()。这个顺序把失败情况放在状态修改之前，能保证一个多余右括号不会破坏已有状态。

push、top、pop 的判断顺序可以固定为四步。先看栈是否可能为空，再看当前操作是否读取引用，再看本次操作是否改变元素数量，最后看底层容器是否可能分配、移动、销毁元素。这个顺序比单纯背 API 更有用，因为它能迁移到 queue、priority_queue 和自定义适配器的状态审查中。

22.4 iterator 封装边界与顺序语义​

std::stack 没有暴露 begin()、end()、随机访问下标或中间插入接口。这个封装边界服务于顺序语义：调用者只能从栈顶观察和移除元素，无法把底层序列当普通容器遍历后再继续声称代码遵守 LIFO。接口限制让“最近进入的元素先处理”成为可维护的约束。

括号匹配代码体现了这个边界。算法无需知道所有未匹配左括号的位置，只需要知道是否还有左括号可匹配。若代码开始遍历底层容器，通常意味着需求已经超出 LIFO，例如要统计所有未匹配位置、输出错误路径、支持随机撤销或从中间删除状态。此时应直接使用 std::vector、std::deque 或自定义结构表达真实需求。

std::stack 的底层成员在标准定义中是受保护的 c，派生类可以访问它，但普通调用者没有公开入口。通过派生类暴露底层容器是可写的 C++，但工程上会削弱适配器的语义边界：

#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 名称会误导维护者，让他们以为代码只执行 LIFO 操作。

顺序语义还影响比较和格式化。标准库为 std::stack 提供了关系比较等非成员操作，比较通常转到底层容器的比较规则；C++23 引入 formatter 支持，C++23 也增加范围插入相关能力。这些能力没有改变 LIFO 主接口。阅读相关实现时，应把它们归类为“适配器围绕底层容器补齐的外部能力”，核心判断仍应围绕 LIFO 主接口展开。

当需求包含调试输出时，可以在边界上做一次有意识的复制。复制一个 stack，循环读取 top() 并 pop()，可以按从顶到底的顺序输出快照，同时不改变原始栈：

#include <iostream>
#include <stack>

void print_from_top(std::stack<int> values) {
    while (!values.empty()) {
        std::cout << values.top() << '\n';
        values.pop();
    }
}

这个函数按值接收 stack，因此修改的是副本。它适合调试或日志，成本是复制底层容器中的元素。若元素数量大或元素复制成本高，应重新评估日志需求；若业务逻辑需要频繁从栈底到栈顶查看内容，使用底层序列容器会更直接。

22.5 工程使用场景​

选择 std::stack 的第一步是确认问题只需要栈顶。只要需求能表述成“新增一个当前状态、查看最近状态、完成后移除最近状态”，std::stack 就有清晰适用性。括号匹配、显式 DFS、回溯搜索、表达式求值、操作撤销、路径回退都属于这一类。它们的共同证据是：非栈顶元素在当前步骤中只是历史上下文，当前动作无需直接修改它们。

括号匹配是最小场景。左括号入栈，右括号消费栈顶，结束时栈为空才说明所有左括号都被匹配。这个模型可以扩展到多种括号：栈里保存期望的右括号，读到右括号时和 top() 比较。关键判断仍然是最近开启的结构必须最先闭合。

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

这段代码把“尚未匹配的左括号”改成“未来期望遇到的右括号”。读到 [ 时压入 ]，读到 ] 时检查栈顶。这个改写降低了分支判断数量，也让栈顶含义更接近当前检查动作。它说明 stack 中保存的元素不一定是原始输入，也可以是后续动作所需的最小状态。

显式 DFS 和回溯搜索是更工程化的场景。递归调用依赖语言运行时调用栈，显式 std::stack 则把待处理节点、路径状态或恢复点放入堆上容器。这样可以控制状态对象、记录调试信息，并在某些场景中减少深递归带来的栈空间风险。选择显式栈时，应检查每个栈元素是否包含恢复所需的最小状态；若每个元素都复制大对象，瓶颈可能转移到底层容器分配和元素移动。

撤销和状态回退也适合 stack。每次操作提交前保存逆操作或快照，撤销时读取最近一次记录并弹出。这里的边界是分支历史：若系统支持任意历史点跳转、合并多个分支或按时间范围查询，单个 stack 的 LIFO 表面会受限，通常需要 vector、树状历史或日志结构。

工程选型可以固定成以下顺序。先判断访问模式是否只触碰最近元素；再判断是否需要遍历、中间删除或随机访问；然后判断元素类型的复制、移动和销毁成本；接着选择底层容器，默认 deque，容量可预估且重视局部性时考虑 vector，需要节点稳定且能接受分配成本时考虑 list；最后检查空栈调用、引用有效期、异常安全和线程同步。std::stack 本身不提供并发同步，多线程共享时需要外部锁或使用专门的并发栈结构。

最小自检任务​

阅读下面代码，判断它是否适合继续使用 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;
}

答案要点​

这段代码的访问模式表面上是 LIFO，因为它只调用 push() 和 top()，没有遍历或中间删除。底层容器选择了 std::vector<int>，它满足 stack 的接口条件：能提供 back()、push_back()、pop_back()。风险出现在状态修改和引用有效期之间：int& current = values.top() 绑定到当前 vector 后端元素，随后循环执行大量 push()。当 vector 容量不足时，底层存储可能重新分配，旧元素被移动或拷贝到新存储，原来的引用可能失效。current = 42 在引用失效后写入，行为不再有可靠语义。

修正思路是缩短引用使用范围，或在所有 push() 之后重新获取 top()。若确实需要在大量追加后修改原来的元素，std::stack 的接口已经表达不出“修改旧栈顶下方某个元素”的需求，应改用 std::vector 或其他能暴露位置的结构。若目标是让 vector 扩容次数可控，可以在构造底层容器时预留容量；这个动作能降低扩容概率，长期保存栈顶引用仍然需要单独审查。

本章知识点总结​

  • LIFO 语义：栈的当前可访问对象始终是最近进入且尚未移除的元素。
  • 适配器目标：std::stack 通过收窄底层容器接口，把普通序列容器包装成后端操作表面。
  • 底层容器：stack 的元素存储、分配、移动、销毁和引用有效期由底层容器决定。
  • 接口条件：可作为底层容器的类型需要提供 back()、push_back()、pop_back()，并满足序列容器基础要求。
  • 默认 deque：std::deque 在大小波动和后端增长场景中提供均衡成本，因此适合作为默认底层容器。
  • vector 边界：std::vector 底层栈具备连续存储局部性，但容量不足时可能迁移元素并影响旧引用。
  • list 边界：std::list 底层栈能保持节点稳定，但节点分配和指针追踪会增加运行成本。
  • push 路径：push() 转到底层 push_back()，新元素进入后端并成为新的栈顶。
  • top 路径：top() 返回底层 back() 引用，调用前必须确认栈非空。
  • pop 路径：pop() 转到底层 pop_back()，只移除栈顶并且返回 void。
  • 封装边界：std::stack 不暴露 iterator，调用者无法通过公开接口遍历或修改中间元素。
  • 调试快照：需要输出栈内容时，可以复制一个栈并循环 top() / pop()，成本是复制底层元素。
  • 场景判断：括号匹配、回溯、显式 DFS、撤销历史适合使用 std::stack，前提是当前动作只依赖最近状态。
  • 审查顺序：先看访问模式，再看是否需要非栈顶访问，再看元素成本，最后检查底层容器、空栈调用和引用有效期。