29 · 栈与队列的应用

中缀表达式难算，是因为读到 + 的时候你还不知道后面有没有 ×：优先级和括号都要“往后看”。后缀表达式把这些决定提前做完了，读到运算符时，它要的两个操作数一定刚好是最近的两个。

“最近的”就是栈顶。于是算法只有三行：数字入栈；运算符弹出两个算一次再压回去；扫完栈里剩一个数。

顺序是关键。先弹出的是右操作数 b，后弹出的是左操作数 a，计算的是 a op b。对 + 和 × 无所谓，对 − 和 ÷ 写反就得到相反数或倒数 —— 这是本节最高频的 WA。

为什么这样是对的。用归纳看不变量：扫过某个前缀之后，栈里从底到顶正好是“这个前缀算出的、还没被合并的中间结果”，并且它们的相对顺序与表达式剩余部分一致。读到一个数：它是新的中间结果，压栈，不变量成立。读到一个运算符：它作用在最近的两个中间结果上，弹两个压一个，正好是它们的合并，不变量仍成立。扫完整个表达式只剩一个中间结果，就是答案。

复杂度 O(n)：每个字符进栈一次或做一次常数运算。长度 10⁵ 的表达式，几百微秒的事。

// 骨架：一个栈包打天下（st 是 stack<long long>，num 是正在攒的数）
while (cin >> c) {
    if (c >= '0' && c <= '9') {
        num = num * 10 + (c - '0');        // 多位数：一位一位攒
    } else if (c == '.') {
        st.push(num); num = 0;             // '.' 是数字结束符，不是小数点
    } else if (c == '@') {
        break;                             // 表达式结束
    } else {                               // + - * /
        long long b = st.top(); st.pop();  // 先弹出的是右操作数
        long long a = st.top(); st.pop();  // 后弹出的是左操作数
        st.push(c == '+' ? a + b : c == '-' ? a - b : c == '*' ? a * b : a / b);
    }
}

给一行字符串（可能含其他字符，忽略），判断其中 ()、[]、{} 三种括号是否配对且嵌套正确。

栈顶就是“最近的、还没被匹配的左括号”。遇到左括号压栈；遇到右括号，它必须和栈顶配对 ——因为括号的配对是后开的先闭，这正是 LIFO。扫描结束时栈必须为空，否则有左括号没闭上。

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

bool check(const string &s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);                       // 左括号：记住它，等待配对
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;     // 右括号多了：没有左括号可以配
            char t = st.top();
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{')) return false;   // 类型不对，嵌套关系被破坏
            st.pop();                          // 配对成功，弹出这一个
        }
    }
    return st.empty();                        // 左括号多了时这里返回 false
}

int main() {
    string s;
    getline(cin, s);
    cout << (check(s) ? "YES" : "NO") << '\n';
    return 0;
}

三个返回点对应三种失败：①栈空却来了右括号（右括号多）；②类型不匹配（嵌套错）；③扫完栈非空（左括号多）。漏掉任何一个，都会把非法串判成合法。

只有一种括号时，其实一个计数器就够了：遇 ( 加一、遇 ) 减一，中途不能为负、最后必须为 0。这是同一个不变式的退化版本。一旦有第二种括号，计数器就不够了 —— 它记不住“该闭的是哪一种”，例如 ([)] 的计数完全合法，但嵌套是错的。

按 1, 2, …, n 的顺序压栈，任意时刻都可以弹栈。给定一个出栈序列，问它是否合法。判断规则只有一条：按入栈顺序逐个压栈，每压一个就检查栈顶是不是出栈序列当前要的元素，是就一直弹；压完全部之后若栈为空，就合法。

为什么这一条规则够：出栈序列的第一个元素是 k，意味着 1…k 都已经压进来过（不压进去弹不出来），而 1…k−1 还压在 k 下面。此时“能弹就弹”不会损失任何选择 —— 早弹掉一个已经可以弹的元素，只是把它从栈顶移走，不改变剩下元素之间的压弹关系。

// 入栈序列固定为 1..n，判断 out[1..n] 是不是合法的出栈序列
bool ok(int n, const vector<int> &out) {
    stack<int> st;
    int p = 1;                              // 下一个还没压进去的数
    for (int i = 1; i <= n; ++i) {
        // 栈顶不是 out[i]，就只能继续压，直到压出它或压完
        while (p <= n && (st.empty() || st.top() != out[i])) st.push(p++);
        if (st.empty() || st.top() != out[i]) return false;   // 压完了还是没有
        st.pop();                           // 栈顶正好是 out[i]，弹掉它
    }
    return true;
}

第 21 节说过：递归靠系统栈，每层压入参数、局部变量和返回地址，深度到 10⁶ 就爆栈 RE。既然栈是显式的概念，就可以自己开一个栈放到堆上，把递归改写成循环 —— 求连通块这种“只关心访问过哪些点、不关心访问顺序”的问题，改完和递归完全等价。

// 网格连通块：从 (sx, sy) 出发，把能走到的 '.' 全部标记
const int N = 1005;
int n, m;
char g[N][N];
bool vis[N][N];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

void floodStack(int sx, int sy) {
    stack<pair<int, int>> st;
    st.push({sx, sy});
    vis[sx][sy] = true;               // ★ 入栈的同时就标记
    while (!st.empty()) {
        auto [x, y] = st.top();       // C++17 结构化绑定
        st.pop();
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (g[nx][ny] != '.' || vis[nx][ny]) continue;
            vis[nx][ny] = true;       // ★ 这里也一样：push 之前标记
            st.push({nx, ny});
        }
    }
}

标记时机是唯一容易错的地方。递归版是“进函数就标记”，显式栈必须在 push 之前标记。如果等 pop 的时候才标记，同一个点会被它的多个邻居各压一次，在 10⁶ 的网格上栈会膨胀到千万级 → MLE 或 TLE。

两者的差别只在访问顺序：递归深度优先地一条路走到黑，显式栈的弹出顺序受入栈顺序影响，遍历次序不同但访问集合相同。所以连通性、可达性这类问题可以随意替换；要求“按字典序输出第一条路径”时不能随便换。

n 个人围成圈编号 1…n，从 1 号开始报数，报到 m 的人出列，下一个人重新从 1 报，求出列顺序。

用队列，队头就是“当前该报数的人”。报 1 到 m−1 的人安全，把他从队头搬到队尾（相当于绕了一圈）；轮到第 m 个人就出队并输出。“搬队头到队尾”这一个动作，就把线性队列变成了环。

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

int main() {
    int n, m;
    cin >> n >> m;
    queue<int> q;
    for (int i = 1; i <= n; ++i) q.push(i);

    while (!q.empty()) {
        // 前 m-1 个人安全：逐个搬到队尾，报数指针自然前移
        for (int k = 1; k < m; ++k) {
            q.push(q.front());
            q.pop();
        }
        cout << q.front() << ' ';      // 第 m 个人出列
        q.pop();
    }
    cout << '\n';
    return 0;
}

n = 10⁴、m = 10⁴ 时最坏要搬 10⁸ 次，勉强能过；n 到 10⁵ 就必须换算法。一个立刻见效的常数优化：当前还剩 s 个人时，搬 s 次就回到原点，所以只搬 (m - 1) % s 次。彻底的做法是把 m 从一开始就模掉，见下面的数学补给。