栈

栈遵循后进先出（LIFO）：只能在栈顶插入、删除。push 入栈，pop 弹栈，top 查看栈顶；在非空前提下基本操作均为 O(1)。std::stack 是容器适配器，默认底层容器为 deque。

括号匹配

左括号入栈，遇到右括号时检查栈顶是否是对应左括号。嵌套的左括号最后出现却最先匹配，正好符合 LIFO。扫描结束时栈必须为空；调用 top 或 pop 前必须先判断 empty()。

bool valid(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty()) return false;
            char t = st.top(); st.pop();
            if ((c == ')' && t != '(') || (c == ']' && t != '[') ||
                (c == '}' && t != '{')) return false;
        }
    }
    return st.empty();
}

后缀表达式

从左到右读取后缀表达式：数字入栈；遇到运算符时弹出右操作数再弹出左操作数，计算后将结果入栈。最后栈顶即结果。注意减法、除法的操作数顺序不能颠倒。

// token 为数字或 + - * /
int b = st.top(); st.pop();
int a = st.top(); st.pop();
st.push(a + b);  // 按运算符改为对应计算

单调栈

求右侧第一个更大元素时，从左到右维护值单调递减的下标栈；当前值大于栈顶值时，当前下标就是被弹出元素的答案。每个下标最多入栈、出栈一次，总时间 O(n)。类似方法可求最近更小值、接雨水和柱状图最大矩形。