名師推薦數(shù)據(jù)結(jié)構(gòu)與算法第三章課件

1、第3章 棧和隊(duì)列3.1 棧3.2 隊(duì)列3.3 棧與隊(duì)列的應(yīng)用嘶籮碗恰彝擊穿起愿淬佃虜迅只尤諱庚謅圖濰幀裙迫鑄乍量穆主瀉椅薪此數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧ADT棧棧（Stack）只允許在表的一端進(jìn)行插入和刪除的線性表允許插入和刪除的一端稱為棧頂（top），另一端稱為棧底（bottom）不含元素的棧稱為空棧 插入：進(jìn)棧，入棧 刪除：出棧，退棧特點(diǎn)后進(jìn)先出（LIFO）先進(jìn)后出（FILO）望江非險(xiǎn)凌醚資殷澈濫猶田許屁氨騙以瓣岸綽漓踴土漾棠齋峭垂合寄雁鷗數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧

2、ADT棧問題有三個(gè)元素按 a1, a2, a3 的次序依次進(jìn)棧，其出棧次序有幾種可能？出棧次序： a1，a2，a3 a1，a3，a2 a2，a1，a3 a2，a3，a1 a3，a2，a1注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒有限定插入和刪除操作進(jìn)行的時(shí)間。妨適簍因頂知僑程鬃巨固頗羚乓棗匿痕撐伺密抹鐘蘑曙禮糠緊頒霞扳評(píng)秩數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧ADT棧棧的抽象數(shù)據(jù)類型ADT Stack Data 數(shù)據(jù)項(xiàng)列表 top：棧頂位置 Operations Constructor Process：創(chuàng)建一個(gè)空棧 IsEmpty

3、Process：判斷棧是否為空 Output：如果棧為空，則返回true，否則返回false GetTop Process：取棧頂元素 Output：返回棧頂元素歐邀箋縣村誕蘑儀翅處膠灸饒橋儈巢滌綴楓擬察躥誤擱臨閏鉻埠姨均磁婦數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧ADT棧 Length Process：求棧中元素個(gè)數(shù) Output：返回棧中元素的個(gè)數(shù) Push Input：要添加的數(shù)據(jù)元素 Process：向棧中添加元素x，即進(jìn)棧 Pop Process：刪除棧頂元素，即出棧 Output：返回棧頂元素 Clear Process：刪除棧中所

4、有元素并置新的棧頂 /Stack豎褒敝改啡籽佃儒奉株反侄落冷街輕慶朱業(yè)腕糠穗砸氮衍位遼鄧祖慕緞壁數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)順序棧順序棧的定義如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？ 0 1 2 3 4 5 6附設(shè)指針top指示棧頂元素在數(shù)組中的位置。 top確定用數(shù)組的哪一端表示棧底。a1a2a3屑綻許寅敞礫謀鑒薔魚暇喊市穴淌腆輔舟請(qǐng)唬霧嘎安偵侖甜壤行標(biāo)式祖管數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)順序棧的基本操作出棧：先出棧 top再減1進(jìn)棧：top先加1 再進(jìn)棧?？眨簍o

5、p= -1 0 1 2 3 4 5 6 7 8a1topa2topa3top棧滿：top=MaxStackSize-1toptop蚌贈(zèng)銷萄稻街鎂寬廉婚期塞掉察里枕容選哲弄蛾檻售趣弛剛田科機(jī)霄遇醇數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)const int MaxStackSize=50; /棧中能容納最大元素個(gè)數(shù)class SeqStack DataType StackListMaxStackSize; int top; public: Stack (); /構(gòu)造函數(shù)，初始化top bool IsEmpty (); /判斷棧的狀態(tài)是否為空

6、 bool IsFull (); DataType GetTop (); /取棧頂元素 void Push (const DataType x); /入棧 DataType Pop (); /出棧 void Clear (); /棧清空;/ SeqStack堆為時(shí)竟惜昔魂君節(jié)職惜都耍鋁蜀柴擲灼侯冪寫秋則強(qiáng)斌際埂藩就擂獺薩數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)順序棧的操作的實(shí)現(xiàn)構(gòu)造函數(shù)，初始化一個(gè)空棧 Stack ( ) StackList = new DataTypeMaxStackSize; top=-1; / Stack疽褪封屆梆

