栈 Stack 整理笔记

1. 概念
栈是一种运算受限的线性表，只允许在栈顶进行插入和删除操作。
栈顶：允许操作的一端
栈底：不允许操作的一端
特点：后进先出 / 先进后出，简称 LIFO / FILO
可以想象成一摞盘子：最后放上去的盘子，最先被拿走。

---

2. STL 定义

#include <stack>
using namespace std;

stack<int> s;        // 定义一个整型栈
stack<char> st;      // 定义一个字符栈

---

3. 常用函数

函数	作用	返回值
s.push(x)	把 x 压入栈顶	无返回值
s.pop()	删除栈顶元素	无返回值
s.top()	获取栈顶元素	返回栈顶元素
s.empty()	判断栈是否为空	空返回 true
s.size()	返回栈中元素个数	返回元素数量

⚠️ 最易错点：pop() 不返回值！
想取出并删除栈顶元素，必须：

int x = s.top();   // 先取值
s.pop();           // 再删除

不能写：

int x = s.pop();   // ❌ 错误，pop() 没有返回值

---

4. 遍历栈的标准写法

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

---

5. 数组模拟栈
竞赛中有时用数组模拟栈，速度更快：

const int N = 100010;
int stk[N];
int tt = 0;          // 栈顶指针

stk[++tt] = x;       // 入栈
tt--;                // 出栈
int top_val = stk[tt]; // 取栈顶
bool empty = (tt == 0); // 判空

---

6. 常考：出栈序列判断
方法：直接模拟入栈出栈过程
例如入栈顺序为 1 2 3 4 5 6，判断出栈序列 1 3 5 2 4 6 是否合法：
出 1：入 1，出 1 → 栈空
出 3：入 2、3，出 3 → 栈中剩 2
出 5：入 4、5，出 5 → 栈中剩 2、4
出 2：此时栈顶是 4，2 被压在下面，无法先出
所以这个序列不合法。

---

🧠 记忆口诀
栈顶进，栈顶出；后进先出别记错。
pop 不返回值，取值必须用 top。
判断出栈序列，直接模拟最稳妥。

------------------------------------------------------------------------------------------------------------
相关代码讲解与注释

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

int main() {

    /* ==============================
       1. 栈的基本定义与常用操作
       ============================== */

    stack<int> st;

    st.push(10);   // 入栈，栈：10
    st.push(20);   // 入栈，栈：10 20，20 是栈顶
    st.push(30);   // 入栈，栈：10 20 30，30 是栈顶

    cout << "栈顶元素：" << st.top() << endl;   // 输出 30
    cout << "栈大小：" << st.size() << endl;     // 输出 3

    st.pop();  // 弹出栈顶 30，栈变为：10 20

    cout << "弹出后栈顶：" << st.top() << endl;  // 输出 20
    cout << "是否为空：" << st.empty() << endl;   // 输出 0，表示非空

    /* ==============================
       2. 栈的遍历输出
       注意：栈没有迭代器，只能用 top() + pop() 依次取出
       ============================== */

    while (!st.empty()) {
        cout << st.top() << " ";  // 先取栈顶
        st.pop();                 // 再弹出栈顶
    }
    cout << endl;

    // 输出结果：20 10
    // 因为栈是后进先出，所以输出顺序与入栈顺序相反

    /* ==============================
       3. 输入逆序输出
       这是栈最典型的入门应用
       ============================== */

    int n;
    cin >> n;

    stack<int> st2;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        st2.push(x);   // 依次入栈
    }

    // 依次出栈，就得到输入顺序的逆序
    while (!st2.empty()) {
        cout << st2.top() << " ";
        st2.pop();
    }
    cout << endl;

    /* ==============================
       4. 括号匹配
       遇到左括号入栈，遇到右括号检查栈顶是否匹配
       ============================== */

    string s;
    cin >> s; // 读取字符串

    stack<char> st; // 定义字符栈

    // 1. 遍历字符串中的每一个字符
    for(int i = 0; i < s.size(); i++){
        // 如果碰到左括号 '('，入栈（等待被匹配）
        if(s[i] == '(') {
            st.push('(');
        }
        // 如果碰到右括号 ')'，尝试匹配
        else if (s[i] == ')'){
            if(st.empty()){
                // 栈空说明没有左括号来匹配当前的右括号，直接判定失败
                cout << "NO";
                return 0; // 提前结束程序，不再往下看
            } else {
                // 栈不空，弹出栈顶的左括号，表示成功匹配一对
                st.pop();
            }
        }
        
        // 2. 特殊终止条件：遇到 '@' 立即停止遍历
        if(s[i] == '@') break; 
    }

    // 3. 遍历结束后，检查栈中是否还有残留的左括号
    if(st.empty()) {
        // 栈空，说明所有的左括号都被匹配完了，合法
        cout << "YES";
    } else {
        // 栈不空，说明有左括号落单了，非法
        cout << "NO";
    }

    return 0;
}

    /* ==============================
       5. 数组模拟栈
       竞赛中有时用数组模拟栈，速度更快
       ============================== */

    const int N = 100010;
    int stk[N];
    int tt = 0;   // 栈顶指针，tt == 0 表示栈空

    stk[++tt] = 10;   // 入栈
    stk[++tt] = 20;
    stk[++tt] = 30;

    cout << "数组栈栈顶：" << stk[tt] << endl;   // 输出 30
    tt--;                                       // 出栈
    cout << "出栈后栈顶：" << stk[tt] << endl;   // 输出 20

    if (tt == 0) cout << "栈为空" << endl;
    else cout << "栈非空" << endl;

    return 0;
}