出棧序列生成的算法研究與設(shè)計(jì)

王防修，周 康

(武漢工業(yè)學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北武漢430023)

棧的應(yīng)用非常廣泛，諸如電網(wǎng)優(yōu)化、各種智能算法都需要用到棧?？梢哉f(shuō)，幾乎所有高級(jí)算法的程序?qū)崿F(xiàn)都需要用到棧，沒有棧，這些算法的實(shí)現(xiàn)將寸步難行。因此，數(shù)據(jù)結(jié)構(gòu)［1］中棧的學(xué)習(xí)非常重要。事實(shí)上，只有在用棧解決實(shí)際問題時(shí)才能充分體會(huì)棧的作用。雖然棧是一種先進(jìn)后出的線性表，但什么時(shí)候入棧和什么時(shí)候出棧不是隨意的，而是由實(shí)際問題決定的。許多人在學(xué)習(xí)棧時(shí)，由于書中所舉例子的局限性，導(dǎo)致許多人對(duì)棧的認(rèn)識(shí)比較膚淺，進(jìn)而使得他們不能靈活任用棧來(lái)解決實(shí)際問題。所以，筆者希望通過對(duì)出棧序列的生成算法［2］介紹和實(shí)現(xiàn)來(lái)提高大家對(duì)棧的認(rèn)識(shí)，最終使大家能夠自覺任用棧來(lái)解決各種實(shí)際問題。

1 問題描述和分析

1.1 問題描述

根據(jù)問題的規(guī)模由小到大和問題的難度由低到高，可將其歸納為以下兩個(gè)方面:

(1)有四個(gè)元素 a，b，c，d 依次入棧，任何時(shí)候都可以出棧，請(qǐng)寫出所有可能的出棧序列［3－11］和所有不存在的序列。

(2)有多個(gè)元素依次入棧，任何時(shí)候都可以出棧，請(qǐng)寫出所有可能的出棧序列。

1.2 問題分析

對(duì)于問題(1)，由排列組合可知，這4個(gè)元素可以組成4!=24個(gè)不同的元素序列，并且這些元素序列分別為:abcd;abdc;acbd;acdb;adbc;adcb;bacd;badc;bcad;bcda;bdac;bdca;cabd;cadb;cbad;cbda;cdab;cdba;dabc;dacb;dbac;dbca;dcab;dcba。

由棧的先進(jìn)后出特性，可以得到所有的出棧序列分別為:abcd;abdc;acbd;acdb;adcb;bacd;badc;bcad;bcda;bdca;cbad;cbda;cdba;dcba。所有不可能的序列為:adbc;bdac;cabd;cadb;cdab;dabc;dacb;dbac;dbca;dcab。

顯然，對(duì)問題(1)，采用的是窮舉法同時(shí)又是手工計(jì)算的方式得到所有的出棧序列和所有不可能的序列。然而，這種方法只適合入棧元素很少的情況。事實(shí)上，當(dāng)入棧元素有6個(gè)時(shí)，由于可以組成6!=720個(gè)不同的元素序列，如果此時(shí)仍采用手工方式計(jì)算所有可能的出棧序列，將需要花費(fèi)大量時(shí)間，并且很容易出錯(cuò)。

因此，用手工方式計(jì)算問題是不現(xiàn)實(shí)的。如果能夠發(fā)現(xiàn)出棧序列的某種共同規(guī)律，在此基礎(chǔ)上進(jìn)而形成一種算法，那么問題(2)就迎刃而解。

2 算法思想及構(gòu)造

2.1 算法思想

定義1 設(shè)n個(gè)元素x1，x2，…，xn依次入棧，并且任何時(shí)候棧頂元素可以出棧，則得到的一系列出棧元素稱為出棧系列。

性質(zhì)1 如果入棧元素有n個(gè)，則需要進(jìn)行n次入棧操作和n次出棧操作。

性質(zhì)2 沒有入棧就沒有出棧，因此入棧操作比出棧操作先發(fā)生。

性質(zhì)3 如果用字符‘1’表示入棧操作和用字符‘0’表示出棧操作，那么得到一個(gè)長(zhǎng)度為n的出棧序列需要經(jīng)過一個(gè)長(zhǎng)度為2n的二進(jìn)制字符串棧操作序列。

定義2 如果從左往右依次對(duì)二進(jìn)制字符串棧操作序列進(jìn)行順序編號(hào)，則從第1位到第i位所形成的二進(jìn)制字符串稱為第i位左子串。

