方案
设有一个栈为 s
设有一队列 q,q 存储了要求的 s 中元素出栈的顺序
设有一队列 q_push, 其中存储了元素的入栈顺序
判断栈顶元素是否可以出栈, 若为空, 或者不为空但是栈顶元素不是 q 中当前数据, 则不可以出栈. 否则可以出栈
若栈顶元素可以出栈, 则将其进行出栈, 并将 q 队首元素出队
若栈顶元素不可以出栈, 则在队列 q_push 中元素不为空且不等于 q 的队首元素的情况下, 将 q_push 持续出队, 并将弹出的队首元素都入栈到 s 中.
当循环结束时, q_push 只有空与非空两种可能. 空说明没找到这样一个符合要求的元素, 即出栈队列 q 非法, 程序结束. 若非空, 说明找到了这样一个元素, 回到步骤 4
当循环结束时, 判断 q 是否为空, 若非空, 说明出栈顺序不符合要求, 否则, 是符合要求的.
实例
- 5
- 3 4 2 1 5
- 5
- 3 5 1 4 2
- 0
- /*
- 这里没有很严格的使用前面提到的数据结构, 而是根据题目特性进行了一些变形
- 这样写可读性受到了一点影响, 但是还是可以类比到对应的数据结构上, 而且代码更简洁一些
- */
- #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;
- }
来源: http://www.bubuko.com/infodetail-2851178.html