std::stack 详解：栈适配器的实现、底层容器选择、应用场景

栈（stack）这东西，大家学数据结构时肯定都接触过。先进后出，后进先出，就这么个简单的逻辑。但说实话，我在实际项目中见过不少人自己手写栈，写得还漏洞百出。其实 STL 已经给我们准备好了现成的 std::stack，直接用就行，何必重复造轮子呢？

今天我就带大家把 std::stack 彻底搞明白。从它的实现原理，到底层容器的选择，再到两个经典的应用场景——括号匹配和表达式求值。嗯，这些都是我当年踩过坑的地方，希望能帮你少走弯路。

栈适配器：它到底是个什么角色？

先说说 std::stack 的本质。它不是一个独立的容器，而是一个容器适配器。什么叫适配器？说白了，就是给现有的容器套上一层皮，限制它的操作方式，只让你用栈的接口。

你想想看，std::deque 本身就能在两端操作，但栈只需要在一端操作。那怎么办？STL 的设计者就把它包装了一下，只暴露 push、pop、top 这几个接口。底层还是用 deque 在干活，但上层看起来就是个纯粹的栈。

我个人习惯把适配器理解成「接口转换器」。就像你有个 USB-C 的设备，但电脑只有 USB-A 口，加个转接头就能用了。std::stack 就是那个转接头，把通用容器的接口转成栈的专用接口。

底层容器选择：deque、vector、list 怎么选？

std::stack 默认使用 std::deque 作为底层容器。但你可以自己指定，比如 std::stack<int, std::vector<int>> 或者 std::stack<int, std::list<int>>。那问题来了：到底该用哪个？

我曾经在一个性能敏感的项目里做过对比测试，结果挺有意思的。下面这张表是我当时的测试结论：

底层容器	push 性能	pop 性能	内存占用	适用场景
deque（默认）	优秀	优秀	中等	通用场景，推荐默认
vector	尾部快，但可能触发扩容	尾部快	较低	元素数量可预估，追求内存紧凑
list	稳定，无扩容	稳定	较高（每个节点额外开销）	频繁插入删除，但栈很少用这个

说实话，绝大多数情况下用默认的 deque 就够了。我见过有人非要改成 vector，结果因为频繁扩容导致性能反而下降。除非你能提前知道栈的最大深度，否则别瞎折腾。

实战一：括号匹配

括号匹配是栈的经典应用。我记得刚入行时，面试官让我手写这个，我写了个递归版本，被批得狗血淋头。后来才明白，用栈才是正道。

思路很简单：遍历字符串，遇到左括号就入栈，遇到右括号就检查栈顶是否匹配。如果匹配就弹出，不匹配就报错。最后栈为空说明全部匹配。

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

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

bool isValidParentheses(const std::string& s) {
    std::stack<char> st;
    
    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (st.empty() || !isMatching(st.top(), ch)) {
                return false;
            }
            st.pop();
        }
    }
    
    return st.empty();
}

int main() {
    std::string test = "{[()]}";
    std::cout << (isValidParentheses(test) ? "匹配" : "不匹配") << std::endl;
    return 0;
}

这里有个坑，我曾经踩过：别忘了检查栈是否为空。如果字符串是 ")]}"，栈是空的，你直接取 top() 就会崩溃。所以每次取 top 之前，一定要先判断 empty()。

实战二：表达式求值

表达式求值比括号匹配复杂一些。我们需要两个栈：一个存操作数，一个存运算符。遍历表达式时，遇到数字就压入操作数栈，遇到运算符就根据优先级决定是否计算。

我记得有一次写计算器程序，被运算符优先级搞得焦头烂额。后来总结出一个规律：当前运算符优先级 ≤ 栈顶运算符优先级时，就先计算栈顶的。这个规则很管用。

#include <stack>
#include <string>
#include <sstream>
#include <cctype>
#include <iostream>

int applyOp(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: return 0;
    }
}

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

int evaluate(const std::string& expr) {
    std::stack<int> values;
    std::stack<char> ops;
    
    for (size_t i = 0; i < expr.length(); i++) {
        if (expr[i] == ' ') continue;
        
        if (isdigit(expr[i])) {
            int val = 0;
            while (i < expr.length() && isdigit(expr[i])) {
                val = val * 10 + (expr[i] - '0');
                i++;
            }
            values.push(val);
            i--; // 因为外层循环会自增
        } else if (expr[i] == '(') {
            ops.push(expr[i]);
        } else if (expr[i] == ')') {
            while (!ops.empty() && ops.top() != '(') {
                int b = values.top(); values.pop();
                int a = values.top(); values.pop();
                char op = ops.top(); ops.pop();
                values.push(applyOp(a, b, op));
            }
            ops.pop(); // 弹出 '('
        } else {
            while (!ops.empty() && precedence(ops.top()) >= precedence(expr[i])) {
                int b = values.top(); values.pop();
                int a = values.top(); values.pop();
                char op = ops.top(); ops.pop();
                values.push(applyOp(a, b, op));
            }
            ops.push(expr[i]);
        }
    }
    
    while (!ops.empty()) {
        int b = values.top(); values.pop();
        int a = values.top(); values.pop();
        char op = ops.top(); ops.pop();
        values.push(applyOp(a, b, op));
    }
    
    return values.top();
}

int main() {
    std::string expr = "10 + 2 * 6";
    std::cout << expr << " = " << evaluate(expr) << std::endl;
    return 0;
}

栈的核心操作与时间复杂度

栈的操作不多，但每个都很关键。我整理了一下：

操作	说明	时间复杂度
push()	压入元素到栈顶	O(1) 均摊
pop()	弹出栈顶元素（不返回值）	O(1)
top()	返回栈顶元素的引用	O(1)
empty()	判断栈是否为空	O(1)
size()	返回栈中元素个数	O(1)

看到没？所有操作都是 O(1) 的。这就是栈的魅力——简单、高效。但要注意，pop() 不返回值，这是很多人容易搞混的。如果你想获取栈顶元素再弹出，得先 top() 再 pop()。

栈的知识体系总览

下面这张图是我自己画的，把栈的核心知识点串了起来。你可以把它当作一个快速参考：

避坑指南

最后，我把自己这些年用栈踩过的坑总结一下，希望能帮你避开：

• pop 不返回值：这是 C++ 的设计决策，为了异常安全。想获取值，先 top 再 pop。
• 空栈上调用 top 或 pop：这是未定义行为，程序可能直接崩溃。每次操作前务必检查 empty()。
• 底层容器选型不当：默认 deque 最稳妥。vector 在频繁扩容时性能差，list 内存开销大。
• 忘记处理括号不匹配的情况：表达式求值时，如果括号不匹配，程序可能陷入死循环或崩溃。

我曾经在一个线上服务里，因为没检查空栈就调用了 top()，导致服务在高峰期崩溃了半小时。那次教训太深刻了，后来我写代码时，只要用到栈，第一件事就是检查 empty()。

好了，关于 std::stack 的内容就讲到这里。栈这东西看着简单，但用好了能解决很多实际问题。下次遇到需要「后进先出」的场景，别犹豫，直接用 std::stack 就对了。

---