栈（Stack）——后进先出的“叠盘子”魔法

你有没有试过叠盘子？每次洗完盘子，你总是把新盘子叠在旧盘子上面。等要用的时候，你只能从最上面拿，最后放上去的盘子最先被拿走，最早放上去的盘子反而要等到所有上面的盘子都拿光才能取出。这种“后进先出”（LIFO，Last In First Out）的规则，就是**栈（Stack）**的核心思想。

在编程中，栈就像一节只能从一头打开的“管子”。你把数据从这头塞进去（入栈），取出时也只能从这头取最上面的那一个（出栈）。很多编程语言都直接提供了栈的工具，比如 C++ 的 STL 中就有 stack 容器适配器，Python 里也能用 list 或 collections.deque 轻松模拟。本文会带你一步一步学会栈，并用代码亲手体验它的“魔法”。

生活里的栈：到处都是“后进先出”

除了叠盘子，你还能在哪些地方看到栈？

浏览器的“后退”按钮：你依次访问了页面 A → B → C，点击“后退”会先回到 C 之前的 B，再回到 A。最后访问的页面最先被退回。
编辑器的“撤销”（Ctrl+Z）：你打了10个字，又删了3个，然后撤销——撤销的是你最近的一次操作，而不是最早的操作。
一摞作业本：老师把收上来的作业本一本一本叠起来，最上面那本是最后交的，批改时也是从最上面开始拿。
地铁里的自动售票机：你投入的硬币一枚一枚叠在通道里，取回找零时，机器会把最后放入的那枚硬币先吐出来（前提是设计成栈式结构）。

你看，栈其实一直就在我们身边，只是我们没给它取这个名字而已。

计算机里的栈：三个核心操作

在编程中，栈只有三个最基本的操作，却可以解决很多经典问题：

操作	英文名	做什么	生活比喻
入栈	`push(x)`	把元素 x 放到栈顶	把新盘子放到最上面
出栈	`pop()`	移除栈顶元素（但不返回它）	拿走最上面的盘子丢掉（不关心它是什么）
取栈顶	`top()`	看一眼栈顶元素是什么（但不拿走）	瞄一眼最上面的盘子长什么样
判空	`empty()`	检查栈里有没有元素	看看桌子上还有没有盘子
大小	`size()`	返回栈中的元素个数	数一数叠了多少个盘子

特别提醒：pop() 只移除元素，不告诉你移除的是什么；top() 只查看不删除。如果需要“拿下来看看再扔掉”，必须先用 top() 拿到，再用 pop() 移除。

C++ 中的 stack：用“容器适配器”实现

C++ 的 STL 提供了一个现成的 stack 类，叫做容器适配器。什么意思呢？就像给普通水杯加上一个滤网就变成滤水杯——stack 是在其他容器（默认是 deque）外面加了一层限制，只允许从一端操作，从而实现了栈的功能。你也可以指定用 vector 或 list 作为底层容器，不过对于初学者，用默认的 deque 就足够了。

使用步骤

包含头文件：#include <stack>
定义栈对象：stack<int> s; ——这创建了一个存储 int 类型元素的空栈。
调用成员函数：s.push(10); s.pop(); 等。

底层容器怎么选？

虽然默认用的是 deque，但你可以这样指定别的容器：

stack<int, vector<int>> sv;  // 用 vector 当底层
stack<int, list<int>>   sl;  // 用 list 当底层

通常情况下，deque 性能很好，不需要改。但如果你需要更快的随机访问（栈不提供随机访问，所以一般无需），或者要控制内存分配，才会考虑换。

C++ 完整代码示例（带注释）

下面是一个完整的 C++ 程序，展示栈的基本用法，并附有详细的中文注释。

#include <iostream>
#include <stack>  // 使用stack必须包含这个头文件

using namespace std;

