之前我们对栈已经有所了解，先进后出，后进先出这是栈的两大特性，那么，我们经常会碰到这种题，例：

有一组元素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;}

由于系统的栈是现成的，我们可以直接拿来使用，这样问题大大简化，具体的实现步骤过程，代码中也有注释，简单易懂。