问题很简单:在栈的性质下,1~n的数字按顺序入栈,给出它们的出栈序列,判定该序列是否合理。
相比于之前遇到过的“求解所有可行出栈序列”,本问题的复杂度着实降低了不少。不过要把这个过程正确地通过code模拟出来,在逻辑的处理上也需要注意不少细节。
下面先来讲讲处理的方法:
程序输入:n以及给定的出栈序列,出栈序列不妨设为q[n+1],其中q[1]~q[n]顺序保存正确性未知的出栈序列。
由于入栈是按顺序入栈,可以不用额外的数组保存,仅需要一个递增的标志A表示即可。同时,出栈序列也需要一个指针B来保存当前序列首部q[B]。
同时需要一个栈stk来保存压栈的数字
循环执行以下几步:
(1)比较当前序列首q[B]与A是否相等,相等则表示对当前的入栈数字A来说,它入栈后立即出栈,A自增1,出栈序列指针后移,即B自增1
(2)若不相等,那么转而判断栈顶元素是否和当前出栈序列首部相等,若相等,则栈顶元素出栈,出栈序列指针继续后移。
(3)若(1)(2)都不满足,则判断A是否已经大于n了,大于则不满足出栈条件,并跳出循环,小于等于则将当前数字A压栈,并自增1,转而跳(1)
C++实现代码如下
1 #include<iostream>
2 #include<stack>
3 using namespace std;
4 int n; //输入个数
5 int f[100]; //保存出队序列
6 stack<int> stk;
7 int main(){
8 cin>>n;
9 for(int i=1;i<=n;++i)
10 cin>>f[i];
11 int B=1,A=1; //出队序列指针
12 bool flag=1;
13 while(B<=n){
14 if(f[B]==A){ //直接比较未入栈序列首部与当前序列首部
15 A++;
16 B++;
17 }
18 else if(!stk.empty() && stk.top()==f[B]){ //比较栈顶和首部
19 stk.pop();
20 B++;
21 }
22 else if(A<=n){ //若A还有剩余的元素
23 stk.push(A++);
24 }
25 else{
26 flag=0;break;
27 }
28 }
29 if(flag) cout<<"yes";
30 else cout<<"no";
31 return 0;
32 }
原文链接: https://www.cnblogs.com/HolyShine/p/5518340.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/233777
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!