点击链接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
Sample Output:
YES
NO
NO
YES
NO
题意：
输入三个数，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<bits/stdc++.h>
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;
}