STL栈的应用|A1051 Pop Sequence

A1051 Pop Sequence

两种方法均要在push时判断栈的size是否超出了Msize。

从所给出栈序列逆向考虑

比较栈顶元素top与当前要出栈的元素temp，curr _max表示当前1到curr_max已经顺序入栈。
边读入出栈序列边处理，

• 若top == temp，出栈
• 若top > temp，judge = false，（但还继续读入）
• 若top < temp，将 curr_max + 1 到 temp 依次入栈，再弹出栈顶的temp

#include <cstdio>
#include <stack>

using namespace std;

int main() {
    int Msize, len_seq, nn;
    scanf("%d%d%d", &Msize, &len_seq, &nn);
    bool judge;
    int temp;
    stack<int> mstack;
    for (int i = 0; i < nn; ++i) {
        judge = true;
        int curr_max = 0;
        for (int j = 0; j < len_seq; ++j) {
            scanf("%d", &temp);
            if (temp > len_seq) judge = false;
            if (judge) {
                int curr_top = mstack.empty() ? 0 : mstack.top();
                if (temp > curr_top) {
                    // push curr_top + 1 ~ temp, then pop the top item (temp)
                    for (int k = curr_max + 1; k < temp; ++k) {
                        mstack.push(k);
                        if (mstack.size() > Msize - 1) {
                            judge = false;
                            break;
                        }
                    }
                    curr_max = temp;
                } else if (temp == curr_top) {
                    mstack.pop();
                } else judge = false;
            }
        }
        puts(judge ? "YES" : "NO");
        while (!mstack.empty()) mstack.pop();
    }
    return 0;
}

正向模拟入栈过程

参考晴神笔记，正向模拟入栈过程，保存出栈序列，当top元素正是出栈序列中正要出栈的元素时，出栈（⚠️这里应当写成循环）。
⚠️while loop的截止、跳出条件
⚠️最后栈应判空
⚠️每次判断后，都应当清空栈，以免干扰下一次判断

#include <cstdio>
#include <stack>

using namespace std;

int main() {
    int Msize, len_seq, nn;
    scanf("%d%d%d", &Msize, &len_seq, &nn);
    bool judge;
    stack<int> mstack;
    for (int i = 0; i < nn; ++i) {
        int seq[1010];
        for (int j = 0; j < len_seq; ++j) {
            scanf("%d", &seq[j]);
        }
        judge = true;
        int curr_pop = 0, curr_push = 1, cnt = len_seq;
        while (judge && cnt--) {
            if (curr_push <= len_seq)
                mstack.push(curr_push++);
            if (mstack.size() > Msize) {
                judge = false;
                break;
            }
            while (!mstack.empty() && mstack.top() == seq[curr_pop]) {
                mstack.pop();
                curr_pop++;
            }
        }
        if (judge && curr_pop == len_seq && mstack.empty())
            puts("YES");
        else puts("NO");
        while (!mstack.empty()) mstack.pop();
    }
    return 0;
}