栈stack的用法

stack 是什么？

stack 是 栈，一种 后进先出（LIFO） 的数据结构。

类比：一摞盘子

• 只能从 顶部 放
• 只能从 顶部 取

---

需要的头文件

#include <stack>

通常还会配合：

#include <iostream>
using namespace std;

---

定义一个栈

stack<int> st;        // 存 int
stack<string> st2;   // 存 string

stack<T> 中的 T 可以是任意类型。

---

常用成员函数（核心）

函数	作用
st.push(x)	入栈
st.pop()	出栈（不返回值）
st.top()	访问栈顶元素
st.empty()	是否为空
st.size()	元素个数

注意：

• pop() 不会返回元素
• 取元素用 top()

---

基本示例

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

int main() {
    stack<int> st;

    st.push(1);
    st.push(2);
    st.push(3);

    cout << st.top() << endl; // 3

    st.pop();                // 弹出 3
    cout << st.top() << endl; // 2

    cout << st.size() << endl; // 2

    return 0;
}

输出：

3
2
2

---

遍历 stack（常见坑）

stack 不能直接遍历（没有迭代器）

✅ 正确方式：边弹边访问

while (!st.empty()) {
    cout << st.top() << " ";
    st.pop();
}

这会 清空栈

---

安全使用（必须判断）

错误写法（可能崩溃）：

cout << st.top(); // 如果栈为空

正确写法：

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

---

stack 的底层实现（了解）

stack<int> st;

默认底层是：

deque<int>

你也可以指定：

stack<int, vector<int>> st;

但 99% 不需要关心

---

常见应用场景（非常重要）

1. 括号匹配

stack<char> st;
for (char c : s) {
    if (c == '(') st.push(c);
    else {
        if (st.empty()) return false;
        st.pop();
    }
}

2. 单调栈（竞赛必考）

stack<int> st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.top()] > a[i]) {
        st.pop();
    }
    st.push(i);
}