如何解决栈的出栈序列问题？

本文共计542个文字，预计阅读时间需要3分钟。

出栈序列问题——栈的基本原理——后进先出（Last In First Out, LIFO）要解决这类问题：首先，最基本的原则是出栈序列反映了栈中元素的操作顺序。也就是说，最后进入栈的元素会最先被取出。要解决这个问题：

- 最基本的质询是确定出栈序列是否可能。这可以通过比较输入栈的顺序和出栈顺序来决定。- 假设栈的输入顺序为1、2、3，问出栈序列有哪些可能？

假设：1、2、3输入栈，可能的出栈序列有：- 1、2、3- 1、3、2- 2、1、3- 2、3、1- 3、1、2- 3、2、1

即，只要出栈序列满足后进先出的原则，那么它就是可能的。

出栈序列问题

栈之根本——后进先出(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。