出栈序列问题

出栈序列问题

栈之根本——后进先出(Last In First Out,LIFO)

要解决这类问题：最本质就是出栈的时候，可以边入栈边出栈。 考虑：设栈的输入序列是1，2，3则出栈的序列有？

1,2,3 1入栈出栈，2入栈出栈，3入栈出栈

1,3,2 1入栈出栈，2入栈，3入栈出栈，2出栈

2,1,3 1入栈，2入栈出栈，1出栈，3入栈出栈

2,3,1 1入栈，2入栈出栈，3入栈出栈，1出栈

3,2,1 1入栈，2入栈，3入栈出栈，2出栈，1出栈

输入序列有n个数据元素，则出栈的可能序列有:

例如：某个栈的入栈序列是A，B，C，D，E，则可能的出栈序列是：

A、ADBEC

B、EBCAD

C、BCDEA

D、EABCD

对于选项A： A入栈出栈，之后BC入栈，D入栈出栈，选项显示B即将出栈，但是这时栈里还有BC而且C才是栈顶元素。所以A选项不可能。

对于选项B：如果E是第一个出栈的元素，则ABCD一定在E之前就入了栈，所以如果E是第一个出栈的元素，则出栈顺序一定是EDCBA

对于选项C： A入栈，B入栈出栈，C入栈出栈，D入栈出栈，E入栈出栈，最后A出栈。所以选项C正确。

对于选项D：同选项B。