栈
后进先出的线性表

#include <iostream>
using namespace std;
const int MAXN = 6;
int st[MAXN];
int top = 0;                  // top 指向"下一个可插入位置"，同时就是元素个数

void push(int x) {
    if (top == MAXN) { cout << "栈满（溢出）！" << endl; return; }
    st[top++] = x;            // 入栈：放到 top 位置，top 上移
}
void pop() {
    if (top == 0) { cout << "栈空！" << endl; return; }
    top--;                    // 出栈：top 下移（原位置的数据不用管）
}
int main() {
    push(1); push(2); push(3); push(4);      // top = 4
    pop(); pop();                            // 4、3 出栈，top 回到 2
    push(5); push(6); push(7); push(8);      // 复用空位，top 回到 6
    push(9);                                 // 只有 top==MAXN 时才真的满了
    return 0;
}

#include <iostream>
using namespace std;
const int MAXN = 1005;
int st[MAXN], top = 0;        // top 既是"下一个可插入位置"，也是元素个数

bool empty() { return top == 0; }        // 判空
bool full()  { return top == MAXN; }     // 判满
int  size()  { return top; }             // 元素个数（直接就是 top！）
int  peek()  { return st[top - 1]; }     // 取栈顶元素（注意要 -1）

void push(int x) {
    if (full()) { cout << "Stack Full!\n"; return; }
    st[top++] = x;                       // 先放后加
}
void pop() {
    if (empty()) { cout << "Stack Empty!\n"; return; }
    top--;                               // 只需下移，原值下次会被覆盖
}

int main() {
    push(10); push(20); push(30);
    cout << peek() << endl;                  // 30
    pop();
    cout << peek() << " " << size() << endl; // 20 2
    push(40);
    cout << size() << endl;                  // 3
    while (!empty()) { cout << peek() << " "; pop(); }
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> s;
    s.push(10); s.push(20); s.push(30);     // 依次压栈
    cout << s.top() << " " << s.size() << endl;   // 栈顶 30，共 3 个
    s.pop();                                // 弹出栈顶（不返回元素！）
    cout << s.top() << " " << s.size() << endl;   // 20 2
    while (!s.empty()) {                    // 遍历栈的唯一方式：边取边弹
        cout << s.top() << " ";
        s.pop();
    }
    return 0;
}

#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool match(char a, char b) {                 // a 是栈顶左括号，b 是当前右括号
    return (a == '(' && b == ')') || (a == '[' && b == ']');
}
int main() {
    string str;
    cin >> str;
    stack<char> s;
    bool ok = true;
    for (int i = 0; i < (int)str.size(); i++) {
        char c = str[i];
        if (c == '(' || c == '[') s.push(c);           // 左括号：入栈
        else {
            if (s.empty() || !match(s.top(), c)) {     // 没得配 或 类型不符
                ok = false; break;
            }
            s.pop();                                   // 配对成功：弹出栈顶
        }
    }
    if (!s.empty()) ok = false;                        // 还有没配完的左括号
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
    string t;
    stack<int> s;
    while (cin >> t) {                       // 后缀表达式，以 @ 结束
        if (t == "@") break;
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = s.top(); s.pop();        // 先弹出的是右操作数，顺序不能反
            int a = s.top(); s.pop();        // 后弹出的是左操作数
            if (t == "+") s.push(a + b);
            else if (t == "-") s.push(a - b);
            else if (t == "*") s.push(a * b);
            else s.push(a / b);
        } else {                             // 数字：转成整数后入栈
            int x = 0;
            for (int i = 0; i < (int)t.size(); i++)
                x = x * 10 + (t[i] - '0');
            s.push(x);
        }
    }
    cout << s.top() << endl;                 // 最后栈中只剩答案
    return 0;
}

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int pri(char c) {                            // 优先级：乘除 2，加减 1，左括号 0
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;
}
int main() {
    string s, out;
    cin >> s;
    stack<char> op;
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        if (c >= '0' && c <= '9') out += c;                  // 数字：直接输出
        else if (c == '(') op.push(c);                       // 左括号：入栈
        else if (c == ')') {                                 // 右括号：一直弹到左括号
            while (!op.empty() && op.top() != '(') { out += op.top(); op.pop(); }
            op.pop();                                        // 左括号弹出但不输出
        } else {                                             // 运算符：先弹出优先级 >= 自己的
            while (!op.empty() && pri(op.top()) >= pri(c)) { out += op.top(); op.pop(); }
            op.push(c);
        }
    }
    while (!op.empty()) { out += op.top(); op.pop(); }       // 剩余运算符全部输出
    cout << out << endl;
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;
// 递归的每一次调用，本质就是一次"入栈"；每一次返回，就是一次"出栈"
int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);          // 先算 fact(n-1)，本层调用被压在系统栈里
}
// 用显式栈把上面这段递归改写成非递归
int fact_stack(int n) {
    stack<int> s;
    while (n > 0) { s.push(n); n--; }                 // "递"：一路压栈
    int ans = 1;
    while (!s.empty()) { ans *= s.top(); s.pop(); }   // "归"：一路弹栈
    return ans;
}
int main() {
    cout << fact(5) << " " << fact_stack(5) << endl;
    return 0;
}

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    // 写法一：vector 也能当栈用，而且能随时查看、遍历栈里的元素
    vector<int> v;
    v.push_back(1); v.push_back(2);
    cout << v.back() << " " << v.size() << endl;   // 2 2
    v.pop_back();
    cout << v.back() << endl;                      // 1

// 写法二：单调栈 —— 求每个数右边第一个比它大的数（CSP-S 内容，仅作了解）
    int a[5] = {2, 1, 4, 3, 5}, n = 5, ans[5];
    stack<int> s;                                  // 栈里存下标，对应的值单调递减
    for (int i = 0; i < n; i++) ans[i] = -1;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && a[s.top()] < a[i]) {  // 栈顶被当前数"打败"
            ans[s.top()] = a[i];
            s.pop();
        }
        s.push(i);
    }
    for (int i = 0; i < n; i++) cout << ans[i] << " ";
    cout << endl;
    return 0;
}