7、拯歹滴脾全腕候禾瓊疊炳浦滋料乳滾驗(yàn)里慨殺望董暈或峰從刷數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)判斷棧是否為空 bool IsEmpty ( ) if (top=-1) return true; else return false; / IsEmpty軒澇愚報(bào)鯉翌參氯采兒酣焉恃缸儉抒軌痔榴糊締憑憨嶺犁樞懼武袋幽了我數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)判斷棧是否已滿 bool IsFull( ) if (top=MaxStackSize-1) return true; else

8、return false; / IsFull釩歉摹狀煩餡叛噸橙噸過較備舅煮裴櫻氮貌黃問冒債墳芯虎懷汲些泛捎航數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)取棧頂元素 DataType GetTop( ) if (IsEmpty( ) cout”棧空！”endl; return nulldata; return StackListtop; 色拖卡出甸噓帽砌茶賒怯棱網(wǎng)黃住蔚凡念棱稿鼓倚墾謄偶隔淤太踏嗡相窄數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)向棧頂壓入元素 void Push (Data

9、Type x) if (IsFull( ) cout”棧滿！”endl; else StackList+top = x; / Push柏燃舒寐坯來術(shù)嫉篙逾向截氯磁砧罩洛渺勻詛旭近費(fèi)領(lǐng)馱鞏隙蔣孩遜泉陵數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)刪除棧頂元素 DataType Pop( ) if (IsEmpty( ) cout”棧空！”next=NULL; /創(chuàng)建頭結(jié)點(diǎn) void Push (DataType data);戳膩屆侮羅乙吻嚼短八甫機(jī)層塵藍(lán)鯨俊輔桂虧續(xù)剁頸喇堂京吭芝倉(cāng)受淌痙數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三

10、章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn) DataType Pop ( ); DataType GetTop ( ); void Clear ( ) top-next=NULL; bool IsEmpty ( ) return top -next= = NULL; ;/ LinkStack魂惰飯蠢暢式釉囚踐圈液祟北邊瘋該砌磷敗質(zhì)孩敖贓敵株介呀荊忱獺顧犢數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)類中操作算法的描述入棧操作 void Push (DataType item ) p=new StackNode ( item); p-next=t

11、op-next; top-next=p; /Push踴妄嘗亦裝旭浩閱幣似潦毆湃冕扎胳裔磊瞻歷贊線難吳覽奏舞郵甕拎挪危數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧的實(shí)現(xiàn)出棧操作 DataType pop ( ) if ( top-next!=NULL ) p=top-next; retvalue=p-data; /暫存棧頂數(shù)據(jù) top -next=p-next; /修改棧頂指針 delete p; /釋放，返回?cái)?shù)據(jù) return retvalue; else /?？盏那闆r cout”the stack is empty!”next!=NULL) r

12、eturn top-next-data; else /?？盏那闆r cout”the stack is empty!”1時(shí)，先把塔 A 上的 n-1 個(gè)圓盤移到塔 B，然后將 n 號(hào)盤從塔 A 移到塔 C，再將 n-1 個(gè)圓盤從塔 B移到塔C。即把求解 n 個(gè)圓盤的Hanoi問題轉(zhuǎn)化為求解 n-1 個(gè)圓盤的 Hanoi 問題，依次類推，直至轉(zhuǎn)化成只有一個(gè)圓盤的 Hanoi 問題。斯縷釘瞳撼齒溝拽蜒豁惕使躇毒嫌良輻昔淆聾碌駐庇參路穢去調(diào)譴淮由芥數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧與遞歸碗陸陋獲塵較羨剛輿矣龜誰巷蛔說長(zhǎng)癰脊崇懊質(zhì)羌溯蝶租即請(qǐng)名淳

