【数据结构】栈与卡特兰数（详细）
【数据结构】栈与卡特兰数（详细）
在学习数据结构中的栈时，一个有趣的问题常常被提及：当一串数量为n的序列按照固定次序进入一个栈中，并且入栈后可以随时出栈或者等待后再出栈，那么最后输出的长度为n的序列有多少种可能？这个问题的答案与组合数学中的一个重要数列——卡特兰数密切相关。本文将通过一个有趣的数学问题——蚂蚁在n*n方格中从左下角到右上角的路径问题，深入探讨栈与卡特兰数的关系。
对角线路径问题
在研究栈的问题之前，先看下面的一个数学问题。
在一个n*n的二维方格里，有一只蚂蚁需要从左下角前往右上角。这只蚂蚁只能往右或者往上走，那么总共有几条不同的路径？
图1 路径问题
这里我们可以将蚂蚁作出的决策排成一个序列。记向右走为"d"，向上走为"w"，那么可知蚂蚁需要输入n个向右与n个向上共计2n个移动指令。显然，在这2n次操作里，只要移动的顺序有一点不同，则走出的路径就是不同的。于是这个题目可以抽象为，往2n个"盒子"中投入n个“d”与n个“w”，有几种不同的投法？很显然，答案为
（从2n个位置中选出n个位置存放d或w）。
现在在这个简单问题上再加入一点限制，如果蚂蚁不能够越过y=x这条线，那么总共有几条路径？
图2 限制路径问题
由于每一条越过y=x这条线的路径都必然会与y=x+1相交，所以在这里执行下面的映射操作：对于所有越过y=x并与y=x+1相交的路径，在其与y=x+1的第一个交点后，将其“向右走”的操作换成“向上走”，“向上走”的操作换为“向右走”。
图3 变换前
图4 变换后
在原路径的前半段，即与y=x+1相交之前，路径向上走的次数比向右走的次数多1；在原路径后半段，即与y=x+1相交之后，由于向上走的次数和向右走的次数都为n，所以向上走的次数比向右走的次数少1，经过映射后则多1。
所以对于新路径，有w-d=2，又w+d=2n（总操作数不变），可以得到w=n+1，d=n-1，即新路径的终点为B（n-1,n+1）。
又由于原路径不重复，故新路径也不会重复，可以得到越过y=x并最终到达终点A（n,n）的路径数等于从原点出发到达B（n-1,n+1）的路径数。而原题目要求的不能越过y=x的路径数，就等于总路径数减去从原点出发到达B（n-1,n+1）的路径数，即
。经过化简（
）可以得出答案就是卡特兰数
。
那么这跟栈又有什么关系呢？现在将上面的向右走指令“d”换成“进栈”，向上走指令“w”换为“出栈”。由于原问题满足下面两个条件，所以原来栈的问题与对角线问题完全等价：
1、由于路径在y=x下方，所以“出栈”的次数d一定小等于“入栈”的次数w，满足栈的基本性质。
2、由于终点坐标为（n,n），相当于对一串给定序列，输入n个入栈指令与n个出栈指令，恰能够把带有n个元素的输入序列完整转换为带有n个元素的输出序列。
ps：栈的问题：当一串数量为n的序列固定次序地进入一个栈中，并且入栈后可以随时出栈或者等待后再出栈，那么最后输出的数量为n的序列有多少种？
对角线路径问题：在一个nn的二维方格里，有一只蚂蚁需要从左下角前往右上角。这只蚂蚁只能往右或者往上走，且不能够越过y=x*，**总共有几条不同的路径？
解递推式求卡特兰数
除了上面的方法之外，还有一种方法能够求出卡特兰数。现思考：对于一个长度为n的给定次序的序列，如果第一个进栈的元素为a，那么显然，当a被输出时，栈为空。假设a是第x个被输出的元素，那么在a之前的x-1个元素的进出栈问题与a之后的n-x个未入栈元素的进出栈问题是两个独立的进出栈问题。于是假设n个元素进出栈后得到的序列数为f(n)，可以得到下面的递推关系：
（a可能第1、2、3...n次出栈，则f(n)为所有可能性之和）
经过推导可以得出f(n)的通项，具体方法可看b站up主“肉饼粥”的讲解（卡特兰数和数据结构_哔哩哔哩_bilibili）。