數(shù)據(jù)結(jié)構(gòu)（從概念到算法）課件

第3章棧與隊(duì)列01020304目錄CONTENTS棧隊(duì)列應(yīng)用實(shí)例本章小結(jié)01PART棧3.1.1棧的基本概念棧是限定在表尾做插入、刪除操作的線性表。向棧中插入元素叫作進(jìn)棧，從棧中刪除元素叫作出棧，棧的表頭叫作棧底，棧的表尾叫作棧頂。為了明晰棧底和棧頂?shù)母拍?，通常使用“井”狀圖形表示一個(gè)棧。進(jìn)棧：向棧中插入一個(gè)元素。其也稱(chēng)為入棧、推入、壓入、push。出棧：從棧刪除一個(gè)元素。其也稱(chēng)為退棧、上托、彈出、pop。棧頂：允許插入、刪除元素的一端（表尾）。棧頂元素：處在棧頂位置的元素（表尾元素）。棧底：表中不允許插入、刪除元素的一端（表頭）?？諚＃翰缓氐臈?。棧中元素的進(jìn)出原則：“后進(jìn)先出”（Last

In

First

Out）。棧的別名：“后進(jìn)先出”表、LIFO

表、反轉(zhuǎn)存儲(chǔ)器、堆棧。棧3.1.2棧的抽象數(shù)據(jù)類(lèi)型棧3.1.3棧的操作特性下面以火車(chē)調(diào)度站為例來(lái)理解棧的操作特性。假定火車(chē)調(diào)度站滿(mǎn)足棧的插入、刪除規(guī)則，列車(chē)只能在一端進(jìn)站、出站，現(xiàn)有3輛列車(chē)

A、B、C依次進(jìn)入火車(chē)調(diào)度站，那么列車(chē)A、B、C的出站順序會(huì)有下面幾種不同組合：棧3.1.3棧的操作特性第一種組合：輸入順序?yàn)锳,B,C，產(chǎn)生輸出為A,B,C。其過(guò)程為：A進(jìn)?！鶤出?！鶥進(jìn)?！鶥出?！鶦進(jìn)?！鶦出棧。在此進(jìn)、出棧順序下，列車(chē)出站順序（棧的輸出序列）即為A,B,C。棧3.1.3棧的操作特性第二種組合：輸入順序?yàn)锳,B,C，產(chǎn)生輸出為C,B,A。其過(guò)程為：A進(jìn)?！鶥

進(jìn)?！鶦

進(jìn)?！鶦

出?！鶥

出?！鶤

出棧。在此進(jìn)、出棧順序下，列車(chē)出站順序（棧的輸出序列）即為C,B,A。類(lèi)似地，可以得出另外組合：B,C,A、A,C,B

和B,A,C。然而，以A,B,C

為輸入序列時(shí)，無(wú)論采用何種進(jìn)、出棧順序都無(wú)法產(chǎn)生C,A,B的輸出序列。其原因?yàn)椋篊

的輸出需要以C

的進(jìn)棧為前提，輸出

C

之前，所有尚未輸出的、C

的前序元素（A

和

B）都需要存儲(chǔ)在棧中，而輸出

C

之后，所有尚未輸出的、C

的前序元素均應(yīng)以逆序順序輸出（即

C,B,A），故無(wú)法輸出序列C,A,B。擴(kuò)展上述結(jié)論可知，以(…,ai,…,aj,…,ak,…)作為棧的輸入序列時(shí)，無(wú)法得到輸出序列(…,ak,…,ai,…,aj,…)。棧3.1.4棧的順序存儲(chǔ)結(jié)構(gòu)使用順序存儲(chǔ)結(jié)構(gòu)構(gòu)建的棧稱(chēng)為順序棧。對(duì)順序棧進(jìn)行操作時(shí)，需要考慮以下幾點(diǎn)：存儲(chǔ)空間的分配方式；棧頂標(biāo)識(shí)top：top是指向棧頂元素還是指向棧頂元素下一位置；滿(mǎn)棧和空棧的條件：是top指向棧頂元素情況下的滿(mǎn)棧、空棧條件還是top指向棧頂元素下一位置情況下的滿(mǎn)棧、空棧條件。棧3.1.4棧的順序存儲(chǔ)結(jié)構(gòu)假定

