1. 前言雜談
近來重新整理學(xué)習(xí)一下數(shù)據(jù)結(jié)構(gòu)知識，看到了數(shù)據(jù)結(jié)構(gòu)相關(guān)的考試中成醮考棧的一種題型扣草，最近才得知這類問題的名字叫做棧的混洗，不由感嘆自己的淺薄氨鹏，簡單的理解了一下發(fā)現(xiàn)也并不是那么容易的問題欧募，沒有發(fā)現(xiàn)規(guī)律性，而粗略的枚舉由實在很消耗時間喻犁。
故在此整理和搜集一些資料槽片，希望可以整理出一些有用的東西來。
2. 基本問題
概念
給定一個有序的數(shù)據(jù)元素的序列肢础，通過控制入棧和出棧的時機，可以得到不同的出棧序列碌廓，這就是本文討論的棧的混洗传轰。
入棧序列為{1'2'3}，問可能的出棧序列有多少種谷婆？不可能的出棧序列存哪些慨蛙？
這是數(shù)據(jù)結(jié)構(gòu)中相當(dāng)常規(guī)的練習(xí)題，筆者過去遇到這類問題時無非也就是心中枚舉可能的出列序列然后判斷是否合理——
a. 1纪挎、2期贫、3的排列方式有6種；
b. 取出每種可能的序列模擬入棧出棧的時機异袄，論證該序列的能性通砍；
c. 經(jīng)過6次模擬我們可以得出可能的出棧序列有5種，不可能的序列為3烤蜕、1封孙、2。
上面的討論中不難發(fā)現(xiàn)讽营，由于3最先出棧虎忌，因此3必定在棧頂，按照序列1橱鹏、2已經(jīng)入棧膜蠢，1必在2的下方堪藐，即1必在2的后面出棧。
在這一問題中挑围，對排列的各種情況的討論并不困難礁竞，但當(dāng)序列長度增加時，問題的復(fù)雜度會急劇增加贪惹。其實苏章，我們可以發(fā)現(xiàn)這一問題的解答方法應(yīng)該有兩個地方可以優(yōu)化：
- 是否可以快速得到一個序列是否是不可能序列？
- 是否可以快速計算一共有多少種可能的序列奏瞬？
這也是許多測試中經(jīng)常會考察的兩個問題枫绅。
求解可能的序列數(shù)
一般情形下，我們假設(shè)進棧序列為１硼端，２并淋，３，……珍昨，ｎ县耽，可能的退棧序列有ｍ（ｎ）種，對此镣典，我們可以做如下推導(dǎo)：
當(dāng)ｎ＝０時兔毙，ｍ（０）＝１：退棧序列為｛｝；
當(dāng)ｎ＝１時兄春，ｍ（１）＝１：退棧序列為｛１｝澎剥；
當(dāng)ｎ＝２時，ｍ（２）＝２：退棧序列中１在首位赶舆，１左側(cè)有０個數(shù)哑姚，１右側(cè)有一個數(shù)，有ｍ（０）＊ｍ（１）種可能芜茵，１在末位叙量，１左側(cè)有一個數(shù)，右側(cè)有０個數(shù)九串，有ｍ（１）＊ｍ（０）種绞佩，一共有ｍ（０）＊ｍ（１）＋ｍ（１）＊ｍ（０）種可能的序列。
簡單的推導(dǎo)中不難發(fā)現(xiàn)蒸辆，將１置于ｉ＝１……ｎ的位置征炼，則可能的序列數(shù)為ｍ（ｉ－１）＊ｍ（ｎ－ｉ）種。
總結(jié)一下：
一般的躬贡，設(shè)有n個元素序號按序號１,２谆奥，……，ｎ進棧拂玻，輪流讓１在退棧序列的第１酸些，第２宰译，……，第ｎ位魄懂，則可能的的退棧序列種數(shù)為：
ｍ（０）＊ｍ（ｎ－１）＋ｍ（１）＊ｍ（ｎ－２）＋……＋ｍ（ｎ－１）＊ｍ（０）
＝１／（ｎ＋１）＊Ｃ（ｎ沿侈，２ｎ）
＝［（２ｎ）（２ｎ－１）……（ｎ＋２）］／（ｎ！）
不可能的退棧序列
設(shè)對于初始進棧序列1市栗，2缀拭，3，……填帽，ｎ蛛淋，利用棧得到可能的退棧序列為ｐ１，ｐ２篡腌，……褐荷，ｐｉ，……嘹悼，ｐｎ叛甫，
如果序號ｉ＜ｊ＜ｋ，且在進棧序列中ｐｉ＜ｐｊ＜ｐｋ杨伙，即：
……其监，ｐｉ，……限匣，ｐｊ棠赛，……，ｐｋ膛腐，……（ｐｉ＜ｐｊ＜ｐｋ）
則……，ｐｋ鼎俘，……哲身，ｐｉ，……贸伐，ｐｊ勘天，……就是不可能的退棧序列。
因為ｐｋ在ｐｉ和ｐｊ之后進棧捉邢，又先于ｐｉ和ｐｊ退棧脯丝，按照棧的后進后出的特性，ｐｉ壓在ｐｊ的下面伏伐，理應(yīng)ｐｊ先出宠进，所以……，ｐｋ藐翎，……材蹬，ｐｉ实幕，……，ｐｊ堤器，……是不可能的昆庇。
總結(jié)成一句話就是——當(dāng)前下標(biāo)大于后下標(biāo)時，則后下標(biāo)必定遞減（或者說倒序）闸溃。
參考資料:數(shù)據(jù)結(jié)構(gòu)（C語言描述）整吆，清華大學(xué)出版社（2012.10），殷人昆
