西電軟件技術(shù)基礎(chǔ)課件5,6棧和隊(duì)列.

1、軟件技術(shù)基礎(chǔ)（三）棧和隊(duì)列西安電子科技大學(xué) 電子工程學(xué)院 林杰本部分的內(nèi)容九基本要求（1）了解棧和隊(duì)列是操作受限的線性表的概念； 掌握順序棧、鏈棧.順序隊(duì)列.鏈隊(duì)列的類型定義 和基本運(yùn)算的實(shí)現(xiàn)算法;掌握循環(huán)隊(duì)列的概念和滿 隊(duì)、空隊(duì)的條件。（2）掌握利用基本運(yùn)算編寫實(shí)現(xiàn)棧和循環(huán)隊(duì)列應(yīng) 用的算法。2重點(diǎn).難點(diǎn)-重點(diǎn)：棧和隊(duì)列的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu).基本運(yùn)算 的實(shí)現(xiàn)，棧和隊(duì)列的應(yīng)用算法。難點(diǎn)：棧和循環(huán)隊(duì)列應(yīng)用的算法。生活中的棧舉例九：家里吃飯的碗，通常 在洗干凈后一個(gè)一個(gè)地落在 一起存菽，在茯用亦，若一 個(gè)一個(gè)地拿，一定最先拿走 最上面的那只碗，而最后拿 出最下面的那只碗。舉例2：在建筑工地上，使用

2、的磚塊從底往上一層一層地 碼放，在使用時(shí)，將從最上棧的基本概念仃棧(Stack):是限制在表的一端進(jìn)行插入和刪 除操作的線性表。又稱為后進(jìn)先出LIFO (Last In First Out)或先進(jìn)后出FILO (First In Last Out)線性表。- 棧頂(Top):允許進(jìn)行插入、刪除操作的一端，又 稱為表尾。用棧頂指針(Top)來指示棧頂元素。棧底(Bottom):是固定端，又稱為表頭?？諚＃寒?dāng)表中沒有元素時(shí)稱為空棧。面一層一層地拿取。棧的基本概念設(shè)棧S=( (s, a2, .an),則稱為棧底元素，an為棧頂元素，如右圖所o元素是以7召的順序進(jìn)棧，出棧的次序卻是3門戶門皿用1。 棧

3、的修改原則：“后進(jìn)先出腐O棧的基本概念?！吧弦纭?在棧滿時(shí)還進(jìn)行進(jìn)棧運(yùn)算， 必定會(huì)產(chǎn)生空間的溢出棧“下溢”:當(dāng)?？諘r(shí)仍進(jìn)行出棧運(yùn)算， 必定會(huì)產(chǎn)生空間的溢出。上溢是一種出錯(cuò)狀態(tài)，應(yīng)該設(shè)法避免之； 下溢則可能是正?，F(xiàn)象， 因?yàn)闂Ｔ诔绦蛑?使用時(shí)， 其初態(tài)或終態(tài)都是空棧，所以下 溢常常用來作為程序控制轉(zhuǎn)移的條件。出(退)棧(pop)進(jìn)(入)棧(push)- 順序棧示意圖棧底 Bottom8棧的常用基本運(yùn)算(1) InitStack(SS)棧初始化，構(gòu)造一個(gè)空棧S。(2) SetNull置空棧，將棧S清為空棧。(3) Empty(S)判斷?？?，若棧S為空，則返回 “真”值；否則返回“假”值。(4) P

4、ush(S, e)進(jìn)棧，若棧S不滿，則將數(shù)據(jù) 元素e插入棧頂。(5) Pop(Sz&e)出棧，若棧S非空，則刪除棧頂 數(shù)據(jù)元素，并返回該數(shù)據(jù)元素。(6) GetTop(S)取棧頂元素，若棧S非空，則返 回棧頂數(shù)據(jù)元素。該操作完成后，棧的內(nèi)容不變。棧的表示和實(shí)現(xiàn)棧作為特殊的線性表，有兩種基本的存儲(chǔ)結(jié) 構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：順序棧鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈棧順序棧順序棧即棧的順序存儲(chǔ)結(jié)構(gòu)，是利用一組地址連續(xù)的存 儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí) 附設(shè)指針Top指示棧頂元素在順序棧中的存儲(chǔ)位置。 空棧Top=o1O棧的順序存儲(chǔ)結(jié)構(gòu)#define maxsize 50typedef structd

