1. 前言杂谈
近来重新整理学习一下数据结构知识，看到了数据结构相关的考试中常考栈的一种题型，最近才得知这类问题的名字叫做栈的混洗，不由感叹自己的浅薄，简单的理解了一下发现也并不是那么容易的问题，没有发现规律性，而粗略的枚举由实在很消耗时间。
故在此整理和搜集一些资料，希望可以整理出一些有用的东西来。
2. 基本问题
概念
给定一个有序的数据元素的序列，通过控制入栈和出栈的时机，可以得到不同的出栈序列，这就是本文讨论的栈的混洗。
入栈序列为{1'2'3}，问可能的出栈序列有多少种？不可能的出栈序列存哪些？
这是数据结构中相当常规的练习题，笔者过去遇到这类问题时无非也就是心中枚举可能的出列序列然后判断是否合理——
a. 1、2、3的排列方式有6种；
b. 取出每种可能的序列模拟入栈出栈的时机，论证该序列的能性；
c. 经过6次模拟我们可以得出可能的出栈序列有5种，不可能的序列为3、1、2。
上面的讨论中不难发现，由于3最先出栈，因此3必定在栈顶，按照序列1、2已经入栈，1必在2的下方，即1必在2的后面出栈。
在这一问题中，对排列的各种情况的讨论并不困难，但当序列长度增加时，问题的复杂度会急剧增加。其实，我们可以发现这一问题的解答方法应该有两个地方可以优化：
- 是否可以快速得到一个序列是否是不可能序列？
- 是否可以快速计算一共有多少种可能的序列？
这也是许多测试中经常会考察的两个问题。
求解可能的序列数
一般情形下，我们假设进栈序列为１，２，３，……，ｎ，可能的退栈序列有ｍ（ｎ）种，对此，我们可以做如下推导：
当ｎ＝０时，ｍ（０）＝１：退栈序列为｛｝；
当ｎ＝１时，ｍ（１）＝１：退栈序列为｛１｝；
当ｎ＝２时，ｍ（２）＝２：退栈序列中１在首位，１左侧有０个数，１右侧有一个数，有ｍ（０）＊ｍ（１）种可能，１在末位，１左侧有一个数，右侧有０个数，有ｍ（１）＊ｍ（０）种，一共有ｍ（０）＊ｍ（１）＋ｍ（１）＊ｍ（０）种可能的序列。
简单的推导中不难发现，将１置于ｉ＝１……ｎ的位置，则可能的序列数为ｍ（ｉ－１）＊ｍ（ｎ－ｉ）种。
总结一下：
一般的，设有n个元素序号按序号１,２，……，ｎ进栈，轮流让１在退栈序列的第１，第２，……，第ｎ位，则可能的的退栈序列种数为：
ｍ（０）＊ｍ（ｎ－１）＋ｍ（１）＊ｍ（ｎ－２）＋……＋ｍ（ｎ－１）＊ｍ（０）
＝１／（ｎ＋１）＊Ｃ（ｎ，２ｎ）
＝［（２ｎ）（２ｎ－１）……（ｎ＋２）］／（ｎ！）
不可能的退栈序列
设对于初始进栈序列1，2，3，……，ｎ，利用栈得到可能的退栈序列为ｐ１，ｐ２，……，ｐｉ，……，ｐｎ，
如果序号ｉ＜ｊ＜ｋ，且在进栈序列中ｐｉ＜ｐｊ＜ｐｋ，即：
……，ｐｉ，……，ｐｊ，……，ｐｋ，……（ｐｉ＜ｐｊ＜ｐｋ）
则……，ｐｋ，……，ｐｉ，……，ｐｊ，……就是不可能的退栈序列。
因为ｐｋ在ｐｉ和ｐｊ之后进栈，又先于ｐｉ和ｐｊ退栈，按照栈的后进后出的特性，ｐｉ压在ｐｊ的下面，理应ｐｊ先出，所以……，ｐｋ，……，ｐｉ，……，ｐｊ，……是不可能的。
总结成一句话就是——当前下标大于后下标时，则后下标必定递减（或者说倒序）。
参考资料:数据结构（C语言描述），清华大学出版社（2012.10），殷人昆
网友评论