数据结构267-判断栈输出顺序正确与否

试题名称 判断栈输出顺序正确与否

时间限制: 1 秒

内存限制: 10KB

问题描述

给定一个栈，其中最多存储M个数据。将N个数据以1,2,3,…,N的顺序压栈，然后再随机弹栈。判断一下哪些是有可能的弹栈顺序，而哪些不是。例如M是5，N是7，我们可以得到1, 2, 3, 4, 5, 6, 7的弹栈顺序，而不能得到3, 2, 1, 7, 5, 6, 4这样的弹栈顺序。（M，N<=1000）

输入说明

输入包含了一种情况下的测试数据。在每种情况下，有三组输入数据：

第一组列在首行，包含了三个数据：栈的最大容量M，压栈数据长度N，要验证的弹栈序列个数K。

第二组为压栈数据：N个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。

第三组为K行数据，每行包括了一个需要验证的弹栈序列（含N个数据）。

同行数据间以空格隔开。

输出说明

输出应该包括K行，包行了对每个输入的验证序列，输出的一个判断结果。如果这个弹出序列可能发生，就输出“YES”，否则就输出“NO”。

输入样例

5 7 5

1 2 3 4 5 6 7

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

#include<stdio.h>
#include<stdlib.h>
int main(void){
	int M,N,K;
	int i,j;
	scanf("%d%d%d",&M,&N,&K);
	//定义栈
	int stack[1000];
	int top=-1; 
	//定义数据
	int array[1000]; //N个数据 
	int list[1000];//保存弹栈序列 
	//定义标记位 判断是否正确 0表示错误 1表示正确
	int flag[1000];
	
	//输入N个数据 
	for(i=0;i<N;i++){
		scanf("%d",&array[i]);
	}
	
	//对k组数据进行判断
	for(i=0;i<K;i++){
		//先输入测试数据
		for(j=0;j<N;j++){
			scanf("%d",&list[j]);
		}
		
		int top=-1;//置空栈
		int arrayIndex,listIndex;
		arrayIndex=listIndex=0; 
		//分析：当栈不为空且等于弹栈序列 出栈 弹栈序列向前移动
		//其余情况则入栈(栈满时，无法入栈；所有数据都已入栈，还需入栈时，则无法入栈) 
		//top<M 表示不能超出栈的容量
		//listIndex<N 表示弹栈序列没有弹完
		//arrayIndex<=N 表示栈不为空且入栈数据已入完还需要进行入栈操作 则退出循环 
		while(top<M&&listIndex<N&&arrayIndex<=N){
			if(top!=-1&&stack[top]==list[listIndex]){//栈不为空 且等于弹栈序列  则出栈 
				//printf("出栈元素%d\n",stack[top]); 
				top--;//出栈
				listIndex++; //移动弹栈序列 
			}else{//栈为空 或者不等于栈顶元素 则入栈 
				top++; 
				if(top<M&&arrayIndex<N){//不满则入栈 
					//printf("入栈元素%d\n",array[arrayIndex]); 
					stack[top]=array[arrayIndex];
				} 
				arrayIndex++; 
			}
		}
		//printf("top=%d\n",top);
		if(top==-1){
			flag[i]=1;
		}else{
			flag[i]=0;
		}
	} 

	for(i=0;i<K;i++){
		if(flag[i]==1){
			printf("YES");
		}else{
			printf("NO");
		}
		if(i<K-1){
			printf("\n");
		}
	}
	return 0;
}
/**
5 7 2
1 2 3 4 5 6 7
1 2 3 4 5 6 7
3 2 1 7 5 6 4
*/