登录以参加训练计划

Stack（栈） 是 C++ STL 中最基础、最重要的容器之一。它的特点非常鲜明：后进先出（LIFO, Last In First Out）。

就好比你往盒子里放书，先放进去的压在最底下，最后放进去的在最上面。拿书的时候，必须先拿最上面的（最后放进去的）。

下面我为你总结一下 stack 的用法、常用函数以及在竞赛中的注意事项。

---

1. 头文件与定义

要使用栈，你需要引入头文件：

#include <stack>
// 或者直接用万能头文件
#include <bits/stdc++.h> 

定义方式： stack<类型> 变量名;

stack<int> s;       // 定义一个存整数的栈
stack<char> op;     // 定义一个存字符的栈
stack<string> name; // 定义一个存字符串的栈

---

2. 常用成员函数（必须背下来）

stack 的操作非常少，但都很关键。所有操作的时间复杂度均为 $O(1)$。

函数名	写法示例	功能说明	注意事项
push	s.push(x)	入栈：将元素 x 放到栈顶。	栈的大小会 +1。
pop	s.pop()	出栈：删除栈顶元素。	不返回值！ 仅仅是删除。如果栈空时调用会报错（RE）。
top	s.top()	取栈顶：返回栈顶元素的引用。	不删除元素！ 仅仅是查看。如果栈空时调用会报错（RE）。
empty	s.empty()	判空：如果栈为空返回 true，否则 false。	常用在循环条件中。
size	s.size()	大小：返回栈内元素的个数。	返回类型是 size_t (无符号整数)。

---

3. 代码演示

下面这段代码演示了栈的完整生命周期：

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;

    // 1. 入栈 (Push)
    s.push(10);
    s.push(20);
    s.push(30); 
    // 此时栈的结构（从底到顶）：10 -> 20 -> 30

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

    // 2. 查看栈顶 (Top)
    cout << "栈顶元素是: " << s.top() << endl;    // 输出 30

    // 3. 出栈 (Pop)
    s.pop(); // 删掉 30
    // 此时栈的结构：10 -> 20

    cout << "弹出一个后，栈顶元素是: " << s.top() << endl; // 输出 20

    // 4. 遍历并清空栈
    // 栈不支持 s[i] 也不支持迭代器遍历，只能一边弹一边看
    cout << "依次弹出剩余元素: ";
    while (!s.empty()) {        // 只要栈不为空
        cout << s.top() << " "; // 先看
        s.pop();                // 再删
    }
    cout << endl;

    return 0;
}

---

4. 竞赛中的“坑”与注意事项

(1) pop() 和 top() 的致命错误

这是新手最容易犯的错误：在栈为空的时候调用 pop() 或 top()。 这会导致 Runtime Error (RE)，也就是程序崩溃。

错误写法：

stack<int> s;
cout << s.top(); // ❌ 崩溃！因为栈是空的
s.pop();         // ❌ 崩溃！没东西可删

正确写法（养成好习惯）： 在调用这两个函数前，除非你非常确定栈里有东西，否则一定要先检查 !s.empty()。

if (!s.empty()) {
    cout << s.top();
    s.pop();
}

(2) 不支持随机访问

栈不能像数组那样通过下标 s[i] 访问中间的元素，也没有迭代器。 你只能看到“栈顶”，想看下面的？必须先把上面的扔掉（pop）。

(3) pop 不返回值

在 Python 或 Java 中，pop() 可能会返回被删除的元素。但在 C++ STL 中，pop() 返回类型是 void。 如果你想“取出并删除”，必须分两步走：

int x = s.top(); // 1. 取值
s.pop();         // 2. 删除

---

5. 经典应用场景（刷题指南）

当你遇到以下几类题目时，第一时间要想到用 Stack：

1. 括号匹配：比如判断 (([])) 是否合法。遇到左括号入栈，遇到右括号看栈顶是否匹配。
2. 表达式求值：比如你刚才问的 1+2*3，还有后缀表达式（逆波兰表达式）计算。
3. 单调栈 (Monotonic Stack)：找“右边第一个比我大/小的数”。这是提高组/面试的高频考点（如接雨水问题、柱状图中最大的矩形）。
4. DFS（深度优先搜索）的模拟：递归本质上就是系统帮你维护了一个栈，有时候为了防止爆栈（Stack Overflow），我们会手写 stack 来模拟递归过程。
5. 浏览器/编辑器的后退功能：典型的后进先出。

总结

• 特性：后进先出 (LIFO)。
• 核心：push, pop, top, empty。
• 警告：空栈操作必 RE。
• 复杂度：全是 $O(1)$。