數(shù)據(jù)結(jié)構(gòu)第05章--棧與隊(duì)列課件

1、數(shù)據(jù)結(jié)構(gòu)（C+版）第1章 緒論第2章 線性表第3章 排序第4章 串第5章 棧與隊(duì)列第6章 數(shù)組和廣義表第7章 樹(shù)和二叉樹(shù)第8章 查找第9章 圖第10章 綜合應(yīng)用設(shè)計(jì)第5章 棧與隊(duì)列棧和隊(duì)列是兩種特殊的線性表。5.1 棧5.2 隊(duì)列5.3 遞歸數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.1 棧5.1.1 棧的定義5.1.2 棧的抽象數(shù)據(jù)類(lèi)型5.1.3 順序棧類(lèi)5.1.4 鏈?zhǔn)綏ｎ?lèi)5.1.5 棧的應(yīng)用數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.1.1 棧的定義棧（stack）是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進(jìn)行。允許操作一端稱(chēng)為棧頂（top），不允許操作的一端稱(chēng)為棧底（bottom）。棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)

2、的，標(biāo)識(shí)棧頂當(dāng)前位置的變量稱(chēng)為棧頂指針。棧中插入數(shù)據(jù)元素的過(guò)程稱(chēng)為入棧（push），刪除數(shù)據(jù)元素的過(guò)程稱(chēng)為出棧（pop）。當(dāng)棧中沒(méi)有數(shù)據(jù)元素時(shí)稱(chēng)之為空棧。圖4.1 棧結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.1.2 棧的抽象數(shù)據(jù)類(lèi)型棧的數(shù)據(jù)元素棧的基本操作棧的初始化，設(shè)置棧狀態(tài)為空。判斷棧的狀態(tài)是否為空。判斷棧的狀態(tài)是否已滿。入棧：將數(shù)據(jù)元素插入棧中作為新的棧頂數(shù)據(jù)元素的過(guò)程。在入棧之前必須判斷棧的狀態(tài)是否已滿，如果棧不滿，則接收新數(shù)據(jù)元素入棧，否則產(chǎn)生上溢錯(cuò)誤（overflow）。出棧：取出當(dāng)前棧頂數(shù)據(jù)元素，下一個(gè)數(shù)據(jù)元素成為新的棧頂數(shù)據(jù)元素的過(guò)程。在出棧之前，必須判斷棧的狀態(tài)是否為空。如果棧的狀態(tài)為

3、空，產(chǎn)生下溢錯(cuò)誤（underflow）。獲得棧頂數(shù)據(jù)元素，此時(shí)該數(shù)據(jù)元素未出棧。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.1.3 順序棧類(lèi)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.1.4 鏈?zhǔn)綏ｎ?lèi)鏈?zhǔn)綏５慕Y(jié)點(diǎn)類(lèi) template class OnelinkNode2 /單鏈表結(jié)點(diǎn)類(lèi)，模板 public: T data; /數(shù)據(jù)元素域 OnelinkNode2 *next; /指針域，指向后繼結(jié)點(diǎn)的指針 OnelinkNode2(T& k,OnelinkNode2 *nextnode=NULL) /構(gòu)造結(jié)點(diǎn) data=k; next=nextnode; OnelinkNode2() /析構(gòu)函數(shù) ;數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞2

4、. 鏈?zhǔn)綏ｎ?lèi)的設(shè)計(jì)與實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞鏈?zhǔn)綏５幕静僮鲌D 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.1.5 棧的應(yīng)用1棧是嵌套調(diào)用機(jī)制的實(shí)現(xiàn)基礎(chǔ)2實(shí)現(xiàn)深度遍歷算法時(shí)使用棧3利用棧以非遞歸方式實(shí)現(xiàn)遞歸算法數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例5.2 判斷表達(dá)式中括號(hào)是否匹配數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞判斷表達(dá)式中括號(hào)是否匹配的算法描述 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例5.3 使用棧計(jì)算表達(dá)式的值數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞后綴表達(dá)式求值過(guò)程 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式時(shí)運(yùn)算符棧狀態(tài)的變化情況 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞后綴表達(dá)式求值過(guò)程中數(shù)據(jù)棧狀態(tài)的變化情況 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.2 隊(duì)列5.2.

