C / C++ / 系统课时

用 stack 处理后进先出任务

用 stack 处理后进先出任务

有些任务只允许操作“最后放进去”的数据,例如撤销最近一次编辑、解析嵌套括号或执行深度优先过程。std::stack 正是为这种后进先出规则设计的容器适配器,它主动限制访问方式,让代码直接表达这种约束。

学习目标

  • 掌握 std::stack 的 push、top、pop、empty 和 size
  • 理解后进先出为什么适合撤销与括号匹配
  • 判断什么时候应该使用 stack,什么时候应直接使用其他容器

stack 的访问限制就是它的价值

栈遵循 LIFO,也就是 Last In, First Out:最后压入的数据最先取出。std::stack 不提供随机访问,也不允许像普通序列容器那样直接遍历全部元素,常用操作只有栈顶附近的几个接口。

  • push(value):把元素压到栈顶。
  • top():访问栈顶元素,但不删除它。
  • pop():删除栈顶元素,没有返回值。
  • empty():判断栈是否为空。
  • size():取得当前元素数量。

调用 top() 或 pop() 前必须保证栈非空。需要“取出并删除”时,应先读取 top(),再调用 pop(),不能写成从 pop() 接收返回值。

撤销功能也是同样的结构:每执行一个可撤销操作,就把恢复所需的信息压栈;用户点击撤销时,只需要处理最近压入的记录。较早的记录自然留在下面等待后续撤销。

用括号匹配实践后进先出

嵌套括号要求最后打开的括号最先闭合。例如在 (a[b]{c}) 中,{ 必须先由 } 关闭,然后才轮到更早出现的 [ 和 (。这与栈的访问顺序完全一致。

下面的完整程序忽略普通字符,只检查 ()、[] 和 {} 是否正确配对。

cpp
#include <iostream>
#include <stack>
#include <string>

bool matches(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

bool isValid(const std::string& text) {
    std::stack<char> opens;

    for (char ch : text) {
        // 左括号暂存,等待后面最近出现的右括号与它匹配。
        if (ch == '(' || ch == '[' || ch == '{') {
            opens.push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            // 右括号出现时,只能与当前栈顶的左括号配对。
            if (opens.empty() || !matches(opens.top(), ch)) {
                return false;
            }
            opens.pop();
        }
    }

    return opens.empty();
}

int main() {
    std::cout << std::boolalpha;
    std::cout << "valid: " << isValid("(a[b]{c})") << '\n';
    std::cout << "invalid: " << isValid("([)]") << '\n';
}

预期输出:

text
valid: true
invalid: false

处理右括号时必须先检查 empty()。如果栈已经为空,说明出现了没有对应左括号的右括号;如果栈顶类型不匹配,例如 ([)] 中遇到 ) 时栈顶仍是 [, 也应立即判定失败。遍历结束后还要再次检查栈是否为空,否则说明仍有左括号没有关闭。

为什么这里不用 vector 直接模拟

当然可以用 std::vector 的 push_back、back 和 pop_back 模拟同样的行为,但 std::stack 能把“不允许访问中间元素”直接写进接口约束。看到参数类型是 std::stack,读代码的人就知道算法只关心最近压入的数据。

标准 std::stack 是容器适配器,默认通常使用 std::deque 作为底层容器。大多数业务代码无需依赖这个实现细节,只需要按照栈接口编程即可。

什么时候不该使用 stack

如果算法需要遍历全部元素、访问任意下标、在中间插入数据或按照其他顺序取元素,std::stack 的限制就会成为阻碍,此时应直接选择 vector、deque、关联容器或其他更匹配的数据结构。

判断是否适合栈,可以问一个简单问题:下一次要处理的数据,是否永远是最近加入而尚未处理的那一个? 如果答案是肯定的,撤销记录、括号匹配、表达式求值以及许多深度优先过程都很适合用栈表达。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 stack 处理后进先出任务

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通