top

始終指向棧頂元素，任意棧

s

的特征如下。（1）非空棧條件：top>=0（2）滿(mǎn)棧條件：top==maxlength-1（3）空棧條件：top==-1（4）進(jìn)棧過(guò)程：先對(duì)top加1，使top指向棧頂元素下一空位置，然后將待插入數(shù)據(jù)賦予s[top]，完成進(jìn)棧操作（5）出棧過(guò)程：先取出棧頂元素s[top]，然后對(duì)top減1，使top指向新的棧頂元素，完成出棧操作棧3.1.4棧的順序存儲(chǔ)結(jié)構(gòu)當(dāng)

top

始終指向棧頂元素下一位置時(shí)，任意棧

s

的特征如下。（1）非空棧條件：top>=1（2）滿(mǎn)棧條件：top==maxlength（3）空棧條件：top==0（4）進(jìn)棧過(guò)程：先將待插入數(shù)據(jù)賦予s[top]，然后對(duì)top加1，使top指向棧頂元素下一空位置，完成進(jìn)棧操作（5）出棧過(guò)程：對(duì)top減1，使top指向原來(lái)的棧頂元素棧3.1.4棧的順序存儲(chǔ)結(jié)構(gòu)接下來(lái)，介紹順序棧的靜態(tài)分配與動(dòng)態(tài)分配。其中，靜態(tài)分配時(shí)需要定義棧的空間和棧頂標(biāo)識(shí)；動(dòng)態(tài)分配需要定義棧的首地址、棧頂標(biāo)識(shí)和當(dāng)前?？臻g的大小。具體分配方式如下：（1）靜態(tài)分配棧3.1.4棧的順序存儲(chǔ)結(jié)構(gòu)（2）動(dòng)態(tài)分配：對(duì)比線性表靜態(tài)（動(dòng)態(tài)）分配方式與棧的靜態(tài)（動(dòng)態(tài)）分配方式可知，在棧的分配方式中，使用了棧頂標(biāo)識(shí)top替代線性表分配方式中的表長(zhǎng)。根據(jù)上述分析，約定top指向棧頂元素下一位置，給出如下動(dòng)態(tài)分配順序棧的基本操作算法。棧3.1.4棧的順序存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)動(dòng)態(tài)分配順序棧的初始化算法——InitStack函數(shù)。首先，調(diào)用malloc函數(shù)為順序棧分配存儲(chǔ)空間，然后為棧頂標(biāo)識(shí)top和當(dāng)前空間大小stacksize賦值。棧3.1.4棧的順序存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)進(jìn)棧算法——Push函數(shù)。首先，判斷棧是否已滿(mǎn)，如果棧已滿(mǎn)，就運(yùn)用realloc函數(shù)重新開(kāi)辟更大的?？臻g。如果realloc函數(shù)返回值為空，提示溢出，則更新棧的地址以及棧的當(dāng)前空間大小。最終，新元素入棧，棧頂標(biāo)識(shí)top加1。棧3.1.4棧的順序存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)出棧算法——Pop函數(shù)。首先，根據(jù)棧頂標(biāo)識(shí)top判斷當(dāng)前棧是否是一個(gè)空棧，如果當(dāng)前棧是一個(gè)空棧，提示下溢，否則，更新棧頂標(biāo)識(shí)，取出棧頂元素。棧3.1.5棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)于棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，通常只考慮采用單鏈表作為棧的存儲(chǔ)結(jié)構(gòu)。假定元素進(jìn)棧順序?yàn)閍1,a2,…,an，如果用普通無(wú)頭結(jié)點(diǎn)的單鏈表表示，按其元素輸入順序表示元素間的線性關(guān)系，每個(gè)新進(jìn)入的元素結(jié)點(diǎn)應(yīng)鏈接在表尾，這樣構(gòu)造得到的鏈?zhǔn)綏Ｈ鐖D所示。棧3.1.5棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)但是，上面的結(jié)構(gòu)進(jìn)、出棧的時(shí)間開(kāi)銷(xiāo)大，時(shí)間復(fù)雜度為O(n)。為了解決這一問(wèn)題以提高進(jìn)、出棧的效率，我們可以將結(jié)點(diǎn)指針順序顛倒過(guò)來(lái)，即每個(gè)元素結(jié)點(diǎn)的指針由原來(lái)的指向邏輯上直接后繼元素結(jié)點(diǎn)改成指向邏輯上直接前驅(qū)元素的結(jié)點(diǎn)，如將top指向

