【1051】Pop Sequence (stack)

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;   
}

  

 

  
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
  
39
  
40
  
41
  
42
 

4.注意点

（1）题目对栈的大小有限制。
（2）在pop和top操作前记得判空，否则OJ会返回“答案错误”或“段错误”。
（3）步骤3必须判断是否栈空，否则会返回“答案错误”——因为如果在所有元素入栈后无法将所有元素出栈是不合法的。
（4）在每个出栈序列输入前一定要清空栈，否则如果上个出栈序列的结果没有被清空，会影响下个出栈序列的过程。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/112553216