摘 要： 在棧大小不受限制和棧大小受限制兩種情況下，分析在給定入棧序列（1 2 … n）的情況下，出棧序列應(yīng)滿足的性質(zhì)，并據(jù)此給出基于窮舉法和模擬入棧出棧過程的方法判斷序列a1a2…an是否是出棧序列的算法及程序實現(xiàn)。算法較直觀，易于理解，程序均經(jīng)過測試，輸出正確。
關(guān)鍵詞： 棧；出棧序列；降序；算法；程序
0 引言
棧是限定僅在表尾端進行插入或刪除操作的特殊線性表。通常稱表尾端為棧頂，向棧中插入元素稱為進棧，從棧中刪除元素稱為出棧。由于插入和刪除運算僅在棧頂一端進行，因此棧具有后進先出的特性，這種特性使得棧有著十分廣泛的應(yīng)用。在參考文獻[1-9]中，對給定一個入棧序列，求出棧序列數(shù)量、輸出全部出棧序列、判斷一個序列是否為出棧序列等問題進行了研究，得出了相應(yīng)的研究結(jié)果。然而，以上研究結(jié)果均基于一個前提：棧的大小是不受限制的，即棧的大小大于等于入棧序列的長度。而在某些情況下，棧的大小會受到限制，即棧的大小小于入棧序列的長度，此時有關(guān)棧的入棧出棧算法會發(fā)生變化。因此，本文對棧大小不受限制和棧大小受限制兩種情況下，判斷一個序列是否為出棧序列的問題進行分析研究，并給出了相應(yīng)的算法和程序?qū)崿F(xiàn)。
為方便分析，將本文研究的有關(guān)棧的問題描述如下：給定入棧序列（1 2 … n），判斷序列a1a2…an是否是出棧序列。
1 出棧序列性質(zhì)
當(dāng)棧大小不受限制時，即棧的大小大于等于入棧序列的長度時，依據(jù)棧的特點，較容易得出出棧序列應(yīng)該滿足的性質(zhì)。
性質(zhì)1：當(dāng)棧大小不受限制時，序列a1a2…an是（1 2 … n）的一個全排列, 則a1a2…an為出棧序列的充要條件是：對于任意的ai, 在它后面的且比它小的數(shù)是降序排列的。
當(dāng)棧的大小受限制，即棧的大小k小于入棧序列長度n時，出棧序列首先需要滿足性質(zhì)1，然后考慮棧大小受限對出棧序列的要求。例如有長度n=6的入棧序列123456，棧的大小k=4，此時出棧序列的第1位不能超過元素4，即出棧序列第1位小于等于4，第2位小于等于5。
一般情況下，第1位小于等于k，第2位小于等于k+1，依次類推，直到出棧序列第n-k位小于等于n-1。
性質(zhì)2：當(dāng)棧大小受限制，即棧大小k小于入棧序列長度n時，序列a1a2…an是（1 2 … n）的一個全排列, 則a1a2…an為出棧序列的充要條件是滿足性質(zhì)1并且序列的第j位小于等于k+j-1。
2 棧大小不受限制時的判斷
給定入棧序列12…n，判斷序列a1a2…an是否是出棧序列。此時可以對序列直接判斷是否滿足性質(zhì)1。滿足則為出棧序列，否則不是出棧序列。
算法1：入棧序列為12…n，待判斷序列為a1a2…an。
（1）輸入待判斷序列，i=1。
（2）若i>n，轉(zhuǎn)（3）；否則判斷序列a1a2…an第i位ai后比ai小的元素是否降序排列，若是則i++，轉(zhuǎn)（2）；否則轉(zhuǎn)（3）。
（3）若i>n，則判斷該序列為出棧序列；否則，判斷該序列不是出棧序列。
程序如下：
#include "iostream.h"
#include "string.h"
int pd(char a[],int n)
{ int u,v,w,flag=1;
for(u=0;u<=n-2;u++)
for(v=u+1;v<=n-1;v++)
for(w=v+1;w<=n;w++)
if((a[v]<a[w])&&(a[w]<a[u]))
flag=0;
return flag;}
void main()
{char a[10];
cout<<"請輸入待判斷的序列:"<<endl;
cin>>a;
if(pd(a,strlen(a)-1))
cout<<"這是出棧序列"<<endl;
else
cout<<"這不是出棧序列"<<endl;}
不難發(fā)現(xiàn)上述算法需要多層循環(huán)，效率偏低。可以考慮做改進，此時使用臨時棧s模擬入棧出棧過程，用i表示待判斷序列第i位，用j表示入棧序列第j位。算法如下：
算法2：入棧序列為12…n，待判斷序列為a1a2…an, s為臨時棧。
（1）初始情況下i、j的初值為1。
（2）當(dāng)i或j大于n時，轉(zhuǎn)（4），否則用待判斷序列第i位ai與入棧序列第j位比較。
（3）ai大于j時，將j入棧s，j++，轉(zhuǎn)（2）；ai等于j時，i++、j++，轉(zhuǎn)（2）；ai小于j時，比較ai與s棧的棧頂元素，若相等則s棧的棧頂元素出棧，i++，轉(zhuǎn)（2），否則判斷該序列不是出棧序列。
（4）判斷棧是否為空，若為空，則判斷該序列是出棧序列，否則依次判斷ai、ai+1、…、an與s棧的出棧序列是否相同，若不同則判斷該序列不是出棧序列，若相同則判斷該序列為出棧序列。
將上述pd函數(shù)改寫如下：
int pd(char a[],int n)
{ int i=0,j=0,top=0;
char b[10];
while(i<=n&&j<=n)
{ if(a[i]>('1'+j))
{ b[top++]='1'+j; j++; }
else if(a[i]==('1'+j))
{ i++; j++; }
else
{ if(a[i]==b[--top])
i++; } }
if(top)
while(i<=n)
if(a[i]==b[--top])
i++;
else return 0;
return 1;}
3 棧大小受限制時的判斷
當(dāng)棧的大小受限制，即棧的大小k小于入棧序列長度n時，出棧序列需要滿足性質(zhì)2中所述的性質(zhì)。此時可以判斷待判斷序列a1a2…an第i位ai后比ai小的元素是否降序排列以及第j位是否小于等于k+j-1，若滿足則為出棧序列，否則不是出棧序列。
此時的判斷算法，可以在算法1的基礎(chǔ)上，加入對待判斷序列第j位是否小于等于k+j-1的判斷。
算法3：入棧序列為12…n，待判斷序列為a1a2…an。
（1）輸入待判斷序列，i=1，j=1。
（2）若j>n-k，則轉(zhuǎn)（3）；否則判斷序列第j位是否小于等于k+j-1，若是則j++，轉(zhuǎn)（2）；否則轉(zhuǎn)（4）。
（3）若i>n，則轉(zhuǎn)（4）；否則判斷序列a1a2…an第i位ai后比ai小的元素是否降序排列，若是則i++，轉(zhuǎn)（3）；否則轉(zhuǎn)（4）。
（4）若i>n，則判斷該序列為出棧序列；否則，判斷該序列不是出棧序列。
程序如下：
#include "iostream.h"
#include "string.h"
int pd(char a[],int n,int x)
{ int u,v,w,j,flag=1;
for(j=0;j<=n-x;j++)
if((a[j]-'0')>(x+j))
flag=0;
if(flag)
for(u=0;u<=n-2;u++)
for(v=u+1;v<=n-1;v++)
for(w=v+1;w<=n;w++)
if((a[v]<a[w])&&(a[w]<a[u]))
flag=0;
return flag;}
void main()
{ int x;
char a[10];
cout<<"請輸入棧大小:"<<endl;
cin>>x;
cout<<"請輸入待判斷的序列:"<<endl;
cin>>a;
if(pd(a,strlen(a)-1,x)) cout<<"這是出棧序列"<<endl;
else cout<<"這不是出棧序列"<<endl;}
不難看出此算法效率較低，可以做改進。此時需使用臨時棧s模擬入棧出棧過程，當(dāng)待判斷序列第i位大于入棧序列第j位時，將入棧序列第j位入棧。由于受原棧大小為k的限制，此時臨時棧s的入棧元素不能超過k-1個。算法如下：
算法4：棧大小為k，入棧序列為12…n，待判斷序列為a1a2…an，s為臨時棧。
（1）初始情況下i、j的初值為1。
（2）當(dāng)i或j大于n時，轉(zhuǎn)（4）；否則用待判斷序列第i位ai與入棧序列第j位比較。
（3）ai大于j時，判斷s棧中元素個數(shù)是否小于k-1，若是則將j入s棧，j++，轉(zhuǎn)（2），否則判斷該序列不是出棧序列；ai等于j時，i++、j++，轉(zhuǎn)（2）；ai小于j時，比較ai與s棧的棧頂元素，若相等則s棧的棧頂元素出棧，i++，轉(zhuǎn)（2），否則判斷該序列不是出棧序列。
（4）判斷s棧是否為空，若為空，則判斷該序列是出棧序列，否則依次判斷ai、ai+1、…、an與s棧的出棧序列是否相同，若不同則判斷該序列不是出棧序列，若相同則判斷該序列為出棧序列。
將上述pd函數(shù)改寫如下：
int pd(char a[],int n,int k)
{ int i=0,j=0,top=0;
char b[10];
while(i<=n&&j<=n)
{ if(a[i]>('1'+j))
{ if(top==k-1)
return 0;
b[top++]='1'+j; j++; }
else if(a[i]==('1'+j))
{ i++; j++; }
else
{ if(a[i]==b[--top])
i++; } }
if(top)
while(i<=n)
if(a[i]==b[--top])
i++;
else return 0;
return 1; }
上述算法效率依然不是最高的，例如待判斷序列為543261時，用待判斷序列第1位與入棧序列第1位比較，由于5大于1，且s棧中元素個數(shù)為0，小于k-1=3，因此將入棧序列中的1入s棧，繼續(xù)比較待判斷序列第1位與入棧序列第2位。由于5大于2，且s棧中元素個數(shù)為1，小于3，因此將入棧序列中的2入s棧，繼續(xù)比較待判斷序列第1位與入棧序列第3位。由于5大于3，且s棧中元素個數(shù)為2，小于3，因此將入棧序列中的3入s棧，繼續(xù)比較待判斷序列第1位與入棧序列第4位。由于5大于4，而s棧中元素個數(shù)為3，若將4入s棧，則s棧中元素個數(shù)大于3，因此待判斷序列不是出棧序列。
而此時已經(jīng)有3個元素入s棧，才判斷出該序列不是出棧序列，可以考慮直接在開始時判斷該序列是否滿足大小受限制棧的出棧序列應(yīng)該滿足的要求，即第j位小于等于k+j-1。上例由于第1位5大于4+1-1=4，因此不用入s棧就可判斷出該序列不是出棧序列。改進算法如下：
算法5：棧大小為k，入棧序列為12…n，待判斷序列為a1a2…an，s為臨時棧
（1）初始情況下i、j的初值為1。
（2）當(dāng)i或j大于n時，轉(zhuǎn)（4）；否則判斷ai是否大于k+i-1，若大于，則判斷該序列不是出棧序列，否則用待判斷序列第i位ai與入棧序列第j位比較。
（3）ai大于j時，則將j入s棧，j++，轉(zhuǎn)（2）；ai等于j時，i++、j++，轉(zhuǎn)（2）；ai小于j時，比較ai與s棧的棧頂元素，若相等則s棧棧頂元素出棧，i++，轉(zhuǎn)（2），否則判斷該序列不是出棧序列。
（4）判斷棧是否為空，若為空，則判斷該序列是出棧序列，否則依次判斷ai、ai+1、…、an與棧的出棧序列是否相同，若不同則判斷該序列不是出棧序列，若相同則判斷該序列為出棧序列。
改寫pd函數(shù)如下：
int pd(char a[],int n,int k)
{ int i=0,j=0,top=0;
char b[10];
while(i<=n&&j<=n)
{if(a[i]-'0'>k+i) return 0;
if(a[i]>('1'+j))
{ b[top++]='1'+j; j++; }
else if(a[i]==('1'+j))
{ i++; j++; }
else
{if(a[i]==b[--top])
i++; } }
if(top)
while(i<=n)
if(a[i]==b[--top])
i++;
else return 0;
return 1; }
4 結(jié)束語
本文對棧大小不受限制和棧大小受限制兩種情況下，給定入棧序列（1 2 … n），對判斷序列a1a2…an是否是出棧序列的問題進行分析研究。先給出出棧序列應(yīng)滿足的性質(zhì)，依據(jù)性質(zhì)，先采用窮舉法給出判斷的算法及程序
實現(xiàn)，然后模擬入棧出棧過程，給出判斷的改進算法及程序?qū)崿F(xiàn)。本文算法較直觀，易于理解，程序均經(jīng)過測試，輸出正確。
參考文獻
[1] 張先偉,曹雁鋒. 用插入法解決堆棧輸出問題[J]. 計算機應(yīng)用與軟件, 2007,24(11):169-171.
[2] 唐銳. 用后繼序列法解決堆棧輸出問題[J]. 小型微型計算機系統(tǒng), 2006,27(12):2314 -2316.
[3] 徐鳳生. 出棧序列的性質(zhì)及其求解新算法[J]. 計算機工程與應(yīng)用, 2006,42(5):66-68.
[4] 何坤金,陳正鳴,楊垠. 基于算子的棧序列生成算法與實現(xiàn)[J].計算機工程與設(shè)計, 2006,27(12):2266-2267,2287.
[5] 唐保祥. 棧序列及其生成算法[J]. 鄭州大學(xué)學(xué)報, 2001,33(4):33-35.
[6] 李紅衛(wèi),徐亞平. 出棧序列的研究[J]. 計算機技術(shù)與發(fā)展, 2007,17(10):127-129,133.
[7] 袁紅娟. 基于鏈表的出棧序列生成算法[J]. 河北北方學(xué)院學(xué)報(自然科學(xué)版), 2006, 22(5):71-75.
[8] 韓靜.“數(shù)據(jù)結(jié)構(gòu)”課程中出棧序列的一種求解算法[J]. 計算機教育, 2008,6(23):68-70.
[9] 吳集林. 用二叉樹解決出棧序列問題[J]. 贛南師范學(xué)院學(xué)報, 2005,26(6):28 -30.