an，同樣也能夠正確地維護(hù)元素間的線性關(guān)系。這樣進(jìn)棧時(shí)只是簡(jiǎn)單地將新結(jié)點(diǎn)作為首結(jié)點(diǎn)，出棧時(shí)刪除首結(jié)點(diǎn)即可，因?yàn)闂＞哂泻筮M(jìn)先出的特性。那么進(jìn)、出棧不需要遍歷整個(gè)鏈表，時(shí)間開(kāi)銷(xiāo)就為常數(shù)，時(shí)間復(fù)雜度為O(1)。棧3.1.6棧的應(yīng)用棧的“后進(jìn)先出”特性在實(shí)際操作中應(yīng)用非常廣泛。例如，在高級(jí)語(yǔ)言中允許函數(shù)之間的嵌套調(diào)用和函數(shù)的遞歸調(diào)用，編譯程序就是通過(guò)棧這種數(shù)據(jù)結(jié)構(gòu)來(lái)完成這些執(zhí)行順序的控制的；借助棧也可以將一些遞歸算法改寫(xiě)成非遞歸算法，從而提高算法效率。一般情況下，如果訪問(wèn)到的數(shù)據(jù)在后續(xù)處理中還需繼續(xù)被訪問(wèn)，此時(shí)就需要用某種數(shù)據(jù)結(jié)構(gòu)將其保存起來(lái)。在后續(xù)重復(fù)訪問(wèn)這些數(shù)據(jù)時(shí)，其順序是“后保存的數(shù)據(jù)先被訪問(wèn)，先保存的數(shù)據(jù)后被訪問(wèn)”，這種情況下可運(yùn)用棧這個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)保存這些數(shù)據(jù)和控制相關(guān)數(shù)據(jù)的訪問(wèn)順序。下面列舉了棧的應(yīng)用實(shí)例表達(dá)式求值。棧3.1.6棧的應(yīng)用運(yùn)用棧來(lái)對(duì)表達(dá)式求值，四則混合運(yùn)算的規(guī)則如下。（1）先乘除，后加減（2）先括號(hào)內(nèi)，后括號(hào)外（3）同類(lèi)運(yùn)算，從左至右在這里，約定在運(yùn)算過(guò)程中，當(dāng)兩個(gè)運(yùn)算符相鄰出現(xiàn)時(shí)，q1表示左運(yùn)算符，q2表示右運(yùn)算符。另外，新增一個(gè)運(yùn)算符“#”作為一個(gè)表達(dá)式的開(kāi)始符和結(jié)束符，即將待求值的表達(dá)式表示為#待求值的表達(dá)式#。棧3.1.6棧的應(yīng)用運(yùn)算符的優(yōu)先級(jí)關(guān)系表在運(yùn)算過(guò)程中非常重要，它是判定進(jìn)棧、出棧的重要依據(jù)。θ2θ1+-*/()#+>

>

<

<

<

>

>

->

>

<

<

<

>

>

*>

>

>

>

<

>

>

/>

>

>

>

<

>

>

(<

<

<

<

<

=

)>

>

>

>

>

>

#<

<

<

<

<

=棧3.1.6棧的應(yīng)用下面以分析表達(dá)式4+2*3-12/(7-5)為例來(lái)說(shuō)明求解過(guò)程，從而總結(jié)出表達(dá)式求值的算法。求解中設(shè)置兩個(gè)棧：操作數(shù)棧和運(yùn)算符棧。從左至右掃描表達(dá)式：#4+2*3-12/(7-5)#，最左邊是開(kāi)始符，最右邊是結(jié)束符。表達(dá)式求值的過(guò)程如下表所示：步驟號(hào)操作數(shù)棧運(yùn)算符棧輸入串下步操作說(shuō)明0