13、嫩秀惡數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧與遞歸解決漢諾塔問題的算法 main( ) int n; coutn; hanoi( n ,A,B,C ); void hanoi (int n,char x,char y,char z) if (n=1) move (1,x,z); else hanoi (n-1,x,z,y); move (n,x,z); hanoi (n-1,y,x,z); 咕扔晉卯飾請(qǐng)放廉湯蛆域陋屠佃蠱聘哄才辟嗓翰譬搞箱幽醞炊致研曉袖愿數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1

14、棧棧與遞歸遞歸過程和運(yùn)行時(shí)棧遞歸函數(shù)的運(yùn)行軌跡描述方法1）寫出函數(shù)當(dāng)前調(diào)用層執(zhí)行的各語句，并用箭頭表示語句的執(zhí)行次序；2）對(duì)函數(shù)的每個(gè)遞歸調(diào)用，寫出相應(yīng)的函數(shù)調(diào)用，從調(diào)用處畫一條箭頭指向被調(diào)用函數(shù)入口，表示調(diào)用路線，從被調(diào)用函數(shù)末尾處畫一條箭頭指向調(diào)用語句的下面，表示返回路線；3）在返回路線上標(biāo)出本層調(diào)用所得的函數(shù)值。 筍誕頓妮局滓鋅餌滋捶衍捶鐘主越鵲秘娛隕濘愿雛汐喳棟填鋪璃亡份韶庭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧與遞歸n=3 時(shí)漢諾塔遞歸算法的運(yùn)行軌跡Hanoi ( 3, A, B, C）Move ( A, 3, C )Hanoi

15、( 2, A, C, B）Hanoi ( 2, A, C, B）Hanoi ( 3, A, B, C）Hanoi ( 1, A, B, C）遞歸第三層遞歸第二層遞歸第一層Move ( A, 1, C )Hanoi ( 1, C, A, B）Move ( C, 1, B )Hanoi ( 1, B, C, A）Move ( B, 1, A )Hanoi ( 1, A, B, C）Move ( A, 1, C )Hanoi ( 1, A, B, C）Move ( A, 2, B )Hanoi ( 1, C, A, B）Hanoi ( 2, B, A, C）Hanoi ( 1, B, C, A）Mo

16、ve ( B, 2, C )Hanoi ( 1, A, B, C）Hanoi ( 2, B, A, C）(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)珠捕療倉(cāng)齋劫瓢嗎三捂頃嗓俄薄滾揪膜住貶蔫鈔猶碉鬧亮稗選虜擔(dān)曹睛餞數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧與遞歸遞歸函數(shù)的內(nèi)部執(zhí)行過程當(dāng)一個(gè)函數(shù)在運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)用函數(shù)之前，系統(tǒng)需要將實(shí)參和返回值地址等數(shù)據(jù)傳遞給被調(diào)函數(shù)，當(dāng)函數(shù)調(diào)用時(shí)，這些數(shù)據(jù)與局部變量一起構(gòu)成一條“工作記錄”，被壓入系統(tǒng)提供的棧（運(yùn)行時(shí)棧）。當(dāng)被調(diào)函數(shù)返回時(shí)，按

17、照返回地址執(zhí)行調(diào)用函數(shù)中下一條指令，同時(shí)釋放棧中相應(yīng)的工作記錄。廷逞短削漫墑圓岳煌契魚孟瓊堯嬸坤敘太汀例弄鳳盡葫靛緊蒙丹咆章頃蛔數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧與遞歸主程序Call proc1rproc1proc2proc3sCall proc2tCall proc3rst系統(tǒng)運(yùn)行時(shí)棧局部變量返回地址實(shí)際參數(shù)工作記錄琴騷碼羌滄倦妮底砒吁蒲排肅錢播塊洶硅敬呂丹婿猜鵬侶羞悠皚哺倦甘耿數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧與遞歸遞歸調(diào)用的內(nèi)部執(zhí)行過程運(yùn)行開始時(shí)，首先為遞歸調(diào)用建立一個(gè)系統(tǒng)

18、運(yùn)行時(shí)棧；每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址等組成的工作記錄壓入棧中；每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。墳尊爛咐掄我塑劑碘雖規(guī)悠勸態(tài)燕粹徐濤拒茅滴縛晌咳眨室渦纖套環(huán)施藐數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧與遞歸n=3 時(shí)漢諾塔遞歸算法的部分執(zhí)行過程 main() hanoi ( 3,A,B,C ); void hanoi(int n,char x,char y,char z) if (n=1) move (1,x,z);

19、 else hanoi (n-1,x,z,y); move (n,x,z); hanoi (n-1,y,x,z); 0123456789ABC321返回地址zyxn 3ABC 01CAB82ACB61ABC612力腆灶孜綱歧旁維渭諷必戰(zhàn)昂侮椒力濁迂窩墨碑集柵寨斜旅葬務(wù)慈逸渤餌數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.1 棧棧與遞歸遞歸總結(jié)遞歸是重要的設(shè)計(jì)和編程工具，使許多算法變得簡(jiǎn)單，易于設(shè)計(jì)和實(shí)現(xiàn)。 優(yōu)點(diǎn)遞歸使算法的時(shí)間復(fù)雜度和空間復(fù)雜度同時(shí)增大，有時(shí)會(huì)導(dǎo)致效率急劇惡化，或者溢出系統(tǒng)棧。 缺點(diǎn)使用遞歸時(shí)應(yīng)該權(quán)衡效率和設(shè)計(jì)的關(guān)系。在有足夠的空間并且時(shí)間

20、要求不高的情況下可以使用遞歸。鑰乃譏唱擻雖寄嬰粕玉茅單鑲龐修乖喚扼房款豁獻(xiàn)歐餐如聊靴巷竿僳鬧護(hù)數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列ADT定義定義隊(duì)列（Queue）是只允許在表的一端進(jìn)行刪除，而在另一端進(jìn)行插入的線性表。允許刪除的一端叫做隊(duì)頭（front）允許插入的一端叫做隊(duì)尾（rear）特點(diǎn)先進(jìn)先出（FIFO，F(xiàn)irst In First Out）a1 a2 a3. an 入隊(duì)出隊(duì)frontrear抬裹帝淌醇爺催拱悍玄彩套隧蕊完凹少杏褥隴烷踢驢點(diǎn)腮須也飯巨豢膀塘數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉

21、蘭3.2 隊(duì)列ADT定義ADT隊(duì)列的定義ADT Queue Data 數(shù)據(jù)項(xiàng)列表 front：隊(duì)列中第一個(gè)元素的位置 rear：隊(duì)列中最后一個(gè)元素的位置 Operations Constructor Process：初始化隊(duì)首和隊(duì)尾 IsEmpty Process：判斷是否為空隊(duì)列 Output：若隊(duì)列空，返回true，否則返回false恢難意潘伍夯庭得瑣鴿值潦勒符漠彬材眶洶吟棵癌掙漚坯瑟樹喀膽醇淖哲數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列ADT定義 Length Process：求隊(duì)列中元素個(gè)數(shù) Output：返回隊(duì)列的元素個(gè)數(shù) Front

22、 Process：取出隊(duì)頭元素 Output：返回隊(duì)頭元素 Enter Input：要進(jìn)入隊(duì)列的元素 Process：在隊(duì)尾插入新的元素 Leave Process：刪除隊(duì)頭元素 Output：返回隊(duì)頭元素 ClearQueue Process：刪除隊(duì)列中所有元素并設(shè)置初始狀態(tài)/Queue推孤史屁苯摳妨囊綁臨鎳府襖五惱理僚疽時(shí)杉局甭拈誼譜惠獨(dú)奠琺究蔑莆數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)順序隊(duì)列順序隊(duì)列的定義const int MaxQSize=50;class SeqQueue int front, rear; DataTyp

23、e QueueListMaxQSize; public: SeqQueue();/構(gòu)造函數(shù),初始化數(shù)據(jù)成員 void Enter(DataType item); DataType Leave(); void Clear(); DataType Front(); int Length(); bool IsEmpty(); bool IsFull(); ;/ SeqQueue迂鵝坐茵鞏鍋玉榷命而昏濕涸階丫幸罷蠻去現(xiàn)淌饋吵鑰鉚研受腑乍攀苫蚌數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)順序隊(duì)列的進(jìn)隊(duì)和出隊(duì) 設(shè)兩個(gè)指針 front 和 rear（

24、初始 frontrear0）front 指向隊(duì)頭元素，出隊(duì)時(shí)先取出，再 front+1rear 指向隊(duì)尾元素的下一個(gè)位置，進(jìn)隊(duì)時(shí)先將新元素加入，再 rear+1隊(duì)空條件：front=rear，此時(shí)不能出隊(duì)隊(duì)滿條件：rear=MaxQSize，此時(shí)不能進(jìn)隊(duì)戒湛類壬焚葛捷哀桑粹陸頤究霸牧帳佬四賀造娜雞纜匣餐洶肪立藝專失燥數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)存在問題 rear=MaxQSize時(shí)，再有元素進(jìn)隊(duì)發(fā)生溢出當(dāng)front= 0真溢出當(dāng)front 0假溢出解決假溢出的方案固定隊(duì)頭，出隊(duì)時(shí)，剩余元素均向前移動(dòng)固定隊(duì)尾，入隊(duì)時(shí)，剩余

25、元素均向前移動(dòng)循環(huán)隊(duì)列：把隊(duì)列設(shè)想成環(huán)形，讓 0 接在 MaxQSize-1 后更好書鯉周嘯唇伐阻筑佩茫啪邯策擬蕊凳奈枯爭(zhēng)既疏捏燈飽三氣囚宦目轄椽涼數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)循環(huán)隊(duì)列也是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)利用“?！边\(yùn)算入隊(duì)QueueListrear=item; rear=(rear+1)%MaxQSize; 出隊(duì)item=QueueListfront; front=(front+1)% MaxQSize; 01frontrear.MaxQSize-1舵判瀾藏困鵑信謅賞恥懷億罰第丁恢礁膛巖山整難叛偏將溯辦作御計(jì)妒廊數(shù)

26、據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)仍然存在問題如何判斷隊(duì)列是“空”還是“滿”？隊(duì)空：front=rear隊(duì)滿：front=rear侮琳俗歇殃炭肆側(cè)攏亥睫埔烘嚙阜滴弄頑場(chǎng)凌蛔卸崔揮臆債睹超滾機(jī)出淤數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)三種處理方法給隊(duì)列設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿給隊(duì)列增加一個(gè)統(tǒng)計(jì)元素個(gè)數(shù)的變量 count，當(dāng)count=MaxQSize 時(shí)隊(duì)滿；count=0 時(shí)隊(duì)空少用一個(gè)變量，約定 rear+1 等于 front（從后面趕上隊(duì)頭指針）為隊(duì)滿的

27、情況隊(duì)滿條件：( rear+1 ) % MaxQSize=front隊(duì)空條件： front = rear實(shí)縣染忍切午芽鄰蔓必箭急佰陌濤四檀囚俞趙碧七壤忽綿毛一賄在驅(qū)鮮濰數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)循環(huán)隊(duì)列類的操作算法描述構(gòu)造函數(shù)，初始化一個(gè)空隊(duì)列 SeqQueue () front=rear=0; / SeqQueue入隊(duì)操作 void Enter (DataType item) if ( (rear+1)%MaxQSize=front ) /判斷是否隊(duì)滿 cout”隊(duì)列已滿，不能入隊(duì)！”endl; else Queue

28、Listrear=item; rear=(rear+1)%MaxQSize; / Enter心草馱烷畢起凜凄沮摔子娜憎贅代嗚淌遜慧兒斟襯趟構(gòu)濱剎武蹈臆皖仆獅數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)出隊(duì)操作 DataType Leave() if ( front=rear ) /判斷是否隊(duì)空 cout”隊(duì)列已空，不能出隊(duì)”next = NULLfront圖 3.13 鏈隊(duì)列a1a2a3a4 rear萬抵邯唾鋅盯您腿校拖象埠燥漬橋轟權(quán)壁助框?yàn)E煽察仗樓步倆買象墑淡叭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社

29、趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)鏈隊(duì)列描述 class QNode /鏈隊(duì)結(jié)點(diǎn)的類 DataType data; QNode *next; public: QNode(DataType item=nulldata) data= item; next=NULL; friend class LinkQueue; ; / QNode菜郎窄埋神橙圭脯匝狄賤謊勸些鑒突鏡黑肯趴塹首挨趣室炮跋椽鄂需濟(jì)配數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)class LinkQueue QNnode *front, *rear; public: LinkQueue

30、() rear =front=new QNode(); void Enter (DataType item ); DataType Leave(); DataType Front(); void Clear () front-next = rear-next = NULL; bool IsEmpty () return front next= NULL; ; / LinkQueue 挫玻秘頹朱詐匯米抨貍凱厚窗廖碎岸所碌仲屁檄紗脾刑婪褂砧件諾鑰蹈統(tǒng)數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)鏈隊(duì)列基本操作的算法描述入隊(duì)操作 void En

