數(shù)據(jù)結(jié)構(gòu)中出棧序列問題分析

范玉紅

（滄州師范學(xué)院，河北 滄州 061000）

數(shù)據(jù)結(jié)構(gòu)中出棧序列問題分析

范玉紅

（滄州師范學(xué)院，河北 滄州 061000）

數(shù)據(jù)結(jié)構(gòu)中的出棧序列問題是算法中一個(gè)較復(fù)雜的問題，目前，針對(duì)這個(gè)問題的解決方法有很多。文章闡述棧的定義及其出棧序列問題，以及數(shù)據(jù)結(jié)構(gòu)中出棧序列問題的幾種解決方法，希望對(duì)出棧序列問題的解決有一定的借鑒性意義。

數(shù)據(jù)結(jié)構(gòu)；出棧序列；問題分析

隨著計(jì)算機(jī)的發(fā)展，在數(shù)據(jù)結(jié)構(gòu)中出棧序列問題的研究也越來越多，該問題的解決有利于促進(jìn)算法的發(fā)展。目前，針對(duì)出棧序列問題已經(jīng)出現(xiàn)了很多的解決辦法，但如何使計(jì)算程序簡單化是解決出棧序列問題的重點(diǎn)所在。本文主要分析了幾種相對(duì)較簡單的解決出棧序列問題的方法。

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

棧作為一種數(shù)據(jù)結(jié)構(gòu)，指的是只能在棧的頂部進(jìn)入或被排除出去的特殊線性表。棧的頭部稱為棧頂，棧的尾部稱為棧尾。在棧頂進(jìn)入的元素一般稱為進(jìn)棧，從棧中被排除出去的元素一般稱為出棧。因?yàn)橹荒茉跅５捻敳窟M(jìn)入或者排除出去相關(guān)的元素，所以后進(jìn)入棧的元素反而先出棧，這里又引出了棧的另一個(gè)稱呼，即后進(jìn)先出表。正是因?yàn)闂５倪@種后進(jìn)先出的特點(diǎn)，使得棧在算法中的應(yīng)用非常廣泛。某一算法問題只要滿足棧的這一特性，就可以利用棧來解決。因此，在解決算法問題時(shí)，理解并能有效應(yīng)用棧結(jié)構(gòu)就顯得很有必要。在棧的研究內(nèi)容中，經(jīng)常被用來研究的問題是對(duì)有n個(gè)元素進(jìn)入或被排除出去的棧進(jìn)行研究。

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

2 數(shù)據(jù)結(jié)構(gòu)中出棧序列問題的幾種解決辦法

2.1 利用精簡的計(jì)算公式來解決

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

出棧序列的一般計(jì)算公式為：

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

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

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

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

當(dāng)n=1時(shí)，只有1個(gè)數(shù)列排列組合，即1，出棧的序列數(shù)也只有1個(gè)；當(dāng)n=2時(shí)，有兩個(gè)數(shù)列排列組合，即12 21 ，計(jì)算出的出棧序列個(gè)數(shù)也只有兩個(gè)；當(dāng)n=3時(shí)，有6個(gè)數(shù)列排列組合，即123 213 231 321 132 312 ，其中312這種組合方式由于不符合棧的后進(jìn)先出原則，故排除掉，所以實(shí)際的出棧序列數(shù)為5個(gè)，這時(shí)出棧序列數(shù)小于數(shù)列排列組合；當(dāng)n=4時(shí)，有24個(gè)數(shù)列排列組合，即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不符合棧的后進(jìn)先出原則，故要排除掉這10個(gè)數(shù)列組合，所以實(shí)際的出棧序列數(shù)為14個(gè)，這時(shí)出棧序列數(shù)小于數(shù)列排列組合。

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

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

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

根據(jù)結(jié)論三，還可以推斷出第4個(gè)結(jié)論，即無論是降序排列的數(shù)列組合還是升序排列的數(shù)列組合都符合棧的后進(jìn)先出原則，即都是符合條件的數(shù)列組合。

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

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

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

3 結(jié)語

綜上所述，棧作為一種數(shù)據(jù)結(jié)構(gòu)，在算法的計(jì)算中占有重要位置。本文主要闡述了棧的定義及其出棧序列問題。目前，針對(duì)出棧序列問題有很多解決方法，本文主要是結(jié)合個(gè)人學(xué)習(xí)的經(jīng)驗(yàn)列舉出兩種具有代表性的解決出棧序列問題的解決方法。

[1]靳紅霞，呂龍輝.數(shù)據(jù)結(jié)構(gòu)中經(jīng)典算法及其教學(xué)策略探討[J].信息與電腦（理論版），2010（3）：126.

[2]吳紅芝，郭麥成，吳浩.數(shù)據(jù)結(jié)構(gòu)中內(nèi)部排序算法的分析[J].計(jì)算機(jī)時(shí)代，2010（6）：38-39.

[3]王濤春，羅永龍，左開中.基于在線評(píng)測(cè)的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)探討[J].計(jì)算機(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— ），女，河北滄州人，本科，副教授；研究方向：計(jì)算機(jī)軟件。