#4+2*3-12/(7-5)#操作數(shù)進(jìn)棧14#+2*3-12/(7-5)#p(#)<p(+)，進(jìn)棧24#+2*3-12/(7-5)#操作數(shù)進(jìn)棧342#+*3-12/(7-5)#p(+)<p(*)，進(jìn)棧442#+*3-12/(7-5)#操作數(shù)進(jìn)棧5423#+*-12/(7-5)#p(*)>p(-)，退棧op=*6423#+-12/(7-5)#操作數(shù)退棧，b=3742#+-12/(7-5)#操作數(shù)退棧，a=284#+-12/(7-5)#a*b得c=6，進(jìn)棧946#+-12/(7-5)#p(+)>p(-)，退棧op=+1046#-12/(7-5)#操作數(shù)退棧，b=6114#-12/(7-5)#操作數(shù)退棧，a=412

#-12/(7-5)#a+b得c=10，進(jìn)棧1310#-12/(7-5)#p(#)<p(-)，進(jìn)棧1410#-12/(7-5)#操作數(shù)進(jìn)棧棧151012#-/(7-5)#p(-)<p(/)，進(jìn)棧161012#-

/(7-5)#p(/)<p(()，進(jìn)棧171012#-

/(7-5)#操作數(shù)進(jìn)棧1810127#-

/(-5)#p(()<p(-)，進(jìn)棧1910127#-/(-5)#操作數(shù)進(jìn)棧20101275#-

/(-)#p(-)>p())，退棧op=-21101275#-

/()#操作數(shù)退棧，b=52210127#-

/()#操作數(shù)退棧，a=7231012#-

/()#a-b得c=2，進(jìn)棧2410122#-

/()#p(()=p())，去括號(hào)2510122#-/#p(/)>p(#，退棧op=/2610122#-#操作數(shù)退棧，b=2271012#-#操作數(shù)退棧，a=122810#-#a/b得c=6，進(jìn)棧29106#-#p(-)>p(#)，退棧op=-30106##操作數(shù)退棧，b=63110##操作數(shù)退棧，a=1032

##a-b得c=4，進(jìn)棧334##p(#)=p(#)，算法結(jié)束棧3.1.6棧的應(yīng)用通過(guò)觀察中對(duì)一個(gè)表達(dá)式的求解過(guò)程，我們可以發(fā)現(xiàn)：掃描到的操作數(shù)總是會(huì)被推入操作數(shù)棧；掃描到的運(yùn)算符q

2，一般會(huì)與運(yùn)算符棧的棧頂元素q1進(jìn)行優(yōu)先級(jí)比較，再依據(jù)優(yōu)先級(jí)的大小進(jìn)行不同的操作，直到表達(dá)式只剩結(jié)束符、運(yùn)算符棧只剩開(kāi)始符。操作數(shù)棧的元素即是最后表達(dá)式的求值。算法的主要思想如下。設(shè)s1—操作數(shù)棧，存放暫不參與運(yùn)算的數(shù)和中間結(jié)果；

s2—運(yùn)算符棧，存放暫不參與運(yùn)算的運(yùn)算符。棧3.1.6棧的應(yīng)用（1）置s1、s2為空棧；開(kāi)始符#進(jìn)s2。（2）從表達(dá)式讀取w，w可為操作數(shù)或運(yùn)算符。（3）當(dāng)w!='#'||s2的棧頂運(yùn)算符!='#'時(shí)，重復(fù)以下操作。①若w為操作數(shù)，則w進(jìn)s1，讀取下一w。②若w為運(yùn)算符q

2，則：prior(s2

的棧頂運(yùn)算符q1)<prior(w(q

2))時(shí)，w

進(jìn)s2；讀取下一w；prior(s2

的棧頂運(yùn)算符q1)=prior(w(q

2))，且w=‘)’時(shí)，去括號(hào)，Pop(s2)；讀取下一w；prior(s2

的棧頂運(yùn)算符(q1))>prior(w(q2))時(shí)，Pop(s1,a);Pop(s1,b);Pop(s2,op);c=b

op

a;Push(s1,c);/*op為q1*/q1

和q

2

沒(méi)定義優(yōu)先級(jí)關(guān)系，表達(dá)式有語(yǔ)法錯(cuò)誤，會(huì)報(bào)錯(cuò)（4）s1

