C++栈（stack）——后进先出，就像叠盘子

栈是什么？为什么需要它？

栈是一种“后进先出（LIFO）”的数据结构，就像你家里叠盘子：最后放上去的盘子在最上面，最先被拿走。在编程中，当我们需要“记住操作顺序，然后倒着处理”时，栈就派上了大用场。比如：

你在手机上打字时按“撤销”，就会撤销最近一次操作——这正是栈的后进先出。
浏览器点击“后退”，会回到上一个浏览的页面——也是用栈来记录访问历史。
检查算式里的括号是不是成对出现——把左括号压栈，遇到右括号就弹出一个左括号，如果最后栈为空说明括号匹配。

生活中的栈，多举几个例子

除了叠盘子，还有很多地方用到“后进先出”：

叠衣服：你把一件件叠好的T恤放进衣柜，最先放的在最底下，最后放的在最上面。你要拿衣服时，总是先拿最上面的（最后放的那件）。
一摞书：把书一本本叠起来，要取书的时候只能从最上面取。
地铁排队上车：想象一个很窄的通道，只能一个人通过，进去的人排在通道里，最后进去的人得先出来才能让前面的人出来？不，地铁排队是先进先出（队列）。但是如果你把一群人挤在一个电梯里，最后上电梯的人站在门口，下电梯时他先出来——这就是后进先出。

注意：栈和队列的区别就像叠盘子（后进先出）和排队买东西（先进先出）。后面我们会学到队列。

C++ 中的栈：怎么用？

C++ 标准库已经帮我们写好了栈，你只需要包含头文件 <stack>，然后像这样定义一个栈：

#include <stack>   // 用栈必须包含它
using namespace std;

stack<int> s;       // 定义一个存储整数的栈，变量名叫 s
stack<char> c;      // 定义一个存储字符的栈
stack<string> words; // 定义一个存储字符串的栈

常用操作有 5 个，记起来很简单：

操作	代码例子	意思
压入	`s.push(100);`	把 100 放到栈顶（叠上去）
弹出	`s.pop();`	把栈顶元素拿走（但不能拿到值）
查看栈顶	`int x = s.top();`	看一眼栈顶的值，但不拿走
判空	`if (s.empty())`	栈为空返回 true，否则 false
大小	`int n = s.size();`	返回栈里有多少个元素

特别提醒：

pop() 只是弹出元素，不会返回它；如果你既要看又要拿走，需要先 top() 再 pop()。
在调用 top() 或 pop() 之前，一定要先检查栈是否为空，否则程序会崩溃（就像你从空盘架上拿盘子，手会伸空）。

新手容易犯的 3 个错误

1. 忘记检查空栈就 `top()` 或 `pop()`

stack<int> s;
s.pop();          // ❌ 错误！栈是空的，程序会崩溃

正确做法：先 if (!s.empty()) 再操作。

2. 忘记 `pop()`，导致死循环

while (!s.empty()) {
    cout << s.top();  // 每次都只打印栈顶，不弹出
    // 忘记 s.pop()，循环永远停不下来！
}

要记得在打印后调用 s.pop()。

3. 混淆 `push` 和 `pop` 的方向

栈只有一端操作（栈顶），不能像数组那样随意插入中间。如果你想实现“撤销”，只能撤销最近一次操作，不能撤销中间的。

完整示例：用栈模拟“撤销操作”

小明在写作业，他依次做了三件事：

写了“A”
写了“B”
写了“C”

现在他想撤销两次（也就是删除最后写的两个字母），最后剩下什么？

我们用栈来模拟：每做一件事，就把这件事压入栈；撤销一次，就弹出一个栈顶。最后栈里剩下的就是没被撤销的操作。

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

int main() {
    // 定义一个栈，用来存储每一步操作的名字
    stack<string> actions;

    // 依次做三件事，每做一件事就压入栈
    actions.push("写A");   // 第一步：写A
    actions.push("写B");   // 第二步：写B
    actions.push("写C");   // 第三步：写C

    cout << "当前栈里有 " << actions.size() << " 个操作" << endl;

    // 撤销两次：每次弹出栈顶
    if (!actions.empty()) {
        cout << "撤销：" << actions.top() << endl;
        actions.pop();   // 弹出“写C”
    }
    if (!actions.empty()) {
        cout << "撤销：" << actions.top() << endl;
        actions.pop();   // 弹出“写B”
    }

    // 看看现在栈里还剩什么
    cout << "撤销两次后，栈里还剩 " << actions.size() << " 个操作" << endl;
    if (!actions.empty()) {
        cout << "剩下的是：" << actions.top() << endl;  // 应该是“写A”
    }

    return 0;
}

运行结果：

当前栈里有 3 个操作
撤销：写C
撤销：写B
撤销两次后，栈里还剩 1 个操作
剩下的是：写A

你看，最后剩下的就是最开始的“写A”，因为它是最早压入的，最后才被弹出。

小练习：自己试试看

把上面的代码改成用栈模拟“浏览器后退”：依次访问“首页”、“新闻页”、“图片页”，后退两次，最后当前页面是什么？
用栈实现一个简单的括号匹配程序：输入一串只包含 ( 和 ) 的字符串，判断括号是否匹配（比如 () 匹配，) ( 不匹配）。提示：遇到左括号压栈，遇到右括号就弹出一个左括号，如果最后栈为空则匹配。

C++栈（stack）——像叠盘子一样存放数据