數據結構中出棧序列問題分析

范玉紅

（滄州師范學院，河北 滄州 061000）

數據結構中出棧序列問題分析

范玉紅

（滄州師范學院，河北 滄州 061000）

數據結構中的出棧序列問題是算法中一個較復雜的問題，目前，針對這個問題的解決方法有很多。文章闡述棧的定義及其出棧序列問題，以及數據結構中出棧序列問題的幾種解決方法，希望對出棧序列問題的解決有一定的借鑒性意義。

數據結構；出棧序列；問題分析

隨著計算機的發展，在數據結構中出棧序列問題的研究也越來越多，該問題的解決有利于促進算法的發展。目前，針對出棧序列問題已經出現了很多的解決辦法，但如何使計算程序簡單化是解決出棧序列問題的重點所在。本文主要分析了幾種相對較簡單的解決出棧序列問題的方法。

1 棧的定義及其出棧序列問題

棧作為一種數據結構，指的是只能在棧的頂部進入或被排除出去的特殊線性表。棧的頭部稱為棧頂，棧的尾部稱為棧尾。在棧頂進入的元素一般稱為進棧，從棧中被排除出去的元素一般稱為出棧。因為只能在棧的頂部進入或者排除出去相關的元素，所以后進入棧的元素反而先出棧，這里又引出了棧的另一個稱呼，即后進先出表。正是因為棧的這種后進先出的特點，使得棧在算法中的應用非常廣泛。某一算法問題只要滿足棧的這一特性，就可以利用棧來解決。因此，在解決算法問題時，理解并能有效應用棧結構就顯得很有必要。在棧的研究內容中，經常被用來研究的問題是對有n個元素進入或被排除出去的棧進行研究。

具體的出棧序列問題是指，在棧頂進入或被排除出去的n個元素都滿足后進先出原則，問從這n個元素中可以得到多少個出棧序列。針對這個問題的解決有很多方法，如把所有出棧序列都一一列出來，然后從中找出符合條件的出棧序列；通過將出棧序列問題轉化為算法中樹的排列問題來解決；利用數學中的組合知識解決出棧序列問題等。這是幾種較普遍的關于出棧的序列問題的解決方法，本文著重結合自己學習的經驗提出幾種特別的關于出棧序列問題的解決方法，具體分析如下。

2 數據結構中出棧序列問題的幾種解決辦法

2.1 利用精簡的計算公式來解決

前文中有提到解決出棧序列問題有一種方法是可以把所有出棧序列都一一列出來，然后再從中找出符合條件的出棧序列。這個解決方法如果放在應試考試中若遇到n比較大的情況難免會較繁瑣，可以利用精簡的計算公式來簡化整個計算過程。

出棧序列的一般計算公式為：

具體的簡化方法有以下幾個步驟：（1）記住少數幾個具有代表性的f（n，m）答案。若已知f（1，1）=1，f（2，2）=2，f（3，3）=5，那么就可以簡化當n=4時的計算程序，我們可以列出當n=4時的計算程序，發現f（4，4）=14，這時可以總結出其中的規律，從而計算出f（n，m）的值，就算n再大也都可以通過套用公式的方法解決。（2）可以得出這樣的算法規律：f（n-1，n）=f（n，n）。因為f（n，n）=f（n-1，n）+f（n，n-1），由f（n，m）的計算公式可知，只有當n的數值大于m時整個計算過程才能順利進行，因此，可以得出，f（n，n-1）=0，這樣就可以得出以上計算規律。之后就是套用該計算公式，無論n有多大，都可以快速得到答案。

2.2 利用排除法解決出棧序列問題

前文中有提到解決出棧序列問題的其中一個解決方法是利用數學中的組合知識，在具體運用時并不單純只有這一類知識，還需要結合很多簡便的數學解題技巧，如排除法。

出棧序列問題當n較大時，就會有非常多的數列組合，可以先列出其中相對簡單的數列組合，然后再利用計算公式計算出n個元素時可能的數列組合。但這些數列組合并不一定都滿足要求，需要符合棧的后進先出原則?？梢酝ㄟ^一一排列來分析：

當n=1時，只有1個數列排列組合，即1，出棧的序列數也只有1個；當n=2時，有兩個數列排列組合，即12 21 ，計算出的出棧序列個數也只有兩個；當n=3時，有6個數列排列組合，即123 213 231 321 132 312 ，其中312這種組合方式由于不符合棧的后進先出原則，故排除掉，所以實際的出棧序列數為5個，這時出棧序列數小于數列排列組合；當n=4時，有24個數列排列組合，即1234 2134 1243 2143 1324 3214 1342 2341 3241 2431 3421 1432 4321 3124 4123 3142 4132 4213 4231 1423 4312 2413 3412，其中3124 4123 3142 4132 4213 4231 1423 4312 2413 3412不符合棧的后進先出原則，故要排除掉這10個數列組合，所以實際的出棧序列數為14個，這時出棧序列數小于數列排列組合。