int main() {
    // 创建一个int类型的栈
    stack<int> s;

    // 1. 检查栈是否为空
    if (s.empty()) {
        cout << "栈现在是空的" << endl;
    }

    // 2. 向栈中压入元素（入栈）
    s.push(10);   // 压入10
    s.push(20);   // 压入20，现在栈顶是20
    s.push(30);   // 压入30，栈顶是30
    s.push(40);
    s.push(50);   // 最后压入50，栈顶是50

    cout << "当前栈的大小: " << s.size() << endl;  // 应该输出5

    // 3. 查看栈顶元素（不删除）
    cout << "栈顶元素是: " << s.top() << endl;    // 输出50

    // 4. 弹出栈顶元素（删除，不返回）
    s.pop();  // 移除了50
    cout << "pop之后，新栈顶是: " << s.top() << endl;  // 输出40

    // 5. 遍历栈：依次弹出所有元素（这是栈的唯一遍历方式）
    cout << "依次弹出所有元素: ";
    while (!s.empty()) {
        cout << s.top() << " ";  // 输出当前栈顶（40、30、20、10）
        s.pop();                  // 移除栈顶
    }
    cout << endl;

    // 现在栈又空了
    cout << "栈的大小: " << s.size() << endl;

    // 如果你要清空一个栈，直接赋值一个空栈即可
    // s = stack<int>();  // 这样也能清空，不过用 while 循环更安全

    return 0;
}

运行结果：

栈现在是空的
当前栈的大小: 5
栈顶元素是: 50
pop之后，新栈顶是: 40
依次弹出所有元素: 40 30 20 10 
栈的大小: 0

所有操作的时间复杂度都是 O(1)，也就是常数时间，非常快。

Python 中的栈：用 list 和 deque 模拟

Python 没有内置 stack 类，但用 list 就能秒变栈：

append(x) 对应 push
pop() 默认移除最后一个元素，正好对应栈的 pop
list[-1] 访问最后一个元素，对应 top

用 list 模拟栈（推荐新手）

# 使用 Python 的 list 模拟栈
def main():
    # 创建一个空栈（用list表示）
    stack = []

    # 检查栈是否为空
    if not stack:
        print("栈是空的")

    # 向栈中压入元素
    stack.append(10)
    stack.append(20)
    stack.append(30)
    stack.append(40)
    stack.append(50)

    print("当前栈的大小:", len(stack))  # 输出5

    # 访问栈顶元素（不删除）
    print("栈顶元素是:", stack[-1])   # 输出50

    # 弹出栈顶元素
    stack.pop()  # 移除了50
    print("pop之后，新栈顶是:", stack[-1])  # 输出40

    # 依次弹出所有元素
    print("依次弹出所有元素:", end=" ")
    while stack:
        print(stack.pop(), end=" ")   # 每次弹出最后一个元素
    print()

    # 现在栈又空了
    print("栈的大小:", len(stack))

if __name__ == "__main__":
    main()

运行结果和 C++ 完全一样。

用 deque 模拟栈（性能更稳定）

collections.deque 是双端队列，它的 append 和 pop 默认都在右端操作，可以完美模拟栈。而且 deque 在左端操作也很快，如果你以后需要既当栈又当队列，用它更合适。

from collections import deque

stack = deque()        # 创建一个空栈（deque类型）
stack.append(10)       # 入栈
stack.append(20)
x = stack.pop()        # 出栈，x = 20
print("栈顶是:", stack[-1])  # 输出10

注意：deque.pop() 默认是右端（栈顶），如果要左端弹出要用 deque.popleft()。用 deque 模拟栈时，始终只用右端操作（append 和 pop）即可。

新手最容易犯的错误

初学栈时，下面这些坑你可能会踩到，提前知道就避免了：

pop 之后再访问 top

stack<int> s;
s.push(5);
s.pop();
cout << s.top();  // 错误！栈已经空了，访问 top 会导致程序崩溃

解决办法：每次 pop 前先判断 !s.empty()。

