栈是数据结构中一种常用的结构。可以想象成一个没有盖的圆桶。只有两个操作：入栈和出栈。

概念：入栈、出栈、栈顶。入栈和出栈都是针对栈顶元素操作的。具体如下图：

题型：比较集中，具体体现在历年题目中。

统计：设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列有多少种可能（ ）。

答案为：

代入n=5，答案为42。

卡特兰数

说到Catalan数，就不得不提及Catalan序列，Catalan序列是一个整数序列，其：

通项公式是

递推公式是

C(n) = C(1)*C(n-1) + C(2)*C(n-2) + ... +C(n-1)C(1)，n>=2

我们从中取出的Cn就叫做第n个Catalan数，前几个Catalan数如下：

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900,2674440, 9694845, 35357670, …

咋看之下没什么特别的，但是Catalan数却是许多计数问题的最终形式。

Catalan数在组合计算中的应用

1、矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，有几种括号化的方案？

2、一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?

3、n个节点构成的二叉树，共有多少种情形？

4、求一个凸多边形区域划分成三角形区域的方法数？

5、在圆上选择2n个点，将这些点成对链接起来使得所得到的n条线段不相交，一共有多少种方法？(下图供参考)

6、n*n的方格地图中，从一个角到另外一个角，不跨越对角线的路径数为h(n).例如， 4×4方格地图中的路径有：

7、n层的阶梯切割为n个矩形的切法数也是。如下图所示：

8、有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？

9、甲乙两人比赛乒乓球，最后结果为20∶20，问比赛过程中甲始终领先乙的计分情形的种数。

10、2n个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？

往年真题

1. 元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可能是( )。

A.R1    B．R2      C．R4    D．R5

2. 有六个元素FEDCBA 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？

A．EDCFAB      B．DECABF      C．CDFEBA     D．BCDAEF

3. 设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a那么栈容量至少应该是（ ）。

A．6           B．5          C．4            D．3            E．2

4. 地面上有标号为A、B、C的3根细柱, 在A柱上方有10个直径相同中间有孔的圆盘, 从上到下次编号为1, 2, 3, ……，将A柱上的部分盘子经过B柱移入C柱, 也可以在B柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么在C柱上从下到上的盘子的编号为( ).（模拟结果）

A. 2 4 36 5 7   B. 2 4 1 2 5 7  C. 2 4 3 1 7 6     D. 2 4 3 6 7 5 E. 2 1 4 3 7 5

5. 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（ ）。（模拟结果）

A. 1, 2,3, 4, 5    B. 1, 2, 4, 5, 7    C. 1, 4, 3, 7, 6     D. 1, 4, 3, 7, 2    E. 1, 4, 3, 7, 5

6. 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ ）。 （这种情况逐个排除，但是如果问你有多少种可能呢？参考catalan数）

A. a, b,c, e, d      B. b, c, a, e, d     C.a, e, c, b, d      D. d, c, e, b, a

栈与卡特兰数往年真题参考答案：
1.ACD 2.C 3.D 4.D 5.C 6.C