Question

入栈顺序为12345,所有可能的出栈序列是什么？

Answer 1

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种不可能，如上所示。

Answer 2

可以用排列组合来算，总共有42种

Answer 3

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