PAT甲级A1051---栈的应用

1051 Pop Sequence (25分)

分析：

使用一个栈来模拟，将1~n依次入栈，在入栈过程中，如果入栈的元素恰好等于出栈序列当前等待出栈的元素，那么就让栈顶元素出栈，同时把出栈序列等待出栈的元素后移一位。此时如果栈顶元素还是等于待出栈元素，继续出栈。
有两种情况一定不合法，一是入栈的元素个数大于栈的最大值m，二是遍历完后栈内还有元素。

C++：

#include <cstdio>
#include <stack>

using namespace std;

const int maxn = 1010;
int arr[maxn];//保存题目给的出栈序列

int main() {
    int m, n, k;
    scanf("%d%d%d", &m, &n, &k);

    for (int i = 0; i < k; i++) {
        stack<int> st;
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
        int pos = 0;
        bool flag = true;
        for (int i = 1; i <= n; i++) {
            st.push(i);
            if (st.size() > m) {
                flag = false;
                break;
            }
            //栈顶元素与出栈序列当前位置的元素相同时
            while (st.empty() == false && st.top() == arr[pos]) {
                st.pop();
                pos++;
            }
        }
        if (st.empty() == true && flag == true) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}