PTA 7-5 出栈序列的合法性 (25 分)

给定一个最大容量为 M 的堆栈，将 N 个数字按 1, 2, 3, ..., N 的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 M=5、N=7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。

输入格式：

输入第一行给出 3 个不超过 1000 的正整数：M（堆栈最大容量）、N（入栈元素个数）、K（待检查的出栈序列个数）。最后 K 行，每行给出 N个数字的出栈序列。所有同行数字以空格间隔。

输出格式：

对每一行出栈序列，如果其的确是有可能得到的合法序列，就在一行中输出YES，否则输出NO。

输入样例：

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

输出样例：

YES NO NO YES NO

提示：可以使用栈做，将1~n顺序入栈，并将栈顶元素同时与出栈序列相比较，相同则出栈。若最后栈空则序列合法，否则序列不合法。 

#include<iostream> #include<stdio.h> #include<stack> using namespace std; int main() { int M,N,K;//M（堆栈最大容量）、N（入栈元素个数）、K（待检查的出栈序列个数） cin >> M >> N >> K; int a[K][N]; for(int i = 0;i < K;i++) { for(int j = 0;j < N;j++) { cin >> a[i][j]; } } int s[K];//1代表YES 0代表NO for(int i = 0;i < K;i++) { stack<int> st1; int index = 0; //出栈序列的下标 for(int j = 1;j<=N;j++) { if(st1.size() < M) { st1.push(j); } else { // 栈满，无法继续入栈 break; } while(!st1.empty()) { if(st1.top()!=a[i][index]) break; else { st1.pop(); index++; continue; } } } if(st1.empty())//栈空，说明可以 { s[i] = 1; } else { s[i] = 0; } } for(int i = 0;i<K;i++) { if(s[i]) cout << "YES" <<endl; else cout << "NO" << endl; } return 0; }