stack 栈

读完能做什么

• 能创建 stack，用 push 压入、top 看栈顶、pop 弹出，并说出每一步之后栈里还剩哪些元素。
• 能按后进先出的顺序预测一组数的取出顺序，并说出每一步之后 size() 是多少。
• 能解释 top() 和 pop() 的区别，知道访问栈顶和弹出之前要先判断栈非空。
• 能说出 stack 是容器适配器、没有迭代器，所以不能像 vector 那样遍历。

为什么需要它

有些事情的顺序是“最后做的先撤销”：叠起来的盘子只能从最上面拿，输入框里的撤销只能撤掉最近一次操作。这种“最后放入的最先取出”的规则，用一个数组也能模拟：

int a[1005];
int top = 0;                 // top 是"下一个空位"的下标

a[top++] = 10;               // 压入：写在 top 位置，top 后移
cout << a[--top] << '\n';   // 弹出：top 前移，再读那个位置

这段片段（省略了头文件和 main）没有语法错误，但有几个麻烦：数组长度写死了，top 得自己记得更新，压多了还会越界。我们需要一个把这些细节都包好的工具，这就是 stack。

它是什么

一句话：stack 是后进先出的容器——元素只能从同一端加入、从同一端取出，最后放进去的最先被取出。这个规则的英文缩写是 LIFO（Last In First Out）。

用叠盘子建立直觉：

     栈顶（top） →  30   ← 最后压入，最先取出
                   20
     栈底        →  10   ← 最先压入，最后取出

栈顶与栈底。 只有栈顶那一端能进能出，栈底是封住的。想知道“下一个被取出的是谁”，看栈顶就够了。

容器适配器。 stack 自己没有重新实现存储，它拿一个现成的容器（默认是 deque，一种两端都能高效增删的容器）当底座，只把允许的操作重新包装一遍：push 就是往底座一端加元素，pop 就是删掉底座那一端的元素。所以它叫“适配器”——把底座的接口适配成栈需要的接口。代价是它只开放栈顶这一端，你没法跳到栈中间去。

没有迭代器。 迭代器是“指向容器中某个位置的游标”：begin() 给出第一个元素的位置，end() 给出最后一个元素后面一个位置，两个位置一起表示一段区间。stack 故意不提供 begin()、end()，因为栈只允许在栈顶操作——没有游标，也就没法从中间访问，不能像 vector 那样遍历。

模板尖括号。 stack<int> 里的 <int> 表示栈里放什么类型的数据，stack<char> 就是存字符的栈。

stack 对外提供的操作很少，本页用到的就是这五个：

使用时要 #include <stack>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

最小可运行示例

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;                            // 一个空的栈

    st.push(10);                              // 压入栈顶
    st.push(20);
    st.push(30);

    cout << "size = " << st.size() << '\n';
    cout << "top = " << st.top() << '\n';     // 只看栈顶，不取走
    cout << "看完 top 之后 size = " << st.size() << '\n';
    return 0;
}

输出：

size = 3
top = 30
看完 top 之后 size = 3

逐行看：

• stack<int> st; 创建一个空的整数栈，此时 size() 是 0。
• 三次 push 依次把 10、20、30 压到栈顶。最后压入的是 30，所以栈顶是 30。
• st.top() 读栈顶，得到 30。
• top() 只是“看”，不会把元素拿走，所以 size() 仍然是 3。

一步步看变化

依次压入 10、20、30，然后每次都先打印 top() 再 pop()。下表里栈按“左 = 栈底，右 = 栈顶”写：

第 4～6 步的打印结果连起来就是 30 20 10，正好和压入顺序相反。对应的完整程序：

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;
    st.push(10);
    st.push(20);
    st.push(30);

    cout << "取出顺序：";
    while (!st.empty()) {
        cout << st.top() << ' ';              // 先读栈顶
        st.pop();                             // 再弹出它
    }
    cout << '\n';
    cout << "全部弹出后 size = " << st.size() << ", empty = " << st.empty() << '\n';
    return 0;
}