5、1 隊(duì)列的定義5.2.2 隊(duì)列的抽象數(shù)據(jù)類(lèi)型5.2.3 隊(duì)列的存儲(chǔ)結(jié)構(gòu)5.2.4 順序循環(huán)隊(duì)列類(lèi)5.2.5 鏈?zhǔn)疥?duì)列類(lèi) 5.2.6 隊(duì)列的應(yīng)用數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.2.1 隊(duì)列的定義隊(duì)列（queue）是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進(jìn)行。向隊(duì)列中插入元素的過(guò)程稱(chēng)為入隊(duì)（enqueue），刪除元素的過(guò)程稱(chēng)為出隊(duì)（dequeue）。允許入隊(duì)的一端為隊(duì)尾（rear），允許出隊(duì)的一端為隊(duì)頭（front）。標(biāo)識(shí)隊(duì)頭和隊(duì)尾當(dāng)前位置的變量稱(chēng)為隊(duì)頭指針和隊(duì)尾指針。當(dāng)隊(duì)列中沒(méi)有數(shù)據(jù)元素時(shí)稱(chēng)作空隊(duì)列。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.2.2 隊(duì)列的抽象數(shù)據(jù)類(lèi)型1隊(duì)列的數(shù)據(jù)元素2隊(duì)列的基本操作

6、隊(duì)列的初始化，設(shè)置隊(duì)列狀態(tài)為空。判斷隊(duì)列的狀態(tài)是否為空。判斷隊(duì)列的狀態(tài)是否已滿。入隊(duì)：將數(shù)據(jù)元素從隊(duì)尾處加入隊(duì)列的過(guò)程。在入隊(duì)之前必須判斷隊(duì)列的狀態(tài)是否已滿，如果隊(duì)列不滿，則接收新數(shù)據(jù)元素入隊(duì)，隊(duì)列滿時(shí)數(shù)據(jù)元素不能入隊(duì)，產(chǎn)生上溢錯(cuò)誤（overflow）。出隊(duì)：從隊(duì)頭處取出數(shù)據(jù)元素的過(guò)程。在出隊(duì)之前，必須判斷隊(duì)列的狀態(tài)是否為空。隊(duì)列空時(shí)，取不到元素，產(chǎn)生下溢錯(cuò)誤（underflow）。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.2.3 隊(duì)列的存儲(chǔ)結(jié)構(gòu)1隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞2順序循環(huán)隊(duì)列數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.2.4 順序循環(huán)隊(duì)列類(lèi)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例5.4 使用順序循環(huán)隊(duì)列的基本

7、操作數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.2.5 鏈?zhǔn)疥?duì)列類(lèi) 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞鏈?zhǔn)疥?duì)列的基本操作圖 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.2.6 隊(duì)列的應(yīng)用1處理等待問(wèn)題時(shí)系統(tǒng)設(shè)立隊(duì)列隊(duì)列具有“先進(jìn)先出”的特性，當(dāng)需要按一定次序等待時(shí)，系統(tǒng)需設(shè)立一個(gè)隊(duì)列。2實(shí)現(xiàn)廣度遍歷算法時(shí)使用隊(duì)列實(shí)現(xiàn)廣度遍歷算法，如按層次遍歷二叉樹(shù)、以廣度優(yōu)先算法遍歷圖，都需要使用隊(duì)列。詳細(xì)算法將在以后的章節(jié)中介紹。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例5.5 解素?cái)?shù)環(huán)問(wèn)題數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5.3 遞歸1問(wèn)題的定義是遞歸的2算法是遞歸的如果能夠分解成幾個(gè)相對(duì)簡(jiǎn)單且解法相同或類(lèi)似的子問(wèn)題時(shí)，只要解決了子問(wèn)題，那么原問(wèn)題就迎刃而解，這就是遞歸求解。例如，5！=54！。當(dāng)分解后的子問(wèn)題可以直接解決時(shí)，就停止分解。這些可以直接求解的問(wèn)題稱(chēng)為遞歸結(jié)束條件。例如，1！=1。根據(jù)遞歸定義，編寫(xiě)能夠直接反映遞歸定義的遞歸函數(shù)來(lái)求解。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例5.6 求n！數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例5.7 打印數(shù)字塔數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞3數(shù)據(jù)結(jié)構(gòu)是遞歸的將單向鏈表結(jié)點(diǎn)類(lèi)的next鏈與指向鏈表第1個(gè)結(jié)點(diǎn)的head遞歸定義為：數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例5.8 實(shí)現(xiàn)遞歸定義的單鏈表數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞實(shí)習(xí)41實(shí)驗(yàn)?zāi)康模菏褂脳?、?duì)列或遞歸算法求解問(wèn)題2題意（1）走迷