忘记包含头文件
C++ 中 #include <stack> 是必须的，不然编译器会报错。
混淆栈和队列
栈是后进先出，队列是先进先出。不要搞混，比如你顺序压入 1、2、3，栈弹出顺序是 3、2、1，队列弹出顺序是 1、2、3。
试图用下标访问栈中间元素
C++ 的 stack 没有 operator[]，Python 的 list 虽然能用下标，但那样就不是栈了，失去了“只能从一端操作”的意义。如果你需要用下标，就用 vector 或 list，不要用栈适配器。
Python 中误用 list.pop(0)
如果你写 list.pop(0)，它会把列表最左边的元素弹出，这就不像栈了（像队列）。栈只能用 pop() 不带参数（默认弹出右边）。

栈的经典应用：括号匹配

学了栈，我们马上来做一个趣味题：检查字符串中的括号是否匹配。比如 "(()())" 是匹配的，"(()" 是不匹配的。

思路：遍历字符串，遇到左括号 ( 就入栈，遇到右括号 ) 就检查栈顶是不是左括号，如果是就弹出，否则匹配失败。最后如果栈空了，说明所有括号都成对匹配。

下面是一个完整的 C++ 示例（带注释）：

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

using namespace std;

// 判断括号是否匹配的函数
bool isValid(string s) {
    stack<char> st;  // 创建一个字符类型的栈

    // 遍历字符串中的每个字符
    for (char ch : s) {
        if (ch == '(') {
            st.push(ch);  // 左括号入栈
        } else if (ch == ')') {
            // 遇到右括号，栈必须非空且栈顶是左括号
            if (st.empty() || st.top() != '(') {
                return false;  // 不匹配
            }
            st.pop();  // 匹配成功，弹出左括号
        }
    }
    // 最后栈应该为空，说明全部匹配
    return st.empty();
}

int main() {
    string test1 = "(()())";
    string test2 = "(()";
    cout << test1 << " 是否匹配? " << (isValid(test1) ? "是" : "否") << endl;
    cout << test2 << " 是否匹配? " << (isValid(test2) ? "是" : "否") << endl;
    return 0;
}

运行结果：

(()()) 是否匹配? 是
(() 是否匹配? 否

你可以自己试试 "()(())" 或 "())("。

栈还有哪些厉害的应用？

表达式求值：计算器里输入 1 + 2 * 3，需要把数字和运算符压入栈，按优先级进行计算（逆波兰表达式）。
深度优先搜索（DFS）：在迷宫或图中搜路时，用栈记录走过的路径，可以回溯到上一个岔路口。
函数调用（递归）：当你调用一个函数时，系统会把返回地址、局部变量等信息压入“调用栈”，函数返回时再弹出。递归太深会导致栈溢出（Stack Overflow）。
撤销操作：每次编辑都压栈，撤销时弹出。
浏览器的前进后退：实际上用两个栈配合实现（后退栈+前进栈）。

下一步学什么？

掌握了栈，你可以继续探索：

队列（Queue）：先进先出的结构，比如排队买奶茶。
双端队列（Deque）：两端都能插入删除，更灵活。
优先队列（Priority Queue）：出队时按优先级，比如医院的急诊排序。
单调栈：一种特殊技巧，用于在数组中找“下一个更大元素”等，是信息学奥赛的高频考点。
如何用栈实现队列（面试经典题）。

记住：栈的本质是“后进先出”，凡是需要“最近相关性”或“回溯”的算法，都可以考虑使用栈。

总结

栈是一种遵循 LIFO（后进先出）规则的数据结构。
基本操作：push（入栈）、pop（出栈）、top（查看栈顶）、empty（判空）、size（大小）。
C++ 中用 stack 容器适配器，Python 中用 list 或 collections.deque 模拟。
操作都是 O(1)，效率极高。
常见错误：空栈时 pop 或 top；混淆栈和队列。
经典应用：括号匹配、表达式计算、撤销/后退、DFS。

现在，去写几个小程序练练手吧！比如：用栈把十进制数转换成二进制数（不断除以2取余数，最后倒序输出余数，正好用栈实现）。相信你很快就能感受到栈的“后进先出”魔法了！

stack栈适配器——后进先出的“叠盘子”魔法