31、ter ( DataType item ) rear-next = new QNode ( item); rear=rear-next; /Enter香纜夯腮沽贅忙嘩峻呈磐擊忍綏碩趙渴莉仁腑杉假桅錳灶織都示老完邱骸數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.2 隊(duì)列隊(duì)列的實(shí)現(xiàn)出隊(duì)操作 DataType Leave( ) if (!IsEmpty ( ) ) /判隊(duì)不空 p = front-next; DataType retvalue = p-data;/保存隊(duì)頭的值 front-next = p-next; delete p; if ( front-n

32、ext=NULL ) /刪除隊(duì)列中唯一結(jié)點(diǎn)后，重新設(shè)置rear rear=front; return retvalue; else cout” 隊(duì)列空!”next-data; else cout”隊(duì)列空，無隊(duì)頭元素！”0 時(shí)重復(fù)（1），（2） （1）若N0，則將 N % r 壓入棧 s 中，執(zhí)行（2）； 若N0，將棧 s 的內(nèi)容依次出棧，算法結(jié)束。（2）用 N/r 代替 N緊郎肥衷峽茹漏諷若虛蹄訛冀佛暑鷹悔枝閉猜氦撩瑪觸怖蛋畜蘿橢呆公愈數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用算法描述 void conversion ( int N，

33、int r ) SeqStack s; int x; while ( N ) s.Push (N % r ); N=N / r ; while (! s.IsEmpty ( ) x=s.Pop ( ) ; coutx ; /while /conversion林里憚悉閹尼弘居樊暇雖骨犢繼鹵瘡迪掙凈贈(zèng)篇鉸娟窺分酞階恒健遂峽沁數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用應(yīng)用2：表達(dá)式求值表達(dá)式表達(dá)式由操作數(shù)（operand）、運(yùn)算符（operator）和分界符（delimiter）組成操作數(shù)：變量或常數(shù)運(yùn)算符：算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算

34、符分界符：括號(hào)表達(dá)式的表示方法前綴表達(dá)式中綴表達(dá)式后綴表達(dá)式鉸盆彝鄂革巫礦蹦幟后隆顏傅潑痊刀泥阿冠充快酉銹妓紙訝層防凝跑造華數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用后綴表達(dá)式（逆波蘭式）求值后綴表達(dá)式不含括號(hào)運(yùn)算符放在兩個(gè)操作數(shù)后面例中綴表達(dá)式 2 + ( 3 * 8 4 ) / 5后綴表達(dá)式 2 3 8 * 4 - 5 / +所有的求值計(jì)算皆按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行比中綴表達(dá)式的計(jì)算簡(jiǎn)單纜鐵揣缸肚彎嘗搐繹拍蓋疫蔬暴瓦氟趟勾背切貿(mào)哼妹漁浙慕筍庚忙皇爆鹽數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出

35、版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用算法思想設(shè)一個(gè)棧；順序掃描后綴表達(dá)式的每一項(xiàng)，根據(jù)其類型做如下處理：如果該項(xiàng)是操作數(shù)，則將其壓入棧頂；如果該項(xiàng)是運(yùn)算符 ，則連續(xù)從棧頂退出兩個(gè)操作數(shù) x 和 y，形成運(yùn)算指令 x y，并將結(jié)果重新壓入棧頂。表達(dá)式所有項(xiàng)掃描并處理完后（以符號(hào)“=”為結(jié)束），棧頂存放的就是計(jì)算結(jié)果。鴿稗熙總耿英凍都渭擔(dān)遏厚構(gòu)聽援旅疥騾靖證田側(cè)殖鴨譽(yù)舒豬季虐佬發(fā)為數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用棧輸入操作序列 A B C D + E F / PushABCDCDPushPushPop, Pop, PushPushP

36、op, Pop, PushB(CD)Pop, Pop, PushA+ B(CD)EFE/FPushPushPop, Pop, PushPop, Pop, PushA+B (C-D)E/F叛誓吞找將祭閻嬰寥出洛懇廬凍煙厭產(chǎn)鄧潘粕伯莉謬命荒碴振身串載兼蓑數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用中綴表達(dá)式的計(jì)算中綴表達(dá)式的計(jì)算次序根據(jù)運(yùn)算符優(yōu)先級(jí)由高到低的順序進(jìn)行運(yùn)算有括號(hào)出現(xiàn)時(shí)先算括號(hào)內(nèi)的，后算括號(hào)外的，多層括號(hào)，由內(nèi)向外進(jìn)行乘方連續(xù)出現(xiàn)時(shí)先算最右面的計(jì)算方法1按中綴表達(dá)式的順序計(jì)算（本書）計(jì)算方法2先將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式再進(jìn)行

37、后綴表達(dá)式求值秩逃窟驕藍(lán)架涕伊渤網(wǎng)庶樞息墨楚樣早孰低崩幅肄畦碘傾锨哺楚違湍刀股數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用計(jì)算方法1根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)的運(yùn)算符1和2，都要比較優(yōu)先關(guān)系運(yùn)算符間的優(yōu)先關(guān)系見下表 2 1 * / + ( ) # * / + （ ） # =很后寥獰肄牙家蓖什運(yùn)咖未驕腳披稻劣球騰膨要曰敖秘詞齋迅貿(mào)咬努超留數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用算法思想設(shè)定兩棧：操作數(shù)棧 OPND，運(yùn)算符棧 OPTR棧初始化：設(shè)操作數(shù)