性質(zhì)4 棧操作序列的每一位左子串中字符‘1’的個(gè)數(shù)不得少于字符‘0’的個(gè)數(shù)。

證明:如果左子串中字符‘1’的個(gè)數(shù)少于字符‘0’的個(gè)數(shù)，那么當(dāng)棧中的元素全部出棧后，還需要進(jìn)一步出棧，而此時(shí)棧中已經(jīng)沒有元素，因此就會(huì)發(fā)生出棧錯(cuò)誤。

性質(zhì)5 棧操作序列中字符‘0’的個(gè)數(shù)與字符‘1’的個(gè)數(shù)相同。

證明:如果棧操作序列中字符‘0’的個(gè)數(shù)少于字符‘1’的個(gè)數(shù)，那么出棧元素的個(gè)數(shù)就會(huì)少于n，從而也就不可能得到出棧序列;反之，如果棧操作序列中字符‘0’的個(gè)數(shù)多于字符‘1’的個(gè)數(shù)，就會(huì)發(fā)生出棧錯(cuò)誤，同樣得不到出棧序列。

通過對(duì)棧操作序列性質(zhì)的分析，不難發(fā)現(xiàn)，棧操作序列與出棧序列存在一一映射的關(guān)系。

現(xiàn)在來(lái)判斷一個(gè)長(zhǎng)度為8的二進(jìn)制字符串是否是4個(gè)入棧元素的棧操作序列。已知二進(jìn)制字符串“11001010”，那么該字符串是否是棧操作序列呢?首先，該二進(jìn)制序列有4個(gè)‘1’和4個(gè)‘0’，滿足性質(zhì)1、性質(zhì)3和性質(zhì)5。其次，該二進(jìn)制字符串的第一位是‘1’，滿足性質(zhì)2。最后，不難發(fā)現(xiàn)，字符串中每一位的左子串中字符‘1’的個(gè)數(shù)都不少于字符‘0’的個(gè)數(shù)，滿足性質(zhì)5。因此，該二進(jìn)制字符串是一個(gè)出棧序列。如果依次入棧的四個(gè)元素是a，b，c，d，那么由該棧操作序列“11001010”依次執(zhí)行的棧操作是:a入棧;b入棧;b出棧;a出棧;c入棧;c出棧;d入棧;d出棧。因此，該棧操作序列對(duì)應(yīng)的出棧序列是 bacd。再判斷二進(jìn)制字符串“11000110”是否是棧操作序列，由于該字符串的第5位的左子串中字符‘0’的個(gè)數(shù)3比字符‘1’的個(gè)數(shù)2多，故該字符串不滿足性質(zhì)4，以致該字符串不是棧操作序列。

從上面的分析可知，只要找出所有的棧操作序列，就可以找到所有的出棧序列?？傊?，棧操作序列具有下列特征:

(1)如果依次輸入的元素有n個(gè)，那么棧操作序列就是長(zhǎng)度為2n的二進(jìn)制字符串;

(2)棧操作序列的第一個(gè)字符一定是‘1’;

(3)棧操作序列的最后一個(gè)字符一定是‘0’;

(4)棧操作序列中‘1’和‘0’的個(gè)數(shù)相同;

(5)棧操作序列的每一位的左子串中‘1’的個(gè)數(shù)不少于‘0’的個(gè)數(shù)。

2.2 算法構(gòu)造

設(shè)x1，x2，…，xn是依次入棧的n個(gè)元素，則由棧操作序列的性質(zhì)和特征，可知棧操作序列應(yīng)該在“10…0”(2n－1個(gè)‘0’字符)至“1…1”(2n個(gè)‘1’字符)中進(jìn)行選擇。為此，可以充分利用將數(shù)字轉(zhuǎn)換為子字符串的轉(zhuǎn)換函數(shù)itoa(k，str，2)，該命令的功能是將整數(shù)k轉(zhuǎn)換成二進(jìn)制字符串并且保存在字符數(shù)組str中。比如22n－1經(jīng)轉(zhuǎn)換后就變成了“10…0”(2n－1個(gè)‘0’字符)，22n－1經(jīng)轉(zhuǎn)換后就變成了“1…1”(2n個(gè)‘1’字符)。這意味著可以在22n－1至22n－1之間搜索棧操作序列。