的棧頂元素為表達(dá)式的值。02PART隊(duì)列3.2.1隊(duì)列的基本概念隊(duì)列也是插入和刪除操作位置受限的線性表，只允許在表的一端刪除元素，在另一端插入元素。隊(duì)列的別名是“先進(jìn)先出”表、FIFO表、queue等。與隊(duì)列有關(guān)的概念包括以下幾個(gè)?？贞?duì)列：不含元素的隊(duì)列隊(duì)首：隊(duì)列中只允許刪除元素的一端。其一般稱(chēng)為head、front。隊(duì)尾：隊(duì)列中只允許插入元素的一端。其一般稱(chēng)為rear、tail。隊(duì)首元素：處于隊(duì)首的元素隊(duì)尾元素：處于隊(duì)尾的元素。進(jìn)隊(duì)：插入一個(gè)元素到隊(duì)列中。其也稱(chēng)為入隊(duì)。出隊(duì)：從隊(duì)列中刪除一個(gè)元素。隊(duì)列3.2.2隊(duì)列的抽象數(shù)據(jù)類(lèi)型隊(duì)列3.2.3順序隊(duì)列的基本運(yùn)算及實(shí)現(xiàn)順序隊(duì)列是指用一片連續(xù)的地址空間來(lái)存儲(chǔ)元素的隊(duì)列。同樣地，為了方便進(jìn)隊(duì)和出隊(duì)操作，我們需要設(shè)置兩個(gè)標(biāo)識(shí)，分別代表隊(duì)首和隊(duì)尾。例如，一維數(shù)組Q[5]表示順序隊(duì)列，設(shè)置兩個(gè)標(biāo)識(shí)f和r，約定f指向隊(duì)首元素，r指向隊(duì)尾元素后的一個(gè)空單元。這樣r減去f就正好表示隊(duì)列中元素的個(gè)數(shù)；當(dāng)f=r時(shí)，表示隊(duì)列為空。進(jìn)隊(duì)操作，先將新元素保存在r所標(biāo)識(shí)的單元中，然后向后移動(dòng)r；出隊(duì)操作，先取出f指向的隊(duì)首元素，然后向后移動(dòng)f。隊(duì)列3.2.3順序隊(duì)列的基本運(yùn)算及實(shí)現(xiàn)在第（5）步，D,E,F

依次進(jìn)隊(duì)后，r

往后移動(dòng)，r

就會(huì)指向5

單元后面的單元。如果此時(shí)有元素G

進(jìn)隊(duì)，就會(huì)判斷隊(duì)列已滿(mǎn)而出現(xiàn)“溢出”的情況。但這種“溢出”是假溢出，因?yàn)槠鋵?shí)隊(duì)列里面還有空單元Q[0]、Q[1]和Q[2]可以用來(lái)存放元素。解決假溢出的問(wèn)題有以下兩種解決方案：第一種解決方案是移動(dòng)元素。在上面的例子中，如果G想進(jìn)隊(duì)，就先將D,E,F整體往隊(duì)列前端空單元處移動(dòng)，f也移動(dòng)到指向隊(duì)首單元；G進(jìn)隊(duì)后，r往后移動(dòng)指向4單元。這種方法比較費(fèi)時(shí)，移動(dòng)元素的開(kāi)銷(xiāo)較大，需要考慮其他更有效的方案避免元素移動(dòng)，提高進(jìn)隊(duì)與出隊(duì)的效率。隊(duì)列3.2.3順序隊(duì)列的基本運(yùn)算及實(shí)現(xiàn)第二種解決方案是將隊(duì)列Q

當(dāng)循環(huán)表使用，從而使得隊(duì)列成為一個(gè)循環(huán)隊(duì)列。接著上面的例子，D,E,F

進(jìn)隊(duì)后，r

循環(huán)地指向第0

單元；G

進(jìn)隊(duì)后存儲(chǔ)在0

單元，r

往后移動(dòng)，并指向1