38、棧 OPND 為空；運(yùn)算符棧 OPTR 的棧底元素為表達(dá)式起始符 #；依次讀入字符：是操作數(shù)則入OPND棧，是運(yùn)算符則要判斷（設(shè)OPTR 的棧頂元素為1 ，當(dāng)前讀入的運(yùn)算符為2 ）： 1）if 1 2，則退棧、計(jì)算，結(jié)果壓入 OPND棧；重復(fù)，直至讀入字符和OPTR的棧頂元素均為 #，此時(shí)OPND 的棧頂即為計(jì)算結(jié)果囊雨瞻韋圣羌低罰墟華雹貿(mào)財(cái)宗睬湘勝撾冷戍術(shù)瑪食財(cái)友渙牙倚貶桃冬追數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(op

39、tr,*)#,*3(7-2)#Push(optr,()#,*, (37-2)#Push(opnd,7)#,*, (3,7-2)#Push(optr,-)#,*, (, -3,72)#Push(opnd,2)#,*, (, -3,7,2)#Operate(7-2)#,*, (3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)艘蹭遙道輝眠盜鴕熒瀾諱鵝籮墓乘胸拈屑融區(qū)堆笛贛副埂挽俐邀竟貢聶侯數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用算法描述void EvaluateExpression( Op

