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