出栈序列(栈和队列)

出栈序列(栈和队列)

时间: 1ms        内存:128M

描述:

已知自然数1,2,...,N(1≤N≤10000)依次入栈(即a<b当且仅当a先于b入栈),问:序列C1,C2,...,CN是否为可能的出栈序列。
  例如:N=5时,3,4,2,1,5是一个可能的出栈序列,因为其可以按如下操作获得:push 1,push 2,push 3,pop,push 4,pop,pop,pop,push 5,pop

输入:

 输入数据包含若干组测试样例。
  每组测试样例的第一行为整数N(1≤N≤10000);
  第二行为N个正整数,以空格隔开,为出栈序列;
  输入数据的末尾以一个0表示输入的结束。

输出:

对于每组测试样例,输出结果为一行字符串。
  如给出的序列是可能的出栈序列,则输出"Yes",否则输出"No"。
  注意:区分大小写,引号本身不输出。

示例输入:

5
3 4 2 1 5
5
3 5 1 4 2
0

示例输出:

Yes
No

提示:

参考答案(内存最优[752]):

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 200
typedef struct{
	int *base;
	int *top;
	int stacksize;
}Stack;
void Initstack(Stack *S){
	S->base=malloc(sizeof(int)*MAXSIZE);
	S->top=S->base;
	S->stacksize=MAXSIZE;
}
void Push(Stack *S,int e){
	*(S->top++)=e;
}
int Empty(Stack *s){
	if(s->base==s->top)
		return 1;
	return 0;
}
void GetTop(Stack *S,int *e){
	*e=*(--S->top);
}
void ClearStack(Stack *S){
	S->top=S->base;
}
int main()
{
	int n,j,k,e,a,flag;
	Stack s;
	Initstack(&s);
	while(scanf("%d",&n),n){
		flag=1;
		for(k=1;k<=n;k++){
			scanf("%d",&a);
			if(Empty(&s)){//empty
				for(j=k;j<a;j++)
					Push(&s,j);
			}
			else{//un emtpy
				GetTop(&s,&e);
				if(e!=a)
					if(e>a)
						flag=0;
					else
						Push(&s,e);
			}
		}
		if(flag)
			printf("Yes\n");
		else
			printf("No\n");
		ClearStack(&s);
	}
	return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 200
typedef struct{
	int *base;
	int *top;
	int stacksize;
}Stack;
void Initstack(Stack *S){
	S->base=malloc(sizeof(int)*MAXSIZE);
	S->top=S->base;
	S->stacksize=MAXSIZE;
}
void Push(Stack *S,int e){
	*(S->top++)=e;
}
int Empty(Stack *s){
	if(s->base==s->top)
		return 1;
	return 0;
}
void GetTop(Stack *S,int *e){
	*e=*(--S->top);
}
void ClearStack(Stack *S){
	S->top=S->base;
}
int main()
{
	int n,j,k,e,a,flag;
	Stack s;
	Initstack(&s);
	while(scanf("%d",&n),n){
		flag=1;
		for(k=1;k<=n;k++){
			scanf("%d",&a);
			if(Empty(&s)){//empty
				for(j=k;j<a;j++)
					Push(&s,j);
			}
			else{//un emtpy
				GetTop(&s,&e);
				if(e!=a)
					if(e>a)
						flag=0;
					else
						Push(&s,e);
			}
		}
		if(flag)
			printf("Yes\n");
		else
			printf("No\n");
		ClearStack(&s);
	}
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注