输出：

取出顺序：30 20 10 
全部弹出后 size = 0, empty = 1

几点说明：

• while (!st.empty()) 是处理栈的标准写法：只要栈里还有元素，就取出栈顶处理掉。
• 每次循环里都是先 top() 取值、再 pop() 删除，两步分开写。因为 pop() 不返回被删掉的元素，取值和删除必须自己分成两步。
• 全部弹出后 size() 是 0，empty() 打印成 1（布尔值默认输出 0/1）。空栈上不能再调用 top()。

逐项扩展核心操作

读取栈顶不等于删除栈顶

top() 只读，读多少次栈都不变；pop() 才真的把栈顶拿走：

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;
    st.push(10);
    st.push(20);

    cout << "top = " << st.top() << '\n';     // 读一次
    cout << "再读一次 top = " << st.top() << '\n';
    cout << "读两次之后 size = " << st.size() << '\n';

    st.pop();                                 // 这才真的把栈顶取走

    cout << "pop 之后 top = " << st.top() << ", size = " << st.size() << '\n';
    return 0;
}

输出：

top = 20
再读一次 top = 20
读两次之后 size = 2
pop 之后 top = 10, size = 1

两次 top() 都得到 20，size() 也一直是 2；pop() 之后栈顶变成 10，size() 变成 1。要取值就先 top()，要删除才 pop()，顺序反了就会丢掉想用的值。

数据从输入进来：用栈反转一组数

栈的数据常常是先读进来、再按相反顺序处理。下面读入 5 个数，用栈把它们反过来输出：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;                                 // 数据个数

    stack<int> st;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        st.push(x);                           // 一个个压进去
    }

    cout << "反转输出：";
    while (!st.empty()) {
        cout << st.top() << ' ';
        st.pop();
    }
    cout << '\n';
    return 0;
}

输入：

5
1 2 3 4 5

输出：

反转输出：5 4 3 2 1 

数据按 1 2 3 4 5 的顺序压入，栈顶是最后压入的 5，所以取出的顺序是 5 4 3 2 1。栈只改变“什么时候取”，不改变“取哪个”——它总是取栈顶那个。

空栈不能取栈顶、不能弹出

// 错误示例：空栈没有栈顶，也没有元素可弹出，下面这段的运行结果不确定
#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;                            // st 是空的

    cout << st.top() << '\n';                 // 空栈取栈顶，结果不确定
    st.pop();                                 // 空栈弹出，结果不确定
    return 0;
}

这段能编译通过，但运行结果不确定：空栈调用 top() 和 pop() 是未定义行为，程序可能打印出垃圾值，也可能崩溃。所以每次取栈顶之前先用 st.empty() 或 st.size() == 0 判断，就像上一节的 while (!st.empty()) 那样。

适配器没有迭代器

// 错误示例：stack 是容器适配器，不提供迭代器，下面这段不能通过编译
#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;
    st.push(10);

    for (auto it = st.begin(); it != st.end(); it++) {   // stack 没有 begin()/end()
        cout << *it << '\n';
    }
    return 0;
}

这段编译不过：stack 没有 begin() 和 end()。这是适配器的设计意图——栈只允许在栈顶进出，如果还能用游标跳到中间，栈的规则就被破坏了。想看栈里有什么，只能不断 top() 加 pop()（栈会被清空），或者改用 vector / deque 这类能遍历的容器。

用栈判断括号是否配对

