C++ STL stack 栈 —— 像叠盘子一样后进先出 - 五级

栈（stack）：后进先出的数据结构，像叠盘子一样

想象你帮妈妈叠盘子：洗好的盘子一个叠一个放在最上面，需要用时，总是先拿走最上面的盘子（最后放上去的）。这种“后进先出”（Last In First Out，LIFO）的结构就是栈。在计算机里，栈是一种只能在一端操作的数据结构，这一端叫做栈顶。数据从栈顶放进去（压栈），也从栈顶取出来（弹栈），就像往筒里装乒乓球，最后装进去的球最先被弹出来。

栈在编程中非常常用：函数调用时的返回地址、撤销操作（Ctrl+Z）、浏览器后退按钮、括号匹配……很多算法都要靠栈来实现。记住“后进先出”，你就抓住了栈的灵魂。

1. 栈的核心：只能从栈顶进出

栈就像一摞盘子、一叠书、或一根只有一端开口的试管。你只能在最上面放东西，也只能从最上面拿东西。不能从中间或底部插入或取出，否则就破坏了“栈”的规矩。

压栈（push）：把元素放到栈顶，相当于在盘子堆上再放一个盘子。
弹栈（pop）：把栈顶元素拿走，盘子堆减少一个盘子。
查看栈顶（top）：看看最上面是什么盘子，但不拿走。
判空（empty）：盘架子上还有没有盘子？
大小（size）：盘架子上一共有多少个盘子？

2. 怎么在 C++ 里使用 stack？

需要包含头文件 <stack>。定义栈的语法：stack<元素类型> 栈变量名;。例如 stack<int> st; 表示一个存储整数的栈，名字叫 st。

常用操作一览：

操作	作用	示例
`push(值)`	把值压入栈顶	`st.push(5);`
`pop()`	弹出栈顶元素（无返回值）	`st.pop();`
`top()`	返回栈顶元素的引用（但不删除）	`int x = st.top();`
`empty()`	返回 true 表示栈为空，false 表示不为空	`if (st.empty()) ...`
`size()`	返回栈中元素个数（无符号整数）	`int n = st.size();`

注意：pop() 只是移除栈顶元素，不会返回被移除的值。如果想取出并删除栈顶元素，需要先 top() 再 pop()。

3. 生活中的栈：不止叠盘子

撤销操作（Ctrl+Z）：你每做一个操作（比如打字、画图），系统就把这个操作压入“撤销栈”。按下撤销时，它从栈顶弹出最近的一个操作并回退。所以按两次撤销会回退两步。
浏览器后退按钮：你访问网页 A → B → C，浏览器把 A、B 依次压入栈。当在 C 页点击后退，就弹出 C 回到 B；再后退弹出 B 回到 A。最后访问的页面永远在栈顶。
括号匹配：检查代码里的小括号 ()、中括号 []、大括号 {} 是否成对。遇到左括号压栈，遇到右括号就查看栈顶是否匹配，匹配则弹栈，不匹配则报错。最后栈空说明全部匹配。
函数调用：程序执行时，每个函数调用都会把返回地址和局部变量压入“调用栈”。函数返回时从栈顶弹出，回到上一个函数继续执行。

4. 完整示例：叠盘子（模拟日常使用）

下面的程序模拟了叠盘子的过程：先洗了3个盘子，依次叠放，然后需要用时，从最上面开始拿。

#include <iostream>
#include <stack>  // 使用栈需要这个头文件
using namespace std;

int main() {
    // 定义一个整数栈，每个整数代表一个盘子编号
    stack<int> plates;

    // 洗好三个盘子，依次叠放（压栈）
    plates.push(1);  // 第一个盘子
    plates.push(2);  // 叠在1上面
    plates.push(3);  // 叠在2上面

    cout << "栈顶（最上面的盘子）是：" << plates.top() << endl;
    cout << "一共有 " << plates.size() << " 个盘子" << endl;

    // 开始用盘子：每次从上面拿一个
    while (!plates.empty()) {
        cout << "拿走了盘子 " << plates.top() << endl;
        plates.pop();  // 弹出栈顶
    }

    cout << "盘子全部拿完，栈空了" << endl;
    return 0;
}

运行结果：

栈顶（最上面的盘子）是：3
一共有 3 个盘子
拿走了盘子 3
拿走了盘子 2
拿走了盘子 1
盘子全部拿完，栈空了

5. 完整示例：用栈检查括号是否配对

这个例子更贴近编程场景。读入一个由 ( 和 ) 组成的字符串，判断括号是否匹配。

#include <iostream>
#include <stack>  // 使用栈
#include <string> // 使用字符串
using namespace std;

int main() {
    string expr = "((a+b)*(c-d))";  // 待检查的表达式
    stack<char> s;  // 字符栈，用来存放左括号

    for (int i = 0; i < expr.size(); i++) {
        char ch = expr[i];
        if (ch == '(') {
            s.push(ch);  // 遇到左括号，压栈
        } else if (ch == ')') {
            // 遇到右括号，需要检查栈是否为空
            if (s.empty()) {
                cout << "括号不匹配：右括号太多" << endl;
                return 0;
            }
            s.pop();  // 栈顶有左括号，弹出一个（配对成功）
        }
    }

    // 最终栈应为空，否则说明左括号太多
    if (s.empty()) {
        cout << "括号匹配成功！" << endl;
    } else {
        cout << "括号不匹配：左括号太多" << endl;
    }
    return 0;
}

运行结果：

括号匹配成功！

6. 新手容易犯的错误

在空栈上调用 top() 或 pop()
top() 和 pop() 要求栈非空，否则程序会崩溃（未定义行为）。
正确做法：先检查 empty()，再操作。
```
if (!st.empty()) {
    cout << st.top() << endl;
    st.pop();
}
```
误以为 pop() 会返回被弹出的值
pop() 的返回类型是 void，不返回任何东西。要同时获得值并删除，必须两步：
```
int val = st.top();  // 先取
st.pop();            // 再删
```
混淆栈和队列
栈是后进先出（LIFO），队列是先进先出（FIFO，就像排队买饭）。使用时一定要搞清楚需求。
忘记包含头文件
没写 #include <stack> 直接使用 stack 会编译报错。

7. 相关指引

学完栈之后，可以继续了解：

C++ STL 队列（queue）：先进先出，与栈正好相反。
双端队列（deque）：两端都可以插入删除，是 stack 和 queue 的底层容器。
栈的应用：深度优先搜索（DFS）、表达式求值（中缀转后缀）、模拟递归等。
手动实现栈：用数组或链表模拟栈的操作，理解底层原理。

栈是数据结构的入门基石，掌握了它的“后进先出”思想，你会发现很多问题都能用栈优雅地解决。

例题精讲