1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805427332562944
给出容量max=M的栈，分别把1、2、…、n依次入栈，并给出一些列出栈顺序，判读判断出栈顺序是否合法。
2.思路
出栈是否合法要满足：（1）能出栈（2）不超过栈的限制容量。
思路：模拟，将1~n依次入栈，在入栈中——如果入栈的元素恰好等于出栈序列当前等待出栈的元素，就让栈顶元素出栈，同时把出栈序列当前等待出栈的元素位置标记后移1位。
——举个栗子：出栈顺序为3 2 1 7 5 6 4时，1入栈，2入栈，3入栈，3出栈，1出栈，4出栈，5入栈，6入栈，7入栈，7出栈，此时栈的顶端元素为5，而序列要求此时6出栈（不可能），所以输出“NO”。
此时只要栈顶元素仍然等于出栈序列当前等待出栈的元素，则持续出栈。
（1）初始化栈，读入需要测试的出栈序列。
——以bool型变量flag表示出栈序列是否合法，若flag==true，则表示出栈序列合法，flag变量的初值为true。
以int型变量current表示出栈序列当前等待出栈的元素位置标记，初值=1；
（2）由于入栈顺序为1~N，因此从1至N枚举i，对于每个i，先将i入栈。如果此时栈内元素数目大于m个，则违反规则，置flag=false，退出循环；
否则，反复判断当前current所指出出栈序列中的元素（即带出栈元素）是否等于栈顶元素，若是，则让该元素出栈，并让current自增以指向下一个待出栈元素。
（3）如果上述操作结束后栈空且flag ==true，则说明出栈顺序合法，输出“YES”，否则输出“NO”。
3.代码
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include <stack> using namespace std; const int maxn=1010; int arr[maxn]; //保存题目给定的出栈序列 stack<int> st; //定义栈st，用以存放int型元素 int main(){ int m,n,T; scanf("%d%d%d",&m,&n,&T); while(T--){ //循环执行T次 while(!st.empty()) { //清空栈 st.pop(); } for(int i=1;i<=n;i++){ scanf("%d",&arr[i]); } int current=1; //指向出栈序列中的待出栈元素 bool flag=true; for(int i=1;i<=n;i++){ st.push(i); //把i压入栈 if(st.size()>m){ //如果此时栈中元素个数大于容量m，则序列非法 flag=false; break; } //栈顶元素与出栈序列当前位置的元素相同时 while(!st.empty()&&st.top()==arr[current]){ st.pop();//反复弹栈并令current++ current++; } } if(st.empty()==true&&flag==true){ printf("YES\n"); //栈空且flag==true时表明合法 }else{ printf("NO\n"); } } return 0; }
4.注意点
（1）题目对栈的大小有限制。
（2）在pop和top操作前记得判空，否则OJ会返回“答案错误”或“段错误”。
（3）步骤3必须判断是否栈空，否则会返回“答案错误”——因为如果在所有元素入栈后无法将所有元素出栈是不合法的。
（4）在每个出栈序列输入前一定要清空栈，否则如果上个出栈序列的结果没有被清空，会影响下个出栈序列的过程。
