之前我们对栈已经有所了解,先进后出,后进先出这是栈的两大特性,那么,我们经常会碰到这种题,例:
有一组元素abcdef,按先后顺序进栈,那么出栈时哪些情况是非法的?
A. fedcba
B. abdcef
C. acbdef
D. abcdef
选哪个呢???
很明显,根据栈的两大特性:先进后出,后进先出,即可判断,答案:C
剖析: 先看C选项acb这样的出栈序列,那么进栈肯定是abc,那么显然出栈时c肯定不会在b之前,就这么简单。用代码实现这个合法性的判断,当然也是比较容易的,只要思路逻辑清楚,就没有问题。
代码如下:
#include<iostream> #include<stack> #include<cassert> usingnamespacestd; boolisLegalSequence(constchar*Push_seq,constchar*Pop_seq) { assert(Push_seq); assert(Pop_seq); //判断出入栈序列长度是否相等 if(strlen(Push_seq)!=strlen(Pop_seq)) returnfalse; stack<char>stk; while(*Push_seq) { //先判断栈是否为空,然后判断栈顶元素是否和出栈序列的元素相同 if(0==stk.size()||stk.top()!=*Pop_seq) { stk.push(*Push_seq++);//不相同就压栈,继续向后找 } else { stk.pop();//找到相同的,出栈 ++Pop_seq;//跳到出栈序列的下一个元素验证 } } while(stk.size())//将剩余的出栈序列元素判断 { if(stk.top()!=*Pop_seq) { returnfalse; } stk.pop(); } returntrue; } intmain() { char*str1="abcdef"; char*str2="baedcf"; cout<<(isLegalSequence(str1,str2)?"yes":"no")<<endl; system("pause"); return0; }
由于系统的栈是现成的,我们可以直接拿来使用,这样问题大大简化,具体的实现步骤过程,代码中也有注释,简单易懂。
本文出自 “Vs吕小布” 博客,请务必保留此出处http://www.jb51.cc/article/p-dladtivm-ms.html