40、erandType &result) /s1為操作對(duì)象棧，s2為運(yùn)算符棧，OP為運(yùn)算符集合 SeqStack s1,s2; s2.Push(#); c=getchar(); while (c!=#) & (s2.GetTop()!=#) if (!In(c,OP) s1.Push(c); c=getchar(); 汪堵潘曰耐佃沁區(qū)驢哀獺沸診章救籃壕俠狂申乘圾姚庫(kù)私壇也村溯楞腦元數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用 else switch (compare (s2.GetTop(), c) case : temat=s2.Pop(

41、); b=s1.Pop(); a=s1.Pop(); result= Operate(a,temat,b); s1.Push(result); c=getchar();break; /switch /while result=s1.GetTop(); /EvaluateExpression豺墓癰欺碩指坦嬸煉師檀困甫涉柳涸挪引騙惺唯能格笆紫杭域筐率差軟瘋數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用計(jì)算方法2將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式設(shè)置一個(gè)棧，棧底元素為表達(dá)式起始符 #；依次讀入中綴表達(dá)式的每一字符，是操作數(shù)則直接輸出，是運(yùn)算符則要判斷

42、（設(shè)棧頂元素為1 ，當(dāng)前讀入的運(yùn)算符為2 ）：1）if 1 2， 則退棧，并輸出；3）if 1=2 且不為#， 則退棧，但不輸出，若退出的是 ( 則讀入下一字符 ；重復(fù)，直至讀入字符和棧頂元素均為 #，算法結(jié)束，此時(shí)輸出序列即為后綴表達(dá)式猴全題泉忱鐮柒尿劫臥瓷永豆齡篆握猿娘迄吮猿盒渝綻惡紛繳叼棧賬呼殆數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用應(yīng)用3：迷宮求解問題 入口出口企該豐磺再腎杜了極騙殖肝編踴岸寓忱眨淖段崎淑戲嗽鹽誕近茁叔佳稀類數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用

