判断出栈顺序是否正确。

C语言 码拜 6年前 (2015-05-11) 1068次浏览 0个评论

问题描述
给定一个,其中最多存储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

5分
简单的模拟出栈入栈操作,将元素依次入栈。然后根据输入的次序依次出栈。比如给出的出栈次序是 1 4 3 7 6 2 5,首先将1入栈,发现输入数据中的第一个正好是1。将1出栈,下面是4,由于栈是空,并且刚才只把1入栈,接下来将2 3 4依次入栈,些时栈顶元素是4,与输入数据的第二个元素相等,将4出栈。然后3出栈,接下来处理7,由于此时栈顶元素是2,7大于2所以接下来将5 6 7依次入栈(栈中元素为7 6 5 2)。然后栈顶元素与输入数据的7比较相等,7出栈,然后6也相等,6出栈。此时栈中元素(5 2),待判断的输入数据为2 5。2与栈顶元素比较2<5,所以这个序列是不可能出栈顺序。
5分
https://www.baidu.com/s?wd=%E5%88%A4%E6%96%AD%E5%87%BA%E6%A0%88%E9%A1%BA%E5%BA%8F+C%E6%BA%90%E4%BB%A3%E7%A0%81&rsv_spt=1&issp=1&f=8&rsv_bp=0&rsv_idx=2&ie=utf-8&tn=baiduhome_pg&rsv_n=2&rsv_sug3=7&rsv_sug1=6&rsv_sug4=262&inputT=7871
10分
奔跑吧,参考:

int N, M, K;
int *Push, *Pop, *Stack;
int i, j, r, s;
int main(void)
{
	scanf("%d%d%d", &M, &N, &K);
	Stack = malloc(sizeof(int)*M);
	Push = malloc(sizeof(int)*N);
	Pop = malloc(sizeof(int)*N);
	//读入压栈序列
	for (i = 0; i < N; i++) scanf("%d", Push + i);
	r = 0;
	while (r < K)
	{
		//读入出栈序列
		for (j = 0; j < N; j++) scanf("%d", Pop + j);
		i = j = 0;
		s = -1;
		while (j < N)
		{
			if (-1 == s || Stack[s] < Pop[j])  //栈若是空的或栈顶元素小于当前出栈元素,则入栈
			{

				if(s < M - 1) Stack[++s] = Push[i++];
				else  //栈空间有限,无法继续入栈
				{
					printf("NO\n");  
					break;
				}
			}
			if (Stack[s] == Pop[j])  //出栈
			{
				s--;
				j++;
			}
			else if (Stack[s] > Pop[j])
			{
				printf("NO\n");
				break;
			}
		}
		if (j == N) printf("YES\n");  //全部都可以出栈,则序列正确
		r++;
	}
	free(Push);
	free(Pop);
	free(Stack);
	return 0;
}
20分
直接比对,不等的部分压栈,就知道结果

#include <stdio.h>
#define N (1000+10)
int n,m,k, a[N],b[N],sk[N];
bool check(){
    int top =0,*pa=a,*pae=a+n,*pb=b,*pbe=b+n;
    while(pb!=pbe){
        if(pa<pae&&*pb==*pa) {
            if(top==m) return false;
            ++pb,++pa;
        }
        else if(top&&*pb==sk[top-1]) ++pb,--top;
        else if(pa<pae) {
            if(top==m) return false;
            sk[top++]   =*pa++;
        }else return false;
    }
    return true;
}

int main ()
{
   scanf("%d%d%d",&m,&n,&k);
   for(int i=0;i<n;i++) scanf("%d",a+i);
   while(k--){
        for(int i=0;i<n;i++) scanf("%d",b+i);
        printf("%s\n",check() ? "YES" : "NO");
   }
}

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明判断出栈顺序是否正确。
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!