02-线性结构4 Pop Sequence

#include <stdio.h> #include <stdlib.h> /** 手动判定： 对于出栈序列的某写元素，比某一元素早入栈却晚出栈，则该些元素逆序出栈 注意栈的空间有限 程序判定： 根据待测序列，逆推最大空间为M的栈中元素 满足则YES 如果： 1 溢栈 2 未入栈(待测序列中)元素小于栈顶元素 则NO */ int main() { int M, N, K; scanf("%d %d %d",&M,&N,&K); int stack[N],test[N],top,num,j; //用于测试的堆栈不会超过N while(K--) { stack[0]=0; //初始化堆栈，堆顶设为0即可 top=0; //设空堆堆顶为0 num=1; //用于原始序列1~N入栈 j=0; //遍历test[]的标记，如果能成功遍历到N-1，则YES for(int i=0; i<N; i++) { scanf("%d",&test[i]); } while(j<N) { if(stack[top]>test[j]) { //还未入栈的元素test[i]无法成功入栈 break; } while(stack[top]<test[j]) { //test[i]元素还未入栈，需要入栈 stack[++top]=num++; } if(top>M) break; if(stack[top]==test[j]){ top--; //模拟出栈 } j++; } if(j==N) printf("YES\n"); else printf("NO\n"); } return 0; }