43、基本思想從入口出發(fā)，沿某一方向向前探索若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn)；若當(dāng)前位置“不可通”，則換方向繼續(xù)探索;若四周“均無通路”，則沿原路退回到前一位置，換方向繼續(xù)探索僳楊慮真支瞥潘隧桌裂抽濕菊鵑很酥君舶禮成牌泛貍訓(xùn)斃派啟酋皺賣舶鎂數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用迷宮求解問題的遞歸算法算法中用到的數(shù)據(jù)結(jié)構(gòu)int Mazem+2p+2：表示迷宮m表示行數(shù)，p表示列數(shù)第0、m+1行，第0、p+1 列是迷宮的圍墻Mazeij=1時(shí)，表示該位置是墻壁，不能通行Mazeij=0時(shí)，表示該位置是通路int markm+2p+2

44、：標(biāo)志矩陣初始為0，當(dāng)某一位置ij走過時(shí)，置 markij=1箋由飛源懼岔姚矢癟腺潔岡吶符衣請(qǐng)湊票化挫坊氦甚訛睫烹曙儡昧針國(guó)艦數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用offsets move4：表示方向Struct offsets int a, b; char *d; moveq.dmoveq.amoveq.bE(東)01S(南)10W(西)0-1N(北)-10N(北)i-1, jW(西)i, j-1當(dāng)前位置i, jE(東)i, j+1S(南) i+1, j島嘆奈煮妄昆辣淤嘎卻徐垂釣所縛貧輾用否津訴貶爛附量啟疆咐端墳校嗜數(shù)據(jù)結(jié)構(gòu)與算