“后进先出”最典型的用法是配对检查：每遇到一个左括号就压栈，遇到右括号就和最近的左括号配掉。下面读入一个括号串（string 是标准库的字符串类型，cin >> s 读入一个不含空格的字符串，for (char c : s) 逐个字符遍历，详见 string 字符串）：

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;                                 // 读入一个不含空格的括号串

    stack<char> st;
    bool ok = true;
    for (char c : s) {
        if (c == '(') {
            st.push(c);                       // 遇到左括号，压进去等配对
        } else if (c == ')') {
            if (st.empty()) {                 // 没有左括号可配，直接失败
                ok = false;
                break;
            }
            st.pop();                         // 配掉一个左括号
        }
    }
    if (!st.empty()) ok = false;              // 还有左括号没配上

    cout << (ok ? "匹配" : "不匹配") << '\n';
    return 0;
}

输入：

(()())

输出：

匹配

逐字符看：( 压栈，( 压栈，) 配掉一个，( 压栈，) 配掉一个，) 配掉最后一个。循环结束时栈是空的，所以输出 匹配。如果中途遇到 ) 而栈已经空了（右括号多了），或者循环结束时栈里还剩左括号（左括号多了），都判为不匹配。

什么时候选它、哪里容易错

pop() 没有返回值。 它只负责删除，不告诉你删掉了谁。取值和删除要分两步：先 st.top() 拿到值，再 st.pop() 删掉。写成 int x = st.pop(); 会编译失败。

访问前先判空。 top()、pop() 都要求栈非空，空栈上调用属于未定义行为，不能靠“它应该会给我 0”来猜。养成习惯：if (!st.empty()) { ... }。

读取栈顶不等于删除栈顶。 top() 反复调用，栈的内容不会变；只有 pop() 会改变栈。要“看一眼”就直接 top()，不要用 pop() 代替。

没有下标，也没有迭代器。 st[0]、st.begin()、st.end() 都不存在。想看栈里的内容只能一个个弹出，或者改用 vector / deque。

复杂度。 push、pop、top、empty、size 都是常数时间 O(1)。底层默认容器 deque 在两端增删的代价是摊还常数时间（“摊还”指偶尔一次重新分配比较贵，把开销平摊到很多次操作上，平均仍是常数）。

什么时候用它。 需要“撤销最近一步”、“配对”、“把顺序反过来”、“递归式的深入与回退”时，先想想栈。

选读。 底层容器可以换：stack<int, vector<int>> st; 表示用 vector 当底座。默认的 deque 对栈这种“只在一端进出”的用法已经足够，本页不需要改动它。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

stack<int> st;
st.push(1);
st.push(2);
st.pop();                 // 弹出 2
st.push(3);
st.push(4);
st.pop();                 // 弹出 4

cout << st.top() << ' ' << st.size() << '\n';

第 2 题：修改代码

下面这段片段把 3 个数压入栈后全部弹出。请把它改成：压入 1 2 3 4 5，先输出栈顶，再按后进先出的顺序输出所有元素。

stack<int> st;
st.push(1);
st.push(2);
st.push(3);

while (!st.empty()) {
    cout << st.top() << ' ';
    st.pop();
}
cout << '\n';

验证条件：输出两行，第一行是 top = 5，第二行是 取出顺序：5 4 3 2 1 。先说出循环开始前栈顶是谁、循环结束后 size() 是多少，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;
    st.push(1);
    st.push(2);
    st.pop();                                 // 弹出 2
    st.push(3);
    st.push(4);
    st.pop();                                 // 弹出 4

    cout << st.top() << ' ' << st.size() << '\n';
    return 0;
}

3 2

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;
    for (int x : {1, 2, 3, 4, 5}) st.push(x);

    cout << "top = " << st.top() << '\n';     // 最后压入的 5 在栈顶

    cout << "取出顺序：";
    while (!st.empty()) {
        cout << st.top() << ' ';
        st.pop();
    }
    cout << '\n';
    return 0;
}

top = 5
取出顺序：5 4 3 2 1 

立即练习

两道题都只需要循环、数组和本页讲过的 stack 操作。做完后请说明：为什么这里用栈比用队列更合适？如果换成队列，表达式的计算顺序会变成什么样？