Question

已知入栈顺序为12345,求所有可能的出栈序列

Answer 1

序列个数太多，以123为例：123进栈，出栈321；1进栈，1出栈，2进栈，2出栈，3进栈，3出栈，所以是123，以此类推。

4个元素的全排列共有24种，栈要求符合后进先出，按此衡量排除后即得：

1234√    1243√    1324√    1342√    1423×    1432√

2134√    2143√    2314√    2341√    2413×    2431√

3124×    3142×    3214√    3241√    3412×    3421√

4123×    4132×    4213×    4231×    4312×    4321√

14种可能，10种不可能，如上所示。

扩展资料：

栈的顺序存储结构是利用内存中的一片起始位置确定的连续存储区域来存放栈中的所有元素，另外为了指示栈顶的准确位置，还需要引入一个栈顶指示变量top，采用顺序存储结构的栈称为顺序栈（sequence stack)。设数组data[MAXSIZE]为栈的存储空间，其中MAX-SIZE是一个预先设定的常数，为允许进栈结点的最大可能数目，即栈的容量。

初始时栈空，top等于0。当top不等于0时，data[0]为栈底元素，即为当前停留在栈中时间最长的元素；而data[top-1]为最后入栈的元素，即为栈顶元素。

参考资料来源：百度百科-顺序栈

Answer 2

很好理解啊，栈的特点是‘先进后出’，比如说12345，有可能1刚进栈就出栈了，其它数全进去了才出，就会产生15432，以此类推就可以；相反43512就不行，因为当4首先出栈，则说明1，2，3三个元素已经入栈，则出栈序列中1不可能在2之前

Answer 3

4个元素的全排列共有24种，栈要求符合后进先出，按此衡量排除后即得：

1234√    1243√    1324√    1342√    1423×    1432√

2134√    2143√    2314√    2341√    2413×    2431√

3124×    3142×    3214√    3241√    3412×    3421√

4123×    4132×    4213×    4231×    4312×    4321√

14种可能，10种不可能，如上所示。