通過列舉以上較簡單的數列組合和相應的出棧序列數，可以得出兩個結論：（1）出棧序列個數小于或者等于數列組合個數；（2）當較大的數字被排在前面時，通常整個數列會以降序的形式呈現。通過以上兩條觀察得出的結論，推算出若n的數值大于或者等于二，減去第一位為最大數的不符合棧的原則的組合數列，剩余的符合條件的排列個數為：n×m+1（n為數列排列組合的總個數，m為第一位為最大數的不符合棧的原則的組合數列）。

當n的數值較小時，貌似列出的所有數列組合個數都可以將其歸為出棧序列組合，但是當n越來越大時，不符合條件的數列組合也會越來越多，這說明想利用棧來解決算法問題必須符合棧的后進先出原則。

除了以上兩個結論外，還可以推斷出第3個結論，排在最前面的數字與排在它后面的小于它的數字都必須遵循降序排列的原則，另外，除第一位數字外，在后面的遵循降序排列的數字可以隨意插入比第一位數字大的數字。簡單來說，只有在棧的頂端的元素才能出來。針對這個結論，可以通過簡單的例子來加以說明。譬如，有這樣的幾個數列排列方式：312 4312 4231 2413 1423 ，這幾個數列都不滿足棧的后進先出的原則。312這個數列組合，3排在最前面，后面的1與2應當遵循降序排列的原則，但事實上并沒有；4312這個數列組合，4排在最前面，后面的數字3，1，2這幾個數字應遵循降序排列方式，正確的排列方式應為4321，所以后面的4231自然也不符合條件，被排除掉；2413這個數列組合，排在最前面的是2，后面的4，3都大于2，可以隨意排列，但是在4后面的數字1，3比4小，應當遵循降序排列的原則，符合條件的排列方式應為2431，所以2413不符合要求，應當被排除掉；數列組合1423之所以不符合的原因類似于2413的推斷方法，這里不再一一贅述。

根據結論三，還可以推斷出第4個結論，即無論是降序排列的數列組合還是升序排列的數列組合都符合棧的后進先出原則，即都是符合條件的數列組合。

事實上，只要理解了結論三，就可以寫出所有的數列組合，并且可以快速地把不符合條件的刪除掉。以有5個數的數列組合來具體分析：把5放在首位，那么通過結論二可以知道，只有降序排列這一種數列組合符合要求，可以根據公式得出具體的排列組合，總個數為5×4×3×2×1=120個，其中符合條件的是以降序的方式排列出來的組合，按照要求一一列舉出來就可以了，這里不再一一列舉。

當把4放在第一位時，放在其后的必然是5，3這兩個數字，不可能是1，2。若5在第二位，后面的需以降序的方式排列，只能有一種排列方式45321；若3排在第二位，那么后面的5可任意穿插，有43521，43251，43521這3種排列方式。

由于篇幅有限，只列舉出兩種以5為首位和以4為首位的排列方式，以下排列方式的原理類似于這兩種排列方式。

3 結語

綜上所述，棧作為一種數據結構，在算法的計算中占有重要位置。本文主要闡述了棧的定義及其出棧序列問題。目前，針對出棧序列問題有很多解決方法，本文主要是結合個人學習的經驗列舉出兩種具有代表性的解決出棧序列問題的解決方法。

[1]靳紅霞，呂龍輝.數據結構中經典算法及其教學策略探討[J].信息與電腦（理論版），2010（3）：126.

[2]吳紅芝，郭麥成，吳浩.數據結構中內部排序算法的分析[J].計算機時代，2010（6）：38-39.

[3]王濤春，羅永龍，左開中.基于在線評測的數據結構實踐教學探討[J].計算機教育，2010（10）：88-91.

Analysis of stacking sequence issue in data structure

Fan Yuhong
（Cangzhou Normal University, Cangzhou 061000, China）

The stacking sequence issue in data structure is a complicated problem in the algorithm. At present, there are many methods for solving this problem. This paper elaborates the de fi nition of the stuck and stack sequence issue, and several solutions to the stacking sequence issue in data structure, hoping to have certain reference signi fi cance to solve the stack sequence issue.

data structure; stacking sequence; issue analysis

范玉紅（1964— ），女，河北滄州人，本科，副教授；研究方向：計算機軟件。