P4830 出栈序列（入门）

解题思路

第一步，想清楚什么才是"合理"的出栈顺序。 有5个不同的整数，按读入的顺序一个接一个地压进栈里。不过程序可以"边进边出"：压进几个之后，先让栈顶的元素弹出，再继续压后面的。题目给的出栈顺序，必须能够真的按照这样的过程发生，才算"合理"。

第二步，用一个真实的栈来"演一遍"。 我们把题目给出的可能出栈顺序记到数组 b 里，用变量 j 指向 b 中当前要出的是第几个。然后按照入栈顺序，把数字一个个压进栈 st。每压进一个数字，就检查一下：栈顶是不是正好等于 b[j]？如果是，就弹出栈顶，同时 j 加1；因为弹出后栈顶又会变成新元素，所以要循环检查，直到栈顶不再匹配为止。

第三步，举个具体的例子。 入栈顺序是 3 6 2 5 4，目标出栈顺序是 2 6 3 5 4。先压入3、6、2，这时栈顶是2，正好等于目标里的第一个数2，弹出；栈顶变成6，等于目标的第二个数6，弹出；栈顶变成3，等于第三个数3，弹出。接着压入5、弹出5，压入4、弹出4。五个数全部弹出，所以输出 yes。

第四步，想想为什么这样判断是对的。 栈的特点就是"后进先出"，只有栈顶的元素才能弹出。我们只在栈顶恰好等于目标数字时才弹出，绝不跳着弹，所以模拟出来的就是真实的进出栈过程。只要目标顺序能从头到尾全部弹出，就说明它确实可以实现；如果最后 j 没有数到5，就说明中途卡住了，输出 no。边界情况：如果弹出的数字在栈里根本找不到（比如想弹出还没压进去的数），程序也会自然失败。

参考代码

// 出栈序列：模拟入栈过程，验证给出的出栈顺序是否合法
#include <iostream>
using namespace std;

int main() {
    int a[10], b[10], st[10];
    int i;
    // 读入5个入栈数字和5个期望出栈数字
    for (i = 0; i < 5; i++) cin >> a[i];
    for (i = 0; i < 5; i++) cin >> b[i];
    int top = 0;  // 栈顶指针，st[top]是栈顶元素
    int j = 0;    // 已匹配好的出栈数字个数
    for (i = 0; i < 5; i++) {
        st[top++] = a[i];  // 按读入顺序入栈
        // 栈顶正好是要出栈的数字就不断弹出
        while (top > 0 && st[top - 1] == b[j]) {
            top--;
            j++;
        }
    }
    // 全部5个数字都按顺序出栈，说明序列合法
    if (j == 5) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}

复杂度分析

本题固定是5个整数，每个数字最多压入栈一次、弹出栈一次，所以只需要常数次操作，时间复杂度是 O(1)，空间上栈的大小也固定是5个格子，空间复杂度 O(1)。如果把题目推广到 n 个数字，那么每个数字同样最多入栈出栈各一次，时间复杂度就是 O(n)，空间复杂度 O(n)。