【正文】 拋出異常 后置條件：如果插入成功，隊尾增加了一個元素 隊列的抽象數(shù)據(jù)類型定義 隊列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 DeQueue 前置條件：隊列已存在 輸入：無 功能：刪除隊頭元素 輸出：如果刪除成功，返回被刪元素值 后置條件：如果刪除成功，隊頭減少了一個元素 GetQueue 前置條件：隊列已存在 輸入：無 功能：讀取隊頭元素 輸出：若隊列不空，返回隊頭元素 后置條件：隊列不變 隊列的抽象數(shù)據(jù)類型定義 隊列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 Empty 前置條件：隊列已存在 輸入：無 功能：判斷隊列是否為空 輸出：如果隊列為空，返回 1，否則，返回 0 后置條件：隊列不變 endADT 隊列的抽象數(shù)據(jù)類型定義 隊列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 0 1 2 3 4 入隊 出隊 隊列的順序存儲結(jié)構(gòu)及實現(xiàn) 順序隊列 ——隊列的順序存儲結(jié)構(gòu) 如何改造數(shù)組實現(xiàn)隊列的順序存儲？ 例： a1a2a3a4依次入隊 a1 a2 a3 a4 rear rear rear rear 入隊操作時間性能為 O(1) 隊列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 如何改造數(shù)組實現(xiàn)隊列的順序存儲？ 例： a1a2依次出隊 隊列的順序存儲結(jié)構(gòu)及實現(xiàn) 0 1 2 3 4 入隊 出隊 a1 a2 a3 a4 rear 隊列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 如何改造數(shù)組實現(xiàn)隊列的順序存儲？ 例： a1a2依次出隊 隊列的順序存儲結(jié)構(gòu)及實現(xiàn) 0 1 2 3 4 入隊 出隊 a2 a3 a4 rear 隊列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 如何改造數(shù)組實現(xiàn)隊列的順序存儲？ 例： a1a2依次出隊 隊列的順序存儲結(jié)構(gòu)及實現(xiàn) 0 1 2 3 4 入隊 出隊 a3 a4 rear 出隊操作時間性能為 O(n) 隊列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 隊列的順序存儲結(jié)構(gòu)及實現(xiàn) 如何改進出隊的時間性能？ 放寬隊列的所有元素必須存儲在數(shù)組的前 n個單元這一條件 ，只要求隊列的元素存儲在數(shù)組中連續(xù)的位置。 ? 允許插入（也稱入隊、進隊）的一端稱為隊尾，允許刪除（也稱出隊）的一端稱為隊頭。 } coutendl。 a = a / b。 int a = 23, b = 2。 總之，當(dāng)棧的使用過程中元素 個數(shù)變化 較大時，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。 空間性能： ?順序棧：有元素個數(shù)的限制和空間浪費的問題。 } 鏈棧的實現(xiàn) ——刪除 操作接口： DataType Pop( )。 delete p。 p = top。 為什么沒有判斷棧滿？ 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 template class DataType DataType LinkStackDataType ::Pop( ) { if (top == NULL) throw 下溢 。 top = s。 sdata = x。 private: NodeDataType *top。 DataType GetTop( )。 void Push(DataType x)。 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 棧的鏈接存儲結(jié)構(gòu)及實現(xiàn) 棧頂 棧底 鏈棧： 棧的鏈接存儲結(jié)構(gòu) top an an1 a1 ∧ first a1 a2 an ∧ ai 兩種示意圖在內(nèi)存中對應(yīng)同一種狀態(tài)，啟示？ top a1 an1 an ∧ 棧頂 棧底 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 鏈 棧 的 類 聲 明 template class DataType class LinkStack { public: LinkStack( )。 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 棧的鏈接存儲結(jié)構(gòu)及實現(xiàn) 鏈棧： 棧的鏈接存儲結(jié)構(gòu) first a1 a2 an ∧ ai 鏈棧需要加頭結(jié)點嗎？ 如何改造鏈表實現(xiàn)棧的鏈接存儲？ 將哪一端作為棧頂？ 將鏈頭作為棧頂，方便操作。 在 top2處填入 x； 兩棧共享空間的實現(xiàn) ——插入 操作接口： void Push(int i, DataType x) 。 兩棧共享空間類的聲明 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 1. 如果棧滿 ， 則拋出上溢異常； 2. 判斷是插在棧 1還是棧 2； 若在棧 1插入 ， 則 top1加 1。 int top1, top2。 bool Empty(int i)。 DataType Pop(int i)。 ~BothStack( )。 top1和 top2分別為棧 1和棧 2的棧頂指針； Stack_Size為整個數(shù)組空間的大?。▓D中用 S表示）； a1 a2 … ai top1 0 1 2 … … S1 兩棧共享空間 top2 bj … … b2 b1 棧 1底 棧 2底 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 top1= 1 什么時候棧 1為空？ a1 a2 … ai top1 0 1 2 … … S1 兩棧共享空間 top2 bj … … b2 b1 top1 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 top1= 1 什么時候棧 1為空？ a1 a2 … ai top1 0 1 2 … … S1 兩棧共享空間 top2 bj … … b2 b1 什么時候棧 2為空？ top2 top2= Stack_Size 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 top1= 1 什么時候棧 1為空？ a1 a2 … … ai top1 0 1 2 … … S1 兩棧共享空間 top2 bj … … b2 b1 什么時候棧 2為空？ top2= Stack_Size 什么時候棧滿？ top2= top1+1 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 const int StackSize=100。 解決方案 2： 順序棧單向延伸 ——使用一個數(shù)組來存儲兩個棧 在一個程序中需要 同時 使用具有 相同 數(shù)據(jù)類型的兩個棧 ， 如何順序存儲這兩個棧？ 會出現(xiàn)什么問題？如何解決？ 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 兩棧共享空間： 使用一個數(shù)組來存儲兩個棧，讓一個棧的棧底為該數(shù)組的始端，另一個棧的棧底為該數(shù)組的末端，兩個棧從各自的端點向中間延伸。 } 操作接口： DataType Pop( )。 x = data[top]。 } 操作接口： void Push( DataType x )。 top++。 int top。 bool Empty ( )。 DataType Pop ( )。 ~seqStack ( )。 top 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 出棧： top減 1 進棧： top加 1 ?？眨?top= 1 0 1 2 3 4 5 6 7 8 a1 top a2 top a3 top 棧滿： top= MAX_SIZE1 棧的順序存儲結(jié)構(gòu)及實現(xiàn) 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 順序棧類的聲明 const int StackSize=100。 例：有三個元素按 a、 b、 c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？ 棧的邏輯結(jié)構(gòu) ? 情況 3： 棧 出棧序列： a、 b、 c ? 情況 4： 出棧序列： a、 c、 b ? 情況 5： 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 棧的抽象數(shù)據(jù)類型定義 ADT Stack Data 棧中元素具有相同類型及后進先出特性， 相鄰元素具有前驅(qū)和后繼關(guān)系 Operation InitStack 前置條件：棧不存在 輸入：無 功能：棧的初始化 輸出：無 后置條件：構(gòu)造一個空棧 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 DestroyStack 前置條件：棧已存在 輸入：無 功能：銷毀棧 輸出：無 后置條件：釋放棧所占用的存儲空間 Push 前置條件：棧已存在 輸入：元素值 x 功能：在棧頂插入一個元素 x 輸出：如果插入不成功，拋出異常 后置條件：如果插入成功，棧頂增加了一個元素 棧的抽象數(shù)據(jù)類型定義 棧 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 Pop 前置條件：棧已存在 輸入：無 功能：刪除棧頂元素 輸出：如果刪除成功，返回被刪元素值，否則，拋出異常 后置條件：如果刪除成功，棧減少了一個元素 GetTop 前置條件：棧已存在