單元。隊(duì)列3.2.3順序隊(duì)列的基本運(yùn)算及實(shí)現(xiàn)接著上面的例子，目前隊(duì)列中有D、E、F3個(gè)元素，f指向3單元，r指向1單元。如果此時(shí)H,I進(jìn)隊(duì)，r往后移動(dòng)，并指向3單元，而f也指向3單元，那么f=r，如圖所示。前文中，f=r是空隊(duì)列的條件，但這里f=r表示滿(mǎn)隊(duì)列，這樣就會(huì)出現(xiàn)二義性，違反算法的基本特性。隊(duì)列3.2.3順序隊(duì)列的基本運(yùn)算及實(shí)現(xiàn)解決循環(huán)隊(duì)列的二義性問(wèn)題有兩個(gè)方案：方案一是增加一個(gè)標(biāo)識(shí)變量，例如用一個(gè)變量表示隊(duì)列中元素的個(gè)數(shù)來(lái)區(qū)分是滿(mǎn)隊(duì)列還是空隊(duì)列；方案二是留出一個(gè)單元位置不使用，作為元素進(jìn)隊(duì)前測(cè)試之用，即若(r+1)%maxlength==f，表明還剩最后一個(gè)單元可用，此時(shí)可以認(rèn)為隊(duì)列已滿(mǎn)（maxlength是隊(duì)列最大元素個(gè)數(shù)）。若隊(duì)列為Q[maxlength-1]，即系統(tǒng)會(huì)為循環(huán)隊(duì)列Q分配maxlength個(gè)元素的空間，但只能存儲(chǔ)maxlength-1個(gè)元素。方案二比較直觀，循環(huán)隊(duì)列的入隊(duì)算法基本采取這種方式。隊(duì)列3.2.4鏈?zhǔn)疥?duì)列的基本運(yùn)算及實(shí)現(xiàn)鏈?zhǔn)疥?duì)列是用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的隊(duì)列。一般用帶表頭結(jié)點(diǎn)的單鏈表來(lái)表示隊(duì)列，但隊(duì)列的頭指針與單鏈表的頭指針有所不同。隊(duì)列的插入和刪除在兩端，為提高插入、刪除的效率，頭指針中設(shè)置了Q.front和Q.rear兩個(gè)指針。Q.front是隊(duì)首指針，指向表頭結(jié)點(diǎn)；Q.rear是隊(duì)尾指針，指向隊(duì)尾結(jié)點(diǎn)?？贞?duì)列：Q.front和Q.rear均指向表頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)的指針域?yàn)榭?。非空?duì)列：Q.front->next指向隊(duì)首結(jié)點(diǎn)a1，Q.rear指向隊(duì)尾結(jié)點(diǎn)

。03PART應(yīng)用實(shí)例3.3.1棧的應(yīng)用實(shí)例編碼是信息傳輸中一種常見(jiàn)的操作。現(xiàn)有一種簡(jiǎn)易的編碼規(guī)則為“k[encoded_string]”，它表示其中方括號(hào)內(nèi)部的encoded_string正好重復(fù)k次。encoded_string中的基本字符為小寫(xiě)英文字母；數(shù)字k（k必須為正整數(shù)）表示對(duì)應(yīng)字符串重復(fù)出現(xiàn)的次數(shù)。利用該編碼規(guī)則，可以求返回解碼后的字符串。例如，字符串2[ab]3[c]def，表示ab出現(xiàn)2次、c出現(xiàn)3次、def出現(xiàn)1次，解碼后返回的字符串為ababcccdef。另外，這種編碼允許嵌套的表達(dá)形式，解碼的過(guò)程需要由里向外、從左到右進(jìn)行解碼。例

如，字符串3[a2[bc]]2[d]，先對(duì)里層的2[bc]進(jìn)行解碼得到3[abcbc]2[d]，再對(duì)3[abcbc]解碼得到abcbcabcbcabcbc2[d]，最后解碼得到的字符串為abcbcabcbcabcbcdd。應(yīng)用實(shí)例3.3.1棧的應(yīng)用實(shí)例通過(guò)分析上述解碼過(guò)程可知，我們可以借助棧來(lái)實(shí)現(xiàn)嵌套編碼的解碼。其算法思想如下。（1）初始化兩個(gè)棧，分別為記錄重復(fù)次數(shù)的數(shù)字棧s1和記錄字符串的字符串棧s2（2）掃描待解碼的字符串。①若當(dāng)前字符為數(shù)字，解析出完整的數(shù)字并入棧s1②若當(dāng)前字符為字母或左中括號(hào)，入棧s2③若當(dāng)前字符為