5、atatype datamaxsize;用 來存放棧中元素的一維數(shù)組intTop;II用來存放棧頂元素的下標(biāo) SeqStack;1順序棧中元素用向量存放2棧底位置是固定不變的，可設(shè)置在向量?jī)啥说娜我庖粋€(gè) 端點(diǎn)3棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型 量Top（通常稱Top為棧頂指針）來指示當(dāng)前棧頂位置棧的順序存儲(chǔ)結(jié)構(gòu)定義：SeqStack*S;并規(guī)定下標(biāo)為0的向量元 素不用。S-datai是棧底元素，S-dataS-Top是棧頂元素;當(dāng)S-TopdataS-Top+=a11出棧(Pop):e=S-S-Top順序棧中的進(jìn)出棧(圖釋)66554D43C32BTop_2B1A1Aoo高地址

6、低地址棧底Bottom前提：一定要 預(yù)設(shè)棧頂指針Top讀出：e= S-dataf(a)空棧(b)A進(jìn)棧(c)BCD進(jìn)棧(d)DC出棧順序棧的基本操作4(“棧的初始化，即建立空順序棧void InitStack(SeqStack * &S)/構(gòu)造一個(gè)空棧SS=(SeqStack*) malloc(sizeof(SeqStack);S-Top = o;定義初始棧頂下標(biāo)值順序棧的基本操作（2）順序棧置空void SetNull(SeqStack *S)將順序堆棧S置為空棧S-Top = o;順序棧的基本操作（3）判棧空int Empty(SeqStack *S)判棧S為空棧時(shí)返回值為丄，反之

7、為oif (S-TopTop=maxsize-i) return 1;elsereturn o;順序棧的基本操作(5)順序棧的進(jìn)棧int Push(SeqStack *S#datatype x)若棧S不滿，則將元素x插入棧頂，并返回n,否 則返回oif (Full(S) printf(棧上溢)，return o;棧已滿else |S-Top+;S-dataS-Top=x;return 1; 1順序棧的基本操作 (6)順序棧的出棧int Pop(SeqStack *S#dataType &x)將S棧頂元素彈出，放到x所指的存儲(chǔ)空間中if (Empty(S) printf(u棧下溢),re

8、turn o; else Ix=S-dataS Top;S-Top; retur n 1;S-data+S Top=x;x=S-dataS-Top-;順序棧的基本操作（力取棧頂元素int GetTop(SeqStack *S#dataType &x)取棧頂元素if(Empty(S) printf(u棧下溢),return o;else x = dataS-Top;return 1;多棧共享技術(shù)使用順序棧時(shí)，會(huì)因?yàn)閷?duì)?？臻g的大 小難以準(zhǔn)確估計(jì)，從而產(chǎn)生有的棧溢 出，有的?？臻g空閑很多的情況。多棧的共享技術(shù)：讓多個(gè)棧共享一個(gè) 足夠大的數(shù)組空間sM,利用棧的動(dòng) 態(tài)特性來使其存儲(chǔ)空間互相補(bǔ)充。

9、22多棧共享技術(shù)兩個(gè)棧的共享技術(shù)：棧底位置不變（分別放于 數(shù)組的兩端so,SM-1）,而棧頂位置動(dòng)態(tài)變 化。只有當(dāng)兩個(gè)棧占滿整個(gè)向量空間時(shí)，即S-Topi+i=S-Top2,才會(huì)發(fā)生上溢。工號(hào)棧2號(hào)棧o1234M-4M-3M-2M-IS-TopiS-Top2兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義兩個(gè)棧共享一個(gè)向量空間的結(jié)構(gòu)類型定義如下: SeqStack;SeqStack*S=(SeqStack*)malloc(sizeof(SeqStack);typedef struct datatype vmaxsize;intTopTopz;-、假定：從o下標(biāo)開始，向量元素均被使用兩棧共享的進(jìn)棧運(yùn)算void Push(

10、SeqStack *S#datatype xzint i)將元素x插入i號(hào)棧if (S Topi+i = S-Top2) )printfC向量空間溢出“)；else if (i=i)S-v+S-Topi=x;/2v-S-Top2=x;入2號(hào)棧兩棧共享的出棧運(yùn)算datatype Pop(SeqStack*S/int i)i號(hào)棧的棧頂元素出棧 datatype x;if(i=i) if(S-Topi=-i) printf(ui號(hào)棧下溢) )；else x=S-vS-TopoJ; S-Top=-;/九號(hào)棧丄棧else if(S-Top2=M) printf(T號(hào)棧下溢”);else x=S-vS-T

11、op2; S-Top2+;2號(hào)棧出棧returnx;棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈棧鏈棧即采用鏈表作為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧。它是 運(yùn)算受限的單鏈表，其插入和刪除操作僅在表 頭進(jìn)行。與順序棧不同，鏈棧不會(huì)發(fā)生上溢。鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：data域和next域，其定義為：typedefstructstacknodef datatypedata;structstacknode ext;JStackNode;typedefstructfStackNode*Top;棧頂指針JLinkStack;LinkStack 結(jié)構(gòu)類型的定 義是為了方便在函數(shù)體中 修改Top 指針本身若要記錄棧中元素個(gè)數(shù)， 可將元素個(gè)數(shù)屬性

12、放在 LinkStack 類型中定義。丿棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈棧單鏈表實(shí)現(xiàn)棧棧頂指針就是鏈表的頭指針若Top=NULL,則代表?xiàng)？罩挥邢到y(tǒng)中有可用空間，鏈 棧就不會(huì)出現(xiàn)溢出采用鏈棧時(shí)，棧的各種基本 操作的實(shí)現(xiàn)與單鏈表的操作 類似使用完鏈棧，應(yīng)釋放其空間Topanan-ir 注意鏈中指 針的方向4棧頂元素棧底元素28鏈棧的操作：棧初始化算法4 7建立空鏈棧。void lnitStack(LinkStack*&S)構(gòu)造一個(gè)空棧SS=(LinkStack*)malloc(sizeof(LinkStack);S-Top=NULL;鏈棧的操作：置空棧算法4 8鏈棧置空。void SetNull (

13、LinkStack*S)使棧S置為空棧S-Top=NULL;30鏈棧的操作：進(jìn)棧算法4 9鏈棧進(jìn)棧。void Push(LinkStack*S/datatype e)使元素e進(jìn)棧StackNode*p;p=(StackNode*)malloc(sizeof(StackNode);p-data=e;p-next=S-Top; /將新結(jié)點(diǎn)*p插入棧頂S-Top=p;鏈棧不存在上溢的問題鏈棧的操作：出棧算法4o鏈棧進(jìn)棧。int Pop(LinkStack*S#datatype &e)若棧不空，則刪除棧頂元耒，由e帶回棧頂元素，返回1,否則返回oStackNode *p=S-Top;由指針p指

14、向棧頂元素if (Empty(S) printff1棧下溢“)；return o; else e=p-data;S-Top=p-next;/將棧頂結(jié)點(diǎn)*p從鏈上摘下free(p);/釋放原棧頂結(jié)點(diǎn)return 1; 幾點(diǎn)說明:在鏈棧中的頭結(jié)點(diǎn)對(duì)操作的實(shí)現(xiàn)影響不大， 棧頂（表頭）操作頻繁，可不設(shè)頭結(jié)點(diǎn)鏈棧。 一般不會(huì)出現(xiàn)棧滿情況；除非沒有空間導(dǎo)致malloc分配失敗。鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪 除操作，修改指針即可完成。采用鏈棧存儲(chǔ)方式的優(yōu)點(diǎn)是，可使多個(gè)棧共 享空間；當(dāng)棧中元素個(gè)數(shù)變化較大，且存在 多個(gè)棧的情況下，鏈棧是棧的首選存儲(chǔ)方式。棧的應(yīng)用舉例：數(shù)制轉(zhuǎn)換九數(shù)制轉(zhuǎn)換十進(jìn)制整數(shù)n向

15、其它進(jìn)制數(shù)d（二、八.十六）的轉(zhuǎn)轉(zhuǎn)換法則：除基數(shù)取余該轉(zhuǎn)換法則對(duì)應(yīng)于一個(gè)簡(jiǎn)單算法原理:n=（n div d）*d+n mod d其中：div為整除運(yùn)算rood為求余運(yùn)算換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問34棧的應(yīng)用舉例：數(shù)制轉(zhuǎn)換例如：（1348）10 =（25。4）8 ,其運(yùn)算過程如棧的應(yīng)用舉例：數(shù)制轉(zhuǎn)換void conversion( intn,int bas0 ) SeqStack *S; int bit;InitStack(S); scanf&n);while(n!=o)Push(Sfn%base);n=n/base;while(! Empty(S)! ；PopCS.&bit);

16、:printfC%cT7bit);I下：從計(jì)低算到順高序N1348168212Ndiv816821N mod 84052從輸問出到順低序棧 s棧的應(yīng)用舉例：括號(hào)匹配問題2括號(hào)匹配問題假設(shè)在表達(dá)式中(口 ()或( )等為正確的格式， ()或 ()或()均為不正確的格式。匹配思想：從左至右掃描一個(gè)字符串(或表達(dá)式)， 則每個(gè)右括號(hào)將與最近遇到的那個(gè)左括號(hào)相匹配。 則可以在從左至右掃描過程中把所遇到的左括號(hào) 存放到堆棧中。每當(dāng)遇到一個(gè)右括號(hào)時(shí)，就將它 與棧頂?shù)淖罄ㄌ?hào)(如果存在)相匹配，同時(shí)從棧頂 刪除該左括號(hào)。棧的應(yīng)用舉例：括號(hào)匹配問題-算法思想：設(shè)置一個(gè)棧，當(dāng)讀到左括號(hào)時(shí)，左括號(hào)進(jìn) 棧。當(dāng)讀到右括

17、號(hào)時(shí)，則從棧申彈出一個(gè)元素，與讀 到的左括號(hào)進(jìn)行匹配，若匹配成功，繼續(xù)讀入；否則 匹配失敗，返回FLASEO在檢驗(yàn)過程中，若遇到以下幾種情況之一，就可以得 出括號(hào)不匹配的結(jié)論。(1)當(dāng)遇到某一個(gè)右括號(hào)時(shí)，棧已空，說明到目前為止, 右括號(hào)多于左括號(hào)；(2)從棧中彈出的左括號(hào)與當(dāng)前檢驗(yàn)的右括號(hào)類型不同，說明出現(xiàn)了括號(hào)交叉情況；(3)算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹配的左括號(hào)，撫明左括號(hào)多于若括號(hào)。棧的應(yīng)用舉例：括號(hào)匹配問題void BracketMatch(char *str)/*str中為輸入的字符串，利用堆棧技術(shù)來檢查該字符串中的括號(hào)是否匹配勺SeqStack *S;int i; char

18、 ch;InitStack(S);for (i=i;stri !=switch(stri)case W：case V：case%f:Push(Sfstri);break;棧的應(yīng)用舉例：括號(hào)匹配問題case h：case 丁:case V：if (Empty(S)(printf(un 右括號(hào)多余！ ”)； return; else GetTop(S#&ch);if (MatchCch, stri)/*用 Match 判斷兩個(gè)括號(hào)是否匹配勺Pop(S,&ch);廣已匹配的左括號(hào)出棧勺else printf(un 對(duì)應(yīng)的左右括號(hào)不同類！ ”)； return;/*switch*/fo

19、r*/if (Empty(S)printf(un 括號(hào)匹配！ “)elseprintf(un 左括號(hào)多余！ ”)4。棧的應(yīng)用舉例：算術(shù)表達(dá)式的求值3算術(shù)表達(dá)式的求值。算術(shù)表達(dá)式格式，如：#2*（6-3）#設(shè)表達(dá)式中只有x ,/、圓括號(hào)和操作數(shù)。運(yùn)算符間的優(yōu)先級(jí)關(guān)系如下：（1）先乘除后加減；（2）先括號(hào)內(nèi)后括號(hào)外，即“（與“）優(yōu)先級(jí)相同，但 低于括號(hào)內(nèi)的運(yùn)算符，高于括號(hào)外的運(yùn)算符；（3）表達(dá)式起始、結(jié)束符“#的優(yōu)先級(jí)總是最低。為實(shí)現(xiàn)運(yùn)算符優(yōu)先算法，需設(shè)置操作數(shù)棧和運(yùn)算符棧。 操作數(shù)棧OPND存放操作數(shù)或運(yùn)算結(jié)果及中間結(jié)果；運(yùn) 算符棧OPTR存放運(yùn)算符。39棧的應(yīng)用舉例：算術(shù)表達(dá)式的求值分析：選擇

20、棧作為數(shù)據(jù)結(jié)構(gòu)，所以所有操作都要圍繞棧的特點(diǎn)來進(jìn)行。因?yàn)橄热霔６粔涸谙旅娴囊馕吨筇幚恚?優(yōu)先級(jí)低的不能壓著優(yōu)先級(jí)高的而入棧。對(duì)于同級(jí)的操作符，因?yàn)橐凑諒淖笸业倪\(yùn)算規(guī) 貝U,所以也不能壓著同級(jí)的操作符而入棧。簡(jiǎn)單來說，與棧頂?shù)牟僮鞣容^，優(yōu)先級(jí)離的則入棧，否則操作符出棧作相應(yīng)運(yùn)算。4。棧的應(yīng)用舉例：算術(shù)表達(dá)式的求值算法的基本思想是：工初始化，操作數(shù)棧置空；操作符棧壓入護(hù)。 2從左往右讀取算術(shù)表達(dá)式(從第二個(gè)字符開始)，當(dāng) 讀到#且操作符棧棧頂也是#時(shí)則算法結(jié)束。 3如果讀到的是操作數(shù)則壓入操作數(shù)棧中，轉(zhuǎn)到步驟2。4如果讀到是操作符，則比較其與操作符棧棧頂操作符 的優(yōu)先級(jí)。 5 如果

21、棧頂操作符的優(yōu)先級(jí)高，則棧頂操作符出棧，并從操作數(shù) 棧中彈出兩個(gè)操作數(shù)進(jìn)行相應(yīng)的運(yùn)算，再把運(yùn)算結(jié)果壓入操作 數(shù)棧中，轉(zhuǎn)至步驟 4。 6 如果棧頂操作符的優(yōu)先級(jí)低，則把當(dāng)前操作符壓入操作符棧， 轉(zhuǎn)至步驟 2。 7 如果棧頂操作符與當(dāng)前操作符優(yōu)先級(jí)相同，則只可能是(跟丁， 把操作符從棧中彈出即可，轉(zhuǎn)至步驟 2。棧的應(yīng)用舉例：算術(shù)表達(dá)式的求值表達(dá)式為：#2*(6-3) )#步驟OPTR棧OPND棧當(dāng)前讀入的字符操作說明1#2*(6-3)#2進(jìn)OPND棧2#2*(6-3)#“# ”低于進(jìn)OPTR棧3#*26-3)#y低于進(jìn)OPTR棧4#*(23)#6進(jìn)OPND棧5#*(26二3)#“(”低于 “進(jìn)OP

22、TR棧6263)#3進(jìn)OPND棧7#*(-263“ -”高于“)S 運(yùn)算6-3,結(jié)果進(jìn)OPND棧8#叫23歲g 于“)”，脫括號(hào)9#捲23#“水”尚于“#”，運(yùn)算2*3,結(jié)果進(jìn)OPND棧10#6#與“#”相遇，返回操作數(shù)棧頂元素6棧的應(yīng)用舉例：算術(shù)表達(dá)式的求值datatype EvaluateExpression()InitStack(OPTR); InitStack(OPND);/創(chuàng)建 OPTR 和 OPND 棧 PushQPTR/#);while (ch=getchar()!=u# |GetTop(OPTR)! #“) )if (ch!=%+#&ch!=%-z&ch!=%*

23、#&ch!=T&ch!=(z&ch!=y) )Push(OPND,ch); 不是運(yùn)算符，則進(jìn)操作數(shù)棧else switchCPrecedeCGetTopCOPTRch)!casW/棧頂元素優(yōu)先級(jí)低，當(dāng)前運(yùn)算符進(jìn)運(yùn)算符棧Push(OPTR#ch);break;case w：脫括號(hào)x=Pop(OPTR);break;case 9:/棧頂元素優(yōu)先級(jí)高，進(jìn)行運(yùn)算 op=Pop(OPTR); /運(yùn)算特棧頂元素出棧b=Pop(OPND); a=Pop(OPND);/第二、一個(gè)操作數(shù)出棧PushQPNDQperateBopQ); break; return GetTop(OPND);

24、 返回表達(dá)式結(jié)果隊(duì)列及其基本概念隊(duì)列(Queue):也是運(yùn)算受限的線性表。是一 種先進(jìn)先出(First In FirstOut ,簡(jiǎn)稱FIFO)的線 性表。只允許在表的一端進(jìn)行插入，而在另 一端進(jìn)行刪除。隊(duì)頭(front):允許進(jìn)行刪除的一端稱為隊(duì)頭。隊(duì)尾(rear):允許進(jìn)行插入的一端稱為隊(duì)尾。1/ 2/ / 巧1 r隊(duì)頭隊(duì)尾出隊(duì)入隊(duì)隊(duì)列的基本運(yùn)算(1) lnitQueue(&Q)隊(duì)列初始化，構(gòu)造一個(gè)空隊(duì) 列Q。(2) SetNull(Q)置空隊(duì)？將隊(duì)列Q清空。( (3) )Length(Q)-求隊(duì)列畏度，返回隊(duì)列中元素的個(gè)數(shù)。 ( (4) Empty(Q)判空隊(duì)，若隊(duì)列Q為空隊(duì)列，貝U返回“真值；否則返回“假”值。(5)(5)EnQueu