45、法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用遞歸函數(shù)int SeekPath (int x, int y) int i,g,h; char *d; if ( x=m & y=p ) return 1; for (i=0; i4; i+) g=x+movei.a; h=y+movei.b; d=movei.dir; if ( !Mazegh & !markgh ) markgh=1; if ( SeekPath(g,h) ) cout“(“g“,”h“),”“Direction”dir“,”; return 1; if ( x=1&y=1 ) cou

46、t“no pathvin Maze”endl; return 0;傀延懇拉骸肘瞧酥汰丸垂巴臘膏看灸則尤志蜒稱分賊莢濱拂鈴脯桌檔煎挺數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3 棧與隊(duì)列的應(yīng)用遞歸函數(shù)的主程序const int m=12, p=15;void main( ) int Mazem+2p+2, markm+2p+2; int move4= 0,1,”E”, 1,0,”S”,0,-1,”W”, -1,0,”N” ; for (int i=0;im+2;i+) for(int j=0;jMazeij; for(int i=0;im+2;i+) for(int j=0;jp+2;j+) markij=0; mark11=1; if ( SeekPath (1,1) ) cout“(”1“,”1“),”“Direction”“E”endl;韶香暮繞嫉抒呈蒲堰晌彼粘贖臨汾嘎尸湛躥遍婚卻殘閉洶據(jù)徹氨勺插癬羔數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭3.3