姜華林　李立新　陳強(qiáng)

摘要：棧是一種非常重要且特殊的數(shù)據(jù)結(jié)構(gòu)，任何遞歸和函數(shù)調(diào)用都離不開棧。研究n個(gè)元素的進(jìn)棧與出棧性質(zhì)是棧的主要研究?jī)?nèi)容。該文在出棧序列深入分析和研究的基礎(chǔ)上，針對(duì)某一序列是否為合法出棧序列的問題，提出了一種基于三元素出棧序列索引的時(shí)間復(fù)雜度為O（n2）的新算法。該算法簡(jiǎn)單易懂并且比其他傳統(tǒng)判斷方法具有更高的效率。

關(guān)鍵詞：棧；數(shù)據(jù)結(jié)構(gòu)；出棧序列；三元素索引；算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）07-1578-04

已知一個(gè)元素為n（n≥3，n<3時(shí)結(jié)果很顯然，因此不必研究）的進(jìn)棧序列設(shè)為S（a0，a1， a2，…，an-1），再設(shè)T（b0，b1， b2，…，bn-1）為進(jìn)棧序列S（a0，a1， a2，…，an-1）的一個(gè)置換，則T（b0，b1， b2，…，bn-1）是否為一個(gè)合法的出棧序列是一個(gè)值得深入研究的問題。文獻(xiàn)[1～7]對(duì)其相關(guān)問題進(jìn)行了分析和研究。對(duì)此文獻(xiàn)[2]給出了一個(gè)算法思想簡(jiǎn)單但時(shí)間復(fù)雜度較高（O（n3））的判定算法；文獻(xiàn)[6]給出了一個(gè)基于棧的判斷算法，它通過對(duì)入棧、出棧操作的反演得出判斷，其時(shí)間復(fù)雜度雖然較低（為O（n2）），但它沒有分析出棧序列本身具有的特性[7]；文獻(xiàn)[7]提出了一種基于降序段的時(shí)間復(fù)雜度為O （n2）的算法但仍然較為復(fù)雜。該文對(duì)出棧序列性質(zhì)進(jìn)行了進(jìn)一步的分析和研究，在此基礎(chǔ)上提出了一種基于三元素出棧序列索引的新方法，該方法可以快速有效地判定T（b0，b1， b2，…，bn-1）是否為一個(gè)合法的出棧序列，給出了一種更為優(yōu)化的算法實(shí)現(xiàn)；同時(shí)根據(jù)棧的性質(zhì)利用非棧算法實(shí)現(xiàn)了對(duì)元素為n（n≥3）的進(jìn)棧序列S（a0，a1， a2，…，an-1）的進(jìn)棧與出棧模擬。

1 問題分析

為了便于問題描述引入三元素出棧序列索引J（x，y，z）。

定義1 J（x，y，z）中x，y，z分別表示某個(gè)元素進(jìn)棧的索引序號(hào)，J（x，y，z）表示x對(duì)應(yīng)元素最先出棧，y對(duì)應(yīng)元素第二出棧，z對(duì)應(yīng)元素最后出棧。

定義2 J（x，y，z）中如果x對(duì)應(yīng)元素比y對(duì)應(yīng)元素先進(jìn)棧，則稱為xy。

定義3 元素a進(jìn)棧表示為a+，出棧表示為a-。

定義4 元素a0，a1，a2進(jìn)棧與出棧的整個(gè)過程稱為棧序列，記為R（c0，c1，c2，c3，c4，c5），其中ci表示某個(gè)元素進(jìn)?；蛘叱鰲！＠?，“abc”為進(jìn)棧序列，“bac”為出棧序列，則其棧序列為“a+b+b-a-c+c-”即“a進(jìn)棧b進(jìn)棧b出棧a出棧c進(jìn)棧c出?！保琑（c0，c1，c2，c3，c4，c5）={abc}∪{bac}。

性質(zhì)1 已知一個(gè)元素為n（n≥3）的進(jìn)棧序列S（a0，a1， a2，…，an-1），其某一置換為T（b0，b1， b2，…，bn-1），則任取T（b0，b1， b2，…，bn-1）中三個(gè)元素可得相應(yīng)的三元素出棧序列索引J（x，y，z）。

性質(zhì)2 如果元素a0，a1，a2按序進(jìn)棧，a0的進(jìn)棧序號(hào)稱為“前”記為P，a1的進(jìn)棧序號(hào)稱為“中”記為N，a2的進(jìn)棧序號(hào)稱為“后”記為L(zhǎng)（該性質(zhì)便于出棧序列判斷的直觀理解）。

性質(zhì)3 如果元素a0，a1，a2按序進(jìn)棧，其出棧序列共有5種可能，也對(duì)應(yīng)J（x，y，z）中x、y和z的5種關(guān)系，具體為：

1）PNL（前中后），x

2）PLN（前后中），x

3）NLP（中后前），y>x>z；

4）NPL（中前后），y

5）LNP（后中前），x>y>z；

定理1 J（x，y，z）中如果x>z>y，則稱J（x，y，z）為三元素非法出棧序列索引，特記為J（x，y，z）。

證

1）根據(jù)定義1，設(shè)x對(duì)應(yīng)元素為ai，設(shè)y對(duì)應(yīng)元素aj，設(shè)z對(duì)應(yīng)元素ak，出棧序列為ai、aj、ak；

2）根據(jù)定義2和條件x>z>y，則三元素進(jìn)棧序列為：aj、ak、ai；

由上可知，元素ai是最先出棧的，同時(shí)ai是最后進(jìn)棧的，這說明在ai進(jìn)棧之前aj和ak已經(jīng)進(jìn)棧但沒有出棧，而aj比ak先進(jìn)棧，那么根據(jù)棧的先進(jìn)后出性質(zhì)可知，aj必然比ak后出棧，反之假設(shè)aj比ak先進(jìn)棧，同時(shí)aj比ak先出棧，那么aj必然是最先出棧的元素，這與ai是最先出棧的元素相矛盾，所以出棧序列ai、aj、ak為非法出棧序列，該J（x，y，z） 為三元素非法出棧序列索引。

推論1 如果一個(gè)元素為n（n≥3）的進(jìn)棧序列S（a0，a1， a2，…，an-1）的任一出棧序列為T（b0，b1， b2，…，bn-1），那么序列T（b0，b1， b2，…，bn-1）中不存在LPN（后前中）的這樣一個(gè)三元素非法出棧序列索引J（x，y，z）。

由定理1可證。

推論2 如果一個(gè)元素為n（n≥3）的序列T（b0，b1， b2，…，bn-1）是進(jìn)棧序列S（a0，a1， a2，…，an-1）的某一合法出棧序列，那么必然存在棧序列R（c0，c1， c2，…，cn-1），R（c0，c1， c2，…，cn-1）= S（a0，a1， a2，…，an-1）∪T（b0，b1， b2，…，bn-1）。

由推論1和定義4可證。

2 出棧序列判斷算法

該算法核心思想是在要判斷的出棧序列T（b0，b1， b2，…，bn-1）中查找是否存在LPN（后前中）的這樣一個(gè)三元素非法出棧序列索引J（x，y，z），若存在則該出棧序列非法，反之為合法出棧序列。具體操作步驟如下：

1）將出棧序列T（b0，b1， b2，…，bn-1）中的每一個(gè)元素的進(jìn)棧序號(hào)存入出棧索引數(shù)組；

2）設(shè)i，j為計(jì)數(shù)器，i初值為出棧索引數(shù)組的長(zhǎng)度減1，j初值為i減1；

3）如果i >1，將出棧索引數(shù)組第個(gè)i元素的值賦給三元素出棧序列索引J（x，y，z）中的z，否則執(zhí)行第6）步；

4）如果出棧索引數(shù)組第個(gè)j元素的值小于z，則將出棧索引數(shù)組第個(gè)j元素的值賦給三元素出棧序列索引J（x，y，z）中的y，執(zhí)行第5）步；否則j=j-1，反復(fù)執(zhí)行此步直至j=0，然后i=i-1，執(zhí)行第3）步；

5）j=j-1，如果出棧索引數(shù)組第個(gè)j元素的值大于z，則將出棧索引數(shù)組第個(gè)j元素的值賦給三元素出棧序列索引J（x，y，z）中的x，執(zhí)行第7）步；否則j=j-1，反復(fù)執(zhí)行此步直至j<0，然后i=i-1，執(zhí)行第3）步；

6）算法結(jié)束，出棧序列為合法出棧序列；

7）算法結(jié)束，出棧序列為非法出棧序列。

時(shí)間復(fù)雜度為O（n2） 。

算法的關(guān)鍵源碼如下（C#）：

1）置所有元素進(jìn)棧標(biāo)識(shí)為0，置棧序列為空；

2）依次掃描第i個(gè)出棧序號(hào)，若出棧序號(hào)與進(jìn)棧序號(hào)一致，執(zhí)行3），否則執(zhí)行5）；

3）若當(dāng)前序號(hào)對(duì)應(yīng)元素進(jìn)棧標(biāo)識(shí)不為0，執(zhí)行4），否則該元素加入棧序列，模擬該元素進(jìn)棧，同時(shí)置進(jìn)棧標(biāo)識(shí)為1，執(zhí)行4）；

4）當(dāng)前序號(hào)對(duì)應(yīng)元素加入棧序列，模擬該元素出棧，執(zhí)行6）；

5）將比當(dāng)前序號(hào)小的所有序號(hào)所對(duì)應(yīng)元素加入棧序列，模擬所有對(duì)應(yīng)元素進(jìn)棧，同時(shí)置所有進(jìn)棧標(biāo)識(shí)為1，執(zhí)行3）；

6）若出棧序號(hào)已經(jīng)掃描完成，執(zhí)行7），否則i=i+1，執(zhí)行2）；

7）結(jié)束，返回棧序列。

算法的關(guān)鍵源碼如下（C#）：

4 結(jié)束語(yǔ)

本文深入研究出棧序列合法性的規(guī)律后，在進(jìn)棧序列所有元素任意排列的序列中抽象出三元素出棧序列索引J（x，y，z），根據(jù)三元素出棧序列索引J（x，y，z）的特性確定了三元素非法出棧序列索引J（x，y，z），用C#語(yǔ)言實(shí)現(xiàn)了基于三元素出棧序列索引的時(shí)間復(fù)雜度為O（n2）的新算法。該算法簡(jiǎn)單易懂并且比其他傳統(tǒng)判斷方法具有更高的效率。同時(shí)利用非棧算法實(shí)現(xiàn)了對(duì)元素為n（n≥3）的出棧序列T（b0，b1， b2，…，bn-1）的進(jìn)棧與出棧模擬，由此推論2得到了驗(yàn)證。下一步，將繼續(xù)對(duì)棧的性質(zhì)進(jìn)行深入研究，探討棧在其他應(yīng)用領(lǐng)域中的高效算法。

參考文獻(xiàn)：

[1] 盧開澄.組合數(shù)學(xué)[M]. 2版.北京：清華大學(xué)出版社，1991：119-130.

[2] 徐鳳生.出棧序列的性質(zhì)及其求解新算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（5）：66-68.

[3] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)：C語(yǔ)言版[M].北京：清華大學(xué)出版社，1997：152-155.

[4] 唐保祥.棧序列及其生成算法[J].鄭州大學(xué)學(xué)報(bào)：自然科學(xué)版，2001，33（4）：33-35.

[5] 范年柏，張大方，顏學(xué)義，等.基于棧操作的用例規(guī)模的一個(gè)計(jì)算公式[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，31（6）：80-82.

[6] 李紅衛(wèi)，徐亞平.出棧序列的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007，17（10）：127-129.

[7] 吳福英，譚羅生，黃超.一個(gè)判定出棧序列的新方法[J].江西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（3）：251-253.