已知入栈顺序,求可能的出栈序列

进栈序列为e1,e2,e3,e4则可能出栈序列是

一个正确的出栈序列: e2 e4 e3 e1

解释:
e1 ,e2 先进栈 然后e2退栈

然后e3  e4在进栈然后 e4 e3 e1在退

则最后结果是e2 e4 e3 e1

按一次进入的个数来进行分类

至少有14种。

① 全进之后再出情况，只有1种：e4，e3，e2，e1

② 进3个之后再出的情况，有3种，e3,e4,e2,e1  e3,e2,e4,e1  e3,e2,e1,e4

③ 进2个之后再出的情况，有5种，e2,e4,e3,e1   e2,e3,e4,e1   e2,e1, e3,e4  e2,e1,e4,e3  e2,e1,e3,e4

④ 进1个之后再出的情况，有5种，e1,e4,e3,e2  e1,e3,e2,e4  e1,e3,e4,e2  e1,e 2,e3,e4  e1,e2,e4,e3