题目来源:oj.hbu.cn
题目描述
已知自然数1,2,...,N(1<=N<=100)依次入栈,请问序列C1,C2,...,CN是否为合法的出栈序列
输入
输入包含多组测试数据。
每组测试数据的第一行为整数N(1<=N<=100),当N=0时,输入结束。
第二行为N个正整数,以空格隔开,为出栈序列。
输出
对于每组输入,输出结果为一行字符串。
如给出的序列是合法的出栈序列,则输出Yes,否则输出No。
样例输入
5
3 4 2 1 5
5
3 5 1 4 2
0
样例输出
Yes
No
/*
这里没有很严格的使用前面提到的数据结构,而是根据题目特性进行了一些变形
这样写可读性受到了一点影响,但是还是可以类比到对应的数据结构上,而且代码更简洁一些
*/
#include<stdio.h>
typedef struct
{
int data[101];
int top;
}stack;
int main(void)
{
int n,a[101],j;
stack s1,s2;
//s1是相当于方案中的队列q_push,这里用了栈进行表示,没有严格的使用队列
//s2是方案中提到的栈
while(scanf("%d",&n) && n!=0)
{
s1.top = s2.top = -1;
for(int i = 0;i < n;i++)
scanf("%d",&a[i]);
for(int i = n;i > 0;i--)
s1.data[++s1.top] = i;
//前面都是初始化操作,算法从这里开始
for(j = 0;j < n;) //这里的j相当于队列q
{
//栈顶元素不符合要求
if(s2.top==-1 || (s2.top!=-1 && s2.data[s2.top]!=a[j]))
{
//出队入栈
while(s1.top!=-1 && s1.data[s1.top]!=a[j])
s2.data[++s2.top] = s1.data[s1.top--];
//判断q_push是否为空,若空则程序结束
if(s1.top!=-1)
s2.data[++s2.top] = s1.data[s1.top--];
else
break;
}
//栈顶元素符合要求
else {
s2.top--;
j++;
}
}
if(j!=n)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}