Question

n个元素任意依次入栈出栈，共有几种出栈序列

Answer 1

2的n-1次方个。

当n=1时，有1种

当n=2时，有2种

当n=3时，有4种

当n=4时，有8种

不同的出栈序列实际上对应着不同的入栈出栈操作，以1记为入栈，0记位出栈。

设Bn表示n个元素出栈序列的种数，显然B1=1， B2=2

如下2种：1，2 2，1 B3=5,

如下5种：1，2，3 1，3，2 2，1，3 2，3，1 3，2，1 一般地Bn=2n!/((n+1)n!n!)，并满足递推关系 Bn= B0*Bn-1+ B0*Bn-1+…+ Bn-1*B0，其中B0=1 4。

扩展资料：

设数组data[MAXSIZE]为栈的存储空间，其中MAX-SIZE是一个预先设定的常数，为允许进栈结点的最大可能数目，即栈的容量。初始时栈空，top等于0。当top不等于0时，data[0]为栈底元素，即为当前停留在栈中时间最长的元素；而data[top-1]为最后入栈的元素，即为栈顶元素。

当top==MAXSIZE时，表示栈满，如果此时再有结点进栈，将发生称之为“上溢”（语法上表现为“数组越界”）的错误，而当top==0时再执行出栈操作，将发生称之为“下溢”的错误。

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

Answer 2

正确答案应是:
2n!
-----------
(n+1)!*n!

即卡塔南数列~~~~

推导过程如下：

不同的出栈序列实际上对应着不同的入栈出栈操作，以1记为入栈，0记位出栈。

则问题实际上是求n个1和n个0构成的全排列，其中任意一个位置，它及它此前的数中，1个个数要大于等于0的个数。

n个1和n个0构成的全排列数为：

（2n）!
--------------
n! * n!
排除掉不符合要求的序列，即那些在某时刻出栈数大于入栈数的序列，即得结果。

不符合的序列数为：

（2n）！
----------------
(n+1)!(n-1)!

解释：求不符合要求的序列总数，用到了一个小技巧。在n个0和n个1构成的2n个数的序列中，假设第一次出现0的个数大于1个个数（即0的个数比1的个数大一）的位置为k，则k为奇数，k之前有相等数目的0和1，各为(k-1)/2. 若把这k个数，0换成1，1换成0 ，则原序列唯一对应上一个n＋1个1和n－1个0的序列。反之，任意一个由n＋1个1和n－1个0构成的序列也唯一的对应一个这样不合要求的序列。由于一一对应，故这样不合要求的序列数实际上等于有n＋1个1和n－1个0构成的排列数。（关于变换的一一对应，看官可自己琢磨，不再赘言）

故符合要求的数目是：
（2n）! (2n)! (2n)!
-------------- － ------------------ = --------------------
n! * n! (n+1)!(n-1)! (n+1)!(n)!