數(shù)據(jù)結構第05章--棧與隊列課件

1、數(shù)據(jù)結構（C+版）第1章 緒論第2章 線性表第3章 排序第4章 串第5章 棧與隊列第6章 數(shù)組和廣義表第7章 樹和二叉樹第8章 查找第9章 圖第10章 綜合應用設計第5章 棧與隊列棧和隊列是兩種特殊的線性表。5.1 棧5.2 隊列5.3 遞歸數(shù)據(jù)結構（C+版）葉核亞5.1 棧5.1.1 棧的定義5.1.2 棧的抽象數(shù)據(jù)類型5.1.3 順序棧類5.1.4 鏈式棧類5.1.5 棧的應用數(shù)據(jù)結構（C+版）葉核亞5.1.1 棧的定義棧（stack）是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進行。允許操作一端稱為棧頂（top），不允許操作的一端稱為棧底（bottom）。棧頂?shù)漠斍拔恢檬莿討B(tài)

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

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

4、. 鏈式棧類的設計與實現(xiàn)數(shù)據(jù)結構（C+版）葉核亞鏈式棧的基本操作圖 數(shù)據(jù)結構（C+版）葉核亞5.1.5 棧的應用1棧是嵌套調(diào)用機制的實現(xiàn)基礎2實現(xiàn)深度遍歷算法時使用棧3利用棧以非遞歸方式實現(xiàn)遞歸算法數(shù)據(jù)結構（C+版）葉核亞例5.2 判斷表達式中括號是否匹配數(shù)據(jù)結構（C+版）葉核亞判斷表達式中括號是否匹配的算法描述 數(shù)據(jù)結構（C+版）葉核亞例5.3 使用棧計算表達式的值數(shù)據(jù)結構（C+版）葉核亞后綴表達式求值過程 數(shù)據(jù)結構（C+版）葉核亞將中綴表達式變?yōu)楹缶Y表達式時運算符棧狀態(tài)的變化情況 數(shù)據(jù)結構（C+版）葉核亞后綴表達式求值過程中數(shù)據(jù)棧狀態(tài)的變化情況 數(shù)據(jù)結構（C+版）葉核亞5.2 隊列5.2.

5、1 隊列的定義5.2.2 隊列的抽象數(shù)據(jù)類型5.2.3 隊列的存儲結構5.2.4 順序循環(huán)隊列類5.2.5 鏈式隊列類 5.2.6 隊列的應用數(shù)據(jù)結構（C+版）葉核亞5.2.1 隊列的定義隊列（queue）是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進行。向隊列中插入元素的過程稱為入隊（enqueue），刪除元素的過程稱為出隊（dequeue）。允許入隊的一端為隊尾（rear），允許出隊的一端為隊頭（front）。標識隊頭和隊尾當前位置的變量稱為隊頭指針和隊尾指針。當隊列中沒有數(shù)據(jù)元素時稱作空隊列。數(shù)據(jù)結構（C+版）葉核亞5.2.2 隊列的抽象數(shù)據(jù)類型1隊列的數(shù)據(jù)元素2隊列的基本操作

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

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