点击链接PAT甲级-AC全解汇总

题目：
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:
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output 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
1
2
3
4
5
6

Sample Output:

YES
NO
NO
YES
NO
1
2
3
4
5

题意：
输入三个数，N，M，K，分别代表栈得大小为N，初始入栈序列为1 ~ M，输入K个数列
判断每个数列，是否可能为出栈序列。

这道题是基础得数据结构算法题，一定要独立完成，看了别人得答案再做出来就没有训练的意义了！
如果你现在没有思路，请回去至少通过大半case再来，如果已经有思路了那可以继续看。

我的思路：
思路其实很简单，清晰，就是判断输入得每个数的三种情况，直接输出、入栈、出栈。

注意： 题目给的序列是出栈序列，而不是问 能否用这个大小的栈，输出这个序列。

比如：题目中的例子1 7 6 5 4 3 2，栈的大小是 5

过程：

• 1 入栈，立马出栈（而不是直接输出）
• 2 3 4 5 6 入栈

（ 如果直接输出的话 7是不需要入栈的，但题目是pop sequence，所以7得先入栈，再出栈）

• 7入栈

此时，栈内个数大于5，结果为NO！

我的代码：

#include
using namespace std;

int main()
{
    int N,M,K;
    cin>>N>>M>>K;
    stack<int>my_stack;
    for(int i=0;i<K;i++)
    {
        int sequence[M]={0},index=0,num=1;
        for(int j=0;j<M;j++)cin>>sequence[j];
        while(index<M)
        {
            if(sequence[index]==num) //num不入栈
            {
                index++;
                num++;
            }
            else if(my_stack.size() && sequence[index]==my_stack.top()) //num出栈
            {
                index++;
                my_stack.pop();
            }
            else //num入栈
            {
                my_stack.push(num++);
                if(my_stack.size()>N-1)break;//注意是-1
            }
        }
        if(my_stack.size())cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
        while(my_stack.size())my_stack.pop(); //清空栈
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38