PAT甲级1051

题目描述

Given a stack which can keep $M$ numbers at most. Push $N$ numbers in the order of $1, 2, 3, . . ., N$ and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if $M$ is $5$ and $N$ is $7$ , we can obtain $1, 2, 3, 4, 5, 6, 7$ from the stack, but not $3, 2, 1, 7, 5, 6, 4$ .

Input Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO

思路分析

题目大意是给定一个序列，判断这个序列是否是一个pop sequence，不同的是题目还对栈的大小做出了限制。我们不妨直接模拟进栈、出栈的过程。而模拟的依据就是栈顶元素和输入序列中元素的大小关系。我们使用std::stack<int>作为模拟栈，设置一个索引指针curr指向输入序列中当前正在判断的元素，并将此元素称为当前元素。因而，栈顶元素与当前元素的关系无非以下几种：

栈顶元素＜当前元素且此时栈未满，则从序列 $1, 2, 3, . . ., N$ 中顺序取出一个元素入栈。
栈顶元素＝当前元素。此时可判定该元素是合法的，直接将栈顶元素出栈，同时curr后移一位，继续判断下一个元素。
栈顶元素＞当前元素或栈顶元素＜当前元素且栈已满。则可直接判定此输入序列不是一个pop sequence

另外需要注意的是，一开始栈空时也要从 $1, 2, 3, . . ., N$ 中顺序取出一个元素入栈。搞清楚以上过程，程序就不难写了。

C++ 程序

#include <iostream>
#include <stack>

int main() {
    int M, N, K;
    scanf("%d%d%d", &M, &N, &K);
    int p[1001];

    for (int i = 0; i < K; ++i) {
        std::stack<int> s;
        for (int j = 0; j < N; ++j) scanf("%d", p + j);
        int curr = 0, is_legal = 1, number = 0;
        while (curr < N && number <= N) {
            if (s.empty() || (s.top() < p[curr] && s.size() < M))
                s.push(++number);
            else if (s.top() == p[curr]) {
                ++curr;
                s.pop();
            } else {
                is_legal = 0;
                break;
            }
        }
        is_legal ? printf("YES\n") : printf("NO\n");
    }
    return 0;
}