因此，具體算法描述如下:

步驟1 初始化k=22n－1和入棧元素序列S=“x1x2…xn”。

步驟2 執(zhí)行itoa(k，str，2)，可將整數(shù)k變?yōu)殚L(zhǎng)度為2n二進(jìn)制字符串str。

步驟3 判斷str是否是棧操作序列:

(1)如果str中出現(xiàn)字符‘0’與字符‘1’的個(gè)數(shù)不等，則跳到步驟5;

(2)如果str中出現(xiàn)某一位的左子串中字符‘0’的個(gè)數(shù)多于字符‘1’的個(gè)數(shù)，則跳到步驟5。

步驟4 對(duì)入棧元素序列S執(zhí)行棧操作序列:

(1)設(shè) p=q=0，使得 S［p］=‘x1’，q指向 str的第一個(gè)字符;

(2)當(dāng) str［q］=‘1’，則將 S［p］入棧，同時(shí)執(zhí)行p=p+1，使 p指向下一個(gè)入棧元素;當(dāng) str［q］=‘0’，將棧頂元素彈棧;

(3)q=q+1，是指向下一個(gè)操作字符;

(4)當(dāng)q＜2n，則返回到(2);

(5)由所有的出棧元素按先后關(guān)系得到一個(gè)出棧序列。

步驟5 執(zhí)行k=k+1。

步驟6 當(dāng)k＜2n－1，則返回到步驟2。

步驟7 循環(huán)結(jié)束，得到所有的出棧序列。

3 算法分析［12］及改進(jìn)

3.1 算法分析

本算法采用枚舉法來(lái)選擇棧操作序列，因此得到的一定全部最優(yōu)解。由于算法中的k從22n－1開始，故計(jì)算量減少了一半。由于要找到所有的出棧序列，只有用枚舉才能做到這一點(diǎn)。本算法所耗費(fèi)的時(shí)間主要體現(xiàn)兩個(gè)方面:(1)從二進(jìn)制字符串中選擇棧操作序列;(2)根據(jù)棧操作序列得到出棧序列。

由于算法中的k是無(wú)符號(hào)長(zhǎng)整型，因此它最多能表示長(zhǎng)度為32的二進(jìn)制字符串，從而也就只能滿足入棧元素不多于16個(gè)的情形。對(duì)于依次入棧的元素如果多于16個(gè)，則本算法無(wú)能為力。為了能求出入棧元素更多的出棧序列，必須對(duì)本算法加以改進(jìn)。

3.2 改進(jìn)算法

當(dāng)將上述算法由單循環(huán)變成雙循環(huán)，則入棧元素的個(gè)數(shù)由原來(lái)最多16個(gè)擴(kuò)大到最多32.具體做法是用兩個(gè)無(wú)符號(hào)整數(shù)(共64位)對(duì)應(yīng)一個(gè)長(zhǎng)度為64的二進(jìn)制字符串。

改進(jìn)算法描述如下:

步驟1 初始化k1=2n－1和入棧元素序列S=“x1x2…xn”;

步驟2 執(zhí)行 itoa(k1，str1，2)，可將整數(shù) k1變?yōu)殚L(zhǎng)度為n二進(jìn)制字符串str1;

步驟3 初始化k2和str2=“0…0”(n個(gè)0);

步驟4 執(zhí)行 itoa(k2，str3，2)，strcpy(str2+n －strlen(str3)，str3)，strcpy(str，str2)和 strcat(str，str2);

步驟5 判斷str是否是棧操作序列:

(1)如果str中出現(xiàn)字符‘0’與字符‘1’的個(gè)數(shù)不等，則跳到步驟7;

(2)如果str中出現(xiàn)某一位的左子串中字符‘0’的個(gè)數(shù)多于字符‘1’的個(gè)數(shù)，則跳到步驟7;步驟6 對(duì)入棧元素序列S執(zhí)行棧操作序列:

(1)設(shè) p=q=0，使得 S［p］=‘x1’，q指向 str的第一個(gè)字符;

(2)當(dāng) str［q］=‘1’，則將 S［p］入棧，同時(shí)執(zhí)行p=p+1，使 p指向下一個(gè)入棧元素;當(dāng) str［q］=‘0’，將棧頂元素彈棧;

(3)q=q+1，是指向下一個(gè)操作字符;

(4)當(dāng)q＜2n，則返回到(2);

(5)由所有的出棧元素按先后關(guān)系得到一個(gè)出棧序列。

步驟7 執(zhí)行k2=k2+1;

步驟8 當(dāng)k2＜2n－1，則返回到步驟4;

步驟9 執(zhí)行k1=k1+1;

步驟10 當(dāng)k1＜2n－1，則返回到步驟2;

步驟11 循環(huán)結(jié)束，得到所有的出棧序列。

以上算法可以解決入棧元素個(gè)數(shù)大于16但不超過32的情況，至于入棧元素超過32的情形，只需采用三重循環(huán)即可。類似算法容易寫出，這里不再獒述。

4 算法測(cè)試

假設(shè)問題(2)的入棧元素序列是abcdefghijklmnopqrst，那么其中的部分出棧序列如表1所示。

表1 20個(gè)元素依次入棧所產(chǎn)生的部分出棧序列

測(cè)試結(jié)果表明，棧操作序列與出棧序列存在一一對(duì)應(yīng)關(guān)系，不同的棧操作序列對(duì)應(yīng)不同的出棧序列。同時(shí)，入棧的元素越多，需要選擇的二進(jìn)制字符串?dāng)?shù)目越多，因此程序所花費(fèi)的時(shí)間越多。對(duì)算法進(jìn)行分析可知，該算法的時(shí)間復(fù)雜度為O(2n)［13］。

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

求入棧元素比較多的出棧序列時(shí)，程序在執(zhí)行過程中需要花費(fèi)大量時(shí)間。但是，這是因?yàn)橛酶F舉法求所有出棧序列造成的。然而，很多求最優(yōu)解的問題，運(yùn)用棧知識(shí)可以很快求出最優(yōu)解。求出棧序列本身就不是一件容易的事情，沒有對(duì)棧的充分理解和認(rèn)識(shí)，是無(wú)法用算法來(lái)求所有的出棧序列的。因此，在從事教學(xué)和科研過程中，只有充分認(rèn)識(shí)所要解決的問題，才能靈活運(yùn)用棧來(lái)解決實(shí)際問題。通過出棧序列的求取，真正認(rèn)識(shí)到棧的強(qiáng)大威力和有效性。

［1］嚴(yán)蔚敏，吳偉明.數(shù)據(jù)結(jié)構(gòu)(第二版)［M］.北京:清華大學(xué)出版社，2000.

［2］朱大銘，馬紹漢.算法設(shè)計(jì)與分析［M］.北京:高等教育出版社，2009.

［3］吳集林.關(guān)于出棧序列、二叉樹、二叉搜索樹三個(gè)問題計(jì)數(shù)的一致性［J］.廣東廣播電視大學(xué)學(xué)報(bào)，2005，56(4):106 －107.

［4］吳集林.用二叉樹解決出棧序列問題［J］.贛南師范學(xué)院學(xué)報(bào)，2005，6:28 －30.

［5］徐鳳生.出棧序列的性質(zhì)及其求解新算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006，5:66 －68.

［6］袁紅娟.基于鏈表的出棧序列生成算法［J］.河北北方學(xué)院學(xué)報(bào)，2006，22(5):70 －75.

［7］李紅衛(wèi)，徐亞平.出棧序列的研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2007，17(10):127 －129.

［8］張先偉，曹雁鋒.用插入法解決堆棧輸出問題［J］.計(jì)算機(jī)應(yīng)用與軟件，2007，24(11):169 －171.

［9］韓靜.“數(shù)據(jù)結(jié)構(gòu)”課程中出棧序列的一種求解算法［J］.計(jì)算機(jī)教育，2008，23:67 －68.

［10］于林.關(guān)于數(shù)據(jù)結(jié)構(gòu)中出棧序列問題的討論［J］.計(jì)算機(jī)光盤軟件與應(yīng)用，2011，7:111 －112.

［11］吳福英，譚羅生，黃超.一個(gè)判定出棧序列的新方法［J］江西師范大學(xué)學(xué)報(bào)，2011，35(3):251－253.

［12］Mark Allen Weiss.Data Structures and Algorithm Analysis in C:Second Edition［M］.北京:人民郵電出版社，2005.

［13］(美)Robert Sedgewick，(法)Philippe Flajolet.算法分析導(dǎo)論［M］.馮舜璽，李學(xué)武，裴偉東，等.北京:機(jī)械工業(yè)出版社，2006.