1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社第第 3 章章 棧和隊(duì)列棧和隊(duì)列本章的基本內(nèi)容是：本章的基本內(nèi)容是：兩種特殊的線性表兩種特殊的線性表?xiàng)：完?duì)列棧和隊(duì)列從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是操作受限操作受限的線的線性表，他們的邏輯結(jié)構(gòu)相同。性表，他們的邏輯結(jié)構(gòu)相同。從抽象數(shù)據(jù)類(lèi)型角度看，棧和隊(duì)列是兩種重要從抽象數(shù)據(jù)類(lèi)型角度看，棧和隊(duì)列是兩種重要的抽象數(shù)據(jù)類(lèi)型。的抽象數(shù)據(jù)類(lèi)型。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 3.1 棧棧棧的邏輯結(jié)構(gòu)棧的邏輯結(jié)構(gòu)（a1, a2, , an）p棧：棧：限定僅在限定僅在表的一

2、端表的一端進(jìn)行插入和刪除操作的進(jìn)行插入和刪除操作的線性表線性表。p允許插入和刪除的一端稱為棧頂，另一端稱為棧底。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。p空棧：空棧：不含任何數(shù)據(jù)元素的棧。不含任何數(shù)據(jù)元素的棧。 棧頂棧頂棧底棧底數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社a1a2a3入棧入棧出棧出棧棧底棧底棧頂棧頂插入：入棧、進(jìn)棧、壓棧插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧刪除：出棧、彈棧棧頂棧頂棧頂棧頂 3.1 棧棧棧的邏輯結(jié)構(gòu)棧的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社棧的操作特性：棧的操作特性：后進(jìn)先出后進(jìn)先出a1a2

3、a3入棧入棧出棧出棧棧底棧底棧頂棧頂插入：入棧、進(jìn)棧、壓棧插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧刪除：出棧、彈棧棧頂棧頂 3.1 棧棧棧的邏輯結(jié)構(gòu)棧的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社例：有三個(gè)元素按例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底棧底棧頂棧頂ab棧頂棧頂c棧頂棧頂 情況情況1：棧的邏輯結(jié)構(gòu)棧的邏輯結(jié)構(gòu) 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社棧底棧底棧頂棧頂ab棧頂棧頂c棧頂

4、棧頂出棧序列：出棧序列：c出棧序列：出棧序列：c、b出棧序列：出棧序列：c、b、a例：有三個(gè)元素按例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)棧的邏輯結(jié)構(gòu) 情況情況1： 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社棧底棧底棧頂棧頂ab棧頂棧頂出棧序列：出棧序列：b 情況情況2：例：有三個(gè)元素按例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？元素只允許進(jìn)一次棧，則

5、可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)棧的邏輯結(jié)構(gòu) 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社棧底棧底a出棧序列：出棧序列：b出棧序列：出棧序列：b、c出棧序列：出棧序列： b、 c、ac棧頂棧頂棧頂棧頂注意：注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒(méi)有限定插入和刪除操作進(jìn)行的時(shí)間。制，并沒(méi)有限定插入和刪除操作進(jìn)行的時(shí)間。例：有三個(gè)元素按例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)

6、棧的邏輯結(jié)構(gòu) 情況情況2： 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社棧的抽象數(shù)據(jù)類(lèi)型定義棧的抽象數(shù)據(jù)類(lèi)型定義 ADT StackData 棧中元素具有相同類(lèi)型及后進(jìn)先出特性，棧中元素具有相同類(lèi)型及后進(jìn)先出特性， 相鄰元素具有前驅(qū)和后繼關(guān)系相鄰元素具有前驅(qū)和后繼關(guān)系Operation InitStack 前置條件：棧不存在前置條件：棧不存在 輸入：無(wú)輸入：無(wú) 功能：棧的初始化功能：棧的初始化 輸出：無(wú)輸出：無(wú) 后置條件：構(gòu)造一個(gè)空棧后置條件：構(gòu)造一個(gè)空棧 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社DestroySt

7、ack 前置條件：棧已存在前置條件：棧已存在 輸入：無(wú)輸入：無(wú) 功能：銷(xiāo)毀棧功能：銷(xiāo)毀棧 輸出：無(wú)輸出：無(wú) 后置條件：釋放棧所占用的存儲(chǔ)空間后置條件：釋放棧所占用的存儲(chǔ)空間Push 前置條件：棧已存在前置條件：棧已存在 輸入：元素值輸入：元素值x 功能：在棧頂插入一個(gè)元素功能：在棧頂插入一個(gè)元素x 輸出：如果插入不成功，拋出異常輸出：如果插入不成功，拋出異常 后置條件：如果插入成功，棧頂增加了一個(gè)元素后置條件：如果插入成功，棧頂增加了一個(gè)元素棧的抽象數(shù)據(jù)類(lèi)型定義棧的抽象數(shù)據(jù)類(lèi)型定義 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社Pop 前置條件：棧已存在前置

8、條件：棧已存在 輸入：無(wú)輸入：無(wú) 功能：刪除棧頂元素功能：刪除棧頂元素 輸出：如果刪除成功，返回被刪元素值，否則，拋出異常輸出：如果刪除成功，返回被刪元素值，否則，拋出異常 后置條件：如果刪除成功，棧減少了一個(gè)元素后置條件：如果刪除成功，棧減少了一個(gè)元素GetTop 前置條件：棧已存在前置條件：棧已存在 輸入：無(wú)輸入：無(wú) 功能：讀取當(dāng)前的棧頂元素功能：讀取當(dāng)前的棧頂元素 輸出：若棧不空，返回當(dāng)前的棧頂元素值輸出：若棧不空，返回當(dāng)前的棧頂元素值 后置條件：棧不變后置條件：棧不變棧的抽象數(shù)據(jù)類(lèi)型定義棧的抽象數(shù)據(jù)類(lèi)型定義 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出

9、版社Empty 前置條件：棧已存在前置條件：棧已存在 輸入：無(wú)輸入：無(wú) 功能：判斷棧是否為空功能：判斷棧是否為空 輸出：如果棧為空，返回輸出：如果棧為空，返回1，否則，返回，否則，返回0 后置條件：棧不變后置條件：棧不變endADT棧的抽象數(shù)據(jù)類(lèi)型定義棧的抽象數(shù)據(jù)類(lèi)型定義 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序棧順序棧棧的順序存儲(chǔ)結(jié)構(gòu)棧的順序存儲(chǔ)結(jié)構(gòu)如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？ 0 1 2 3 4 5 6 7 8a1確定用數(shù)組的哪一端表示棧底。確定用數(shù)組的哪一端表示棧底

10、。附設(shè)指針附設(shè)指針top指示棧頂元素在數(shù)組中的位置。指示棧頂元素在數(shù)組中的位置。 top 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社出棧：出棧：top減減1進(jìn)棧：進(jìn)棧：top加加1?？眨簵？眨簍op= - -1 0 1 2 3 4 5 6 7 8a1topa2topa3top棧滿：棧滿：top= MAX_SIZE- -1棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 順序棧類(lèi)的聲明順序棧類(lèi)的聲明const int MAX_SIZE=100;template class se

11、qStack public: seqStack ( ) ; seqStack ( ); void Push ( DataType x ); DataType Pop ( ); DataType GetTop ( ); bool Empty ( ); private: DataType dataMAX_SIZE; int top; 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社順序棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)入棧入棧template void seqStack :Push ( DataType x) if (top = MAX_SIZE- -1) throw “溢出溢

12、出”; top+; datatop = x; 操作接口：操作接口： void Push( DataType x );時(shí)間復(fù)雜度？時(shí)間復(fù)雜度？data+top = x 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社順序棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)出棧出棧template DataType seqStack : Pop ( ) if (top = - -1) throw “溢出溢出”; x = datatop-; return x;操作接口：操作接口： DataType Pop( );時(shí)間復(fù)雜度？時(shí)間復(fù)雜度？ 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大

13、學(xué)出版社清華大學(xué)出版社兩棧共享空間兩棧共享空間 解決方案解決方案1：直接解決：為每個(gè)棧開(kāi)辟一個(gè)數(shù)組空間。直接解決：為每個(gè)棧開(kāi)辟一個(gè)數(shù)組空間。 解決方案解決方案2： 順序棧單向延伸順序棧單向延伸使用一個(gè)數(shù)組來(lái)存儲(chǔ)兩個(gè)棧使用一個(gè)數(shù)組來(lái)存儲(chǔ)兩個(gè)棧在一個(gè)程序中需要在一個(gè)程序中需要同時(shí)同時(shí)使用具有使用具有相同相同數(shù)據(jù)類(lèi)型的數(shù)據(jù)類(lèi)型的兩個(gè)棧兩個(gè)棧，如何順序存儲(chǔ)這兩個(gè)棧？如何順序存儲(chǔ)這兩個(gè)棧？會(huì)出現(xiàn)什么問(wèn)題？如何解決？會(huì)出現(xiàn)什么問(wèn)題？如何解決？ 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社兩棧共享空間：兩棧共享空間：使用一個(gè)數(shù)組來(lái)存儲(chǔ)兩個(gè)棧，讓一個(gè)使用一個(gè)數(shù)組來(lái)存儲(chǔ)兩個(gè)

14、棧，讓一個(gè)棧的棧底為該數(shù)組的始端，另一個(gè)棧的棧底為該數(shù)組棧的棧底為該數(shù)組的始端，另一個(gè)棧的棧底為該數(shù)組的末端，兩個(gè)棧從各自的端點(diǎn)向中間延伸。的末端，兩個(gè)棧從各自的端點(diǎn)向中間延伸。兩棧共享空間兩棧共享空間 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社棧棧1的底固定在下標(biāo)為的底固定在下標(biāo)為0的一端；的一端；棧棧2的底固定在下標(biāo)為的底固定在下標(biāo)為StackSize-1的一端。的一端。 top1和和top2分別為棧分別為棧1和棧和棧2的棧頂指針；的棧頂指針；Stack_Size為整個(gè)數(shù)組空間的大?。▓D中用為整個(gè)數(shù)組空間的大?。▓D中用S表示）；表示）；a1 a2 a

15、itop10 1 2 S-1兩棧共享空間兩棧共享空間 top2bj b2 b1棧棧1底底棧棧2底底 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社top1= -1什么時(shí)候棧什么時(shí)候棧1為空？為空？a1 a2 aitop10 1 2 S-1兩棧共享空間兩棧共享空間 top2bj b2 b1top1 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社top1= -1什么時(shí)候棧什么時(shí)候棧1為空？為空？a1 a2 aitop10 1 2 S-1兩棧共享空間兩棧共享空間 top2bj b2 b1什么時(shí)候棧什么時(shí)候棧2為空？為空？top2

16、top2= Stack_Size 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社top1= -1什么時(shí)候棧什么時(shí)候棧1為空？為空？a1 a2 aitop10 1 2 S-1兩棧共享空間兩棧共享空間 top2bj b2 b1什么時(shí)候棧什么時(shí)候棧2為空？為空？top2= Stack_Size什么時(shí)候棧滿？什么時(shí)候棧滿？top2= top1+1 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社const int Stack_Size=100; template class BothStack public: BothStack(

17、)( ); BothStack( )( ); void Push( (int i, DataType x) ); DataType Pop( (int i) ); DataType GetTop( (int i) ); bool Empty( (int i) ); private: DataType dataStack_Size; int top1, top2; ;兩棧共享空間類(lèi)的聲明兩棧共享空間類(lèi)的聲明 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社1. 如果棧滿，則拋出上溢異常；如果棧滿，則拋出上溢異常；2. 判斷是插在棧判斷是插在棧1還是棧還是棧2；

18、2.1 若在棧若在棧1插入，則插入，則 2.1.1 top1加加1; 2.1.2 在在top1處填入處填入x； 2.2 若在棧若在棧2插入，則插入，則 2.2.1 top2減減1; 2.2.2 在在top2處填入處填入x；兩棧共享空間的實(shí)現(xiàn)兩棧共享空間的實(shí)現(xiàn)插入插入 操作接口：操作接口：void Push(int i, DataType x) ; 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社1. 若是在棧若是在棧1刪除，則刪除，則 1.1 若棧若棧1為空棧，拋出下溢異常；為空棧，拋出下溢異常； 1.2 刪除并返回棧刪除并返回棧1的棧頂元素；的棧頂元素；2.

19、 若是在棧若是在棧2刪除，則刪除，則 2.1 若棧若棧2為空棧，拋出下溢異常；為空棧，拋出下溢異常； 2.2 刪除并返回棧刪除并返回棧2的棧頂元素；的棧頂元素；兩棧共享空間的實(shí)現(xiàn)兩棧共享空間的實(shí)現(xiàn)刪除刪除 操作接口：操作接口：DataType Pop(int i) ; 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 鏈棧：鏈棧：棧的鏈接存儲(chǔ)結(jié)構(gòu)棧的鏈接存儲(chǔ)結(jié)構(gòu)firsta1a2anai鏈棧需要加頭結(jié)點(diǎn)嗎？鏈棧需要加頭結(jié)點(diǎn)嗎？如何改造鏈表實(shí)現(xiàn)棧的鏈接存儲(chǔ)？如何改造鏈表實(shí)現(xiàn)棧的鏈接存儲(chǔ)？將哪一端作為棧頂？將哪一端作為棧

20、頂？ 將鏈頭作為棧頂，方便操作。將鏈頭作為棧頂，方便操作。鏈棧不需要附設(shè)頭結(jié)點(diǎn)。鏈棧不需要附設(shè)頭結(jié)點(diǎn)。 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 棧頂棧頂棧底棧底鏈棧：鏈棧：棧的鏈接存儲(chǔ)結(jié)構(gòu)棧的鏈接存儲(chǔ)結(jié)構(gòu)topanan-1a1firsta1a2anai兩種示意圖在內(nèi)存中對(duì)兩種示意圖在內(nèi)存中對(duì)應(yīng)同一種狀態(tài)，啟示？應(yīng)同一種狀態(tài)，啟示？topa1an-1an棧頂棧頂棧底棧底 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社鏈鏈棧棧的的類(lèi)類(lèi)聲聲明明template class Li

21、nkStack public: LinkStack( )( ); LinkStack( )( ); void Push( (DataType x) ); DataType Pop( )( ); DataType GetTop( )( ); bool Empty( )( ); private: Node *top; 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template void LinkStack :Push( (DataType x) ) s = new Node; s-data = x; s-next = top; top = s; topana

22、n-1a1鏈棧的實(shí)現(xiàn)鏈棧的實(shí)現(xiàn)插入插入 xstop操作接口：操作接口： void Push(DataType x); 為什么沒(méi)有判斷棧滿？為什么沒(méi)有判斷棧滿？ 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template DataType LinkStack :Pop( ) if ( (top = NULL) ) throw 下溢下溢; x = top-data; p = top; top = top-next; delete p; return x;鏈棧的實(shí)現(xiàn)鏈棧的實(shí)現(xiàn)刪除刪除操作接口：操作接口： DataType Pop( ); topanan-1a1

23、topp top+可以嗎？可以嗎？ 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社順序棧和鏈棧的比較順序棧和鏈棧的比較時(shí)間性能：時(shí)間性能：相同，都是常數(shù)時(shí)間相同，都是常數(shù)時(shí)間O(1)。空間性能：空間性能：順序棧：有元素個(gè)數(shù)的限制和空間浪費(fèi)的問(wèn)題。順序棧：有元素個(gè)數(shù)的限制和空間浪費(fèi)的問(wèn)題。鏈棧：沒(méi)有棧滿的問(wèn)題，只有當(dāng)內(nèi)存沒(méi)有可用空鏈棧：沒(méi)有棧滿的問(wèn)題，只有當(dāng)內(nèi)存沒(méi)有可用空間時(shí)才會(huì)出現(xiàn)棧滿，但是每個(gè)元素都需要一個(gè)指針間時(shí)才會(huì)出現(xiàn)棧滿，但是每個(gè)元素都需要一個(gè)指針域，從而產(chǎn)生了結(jié)構(gòu)性開(kāi)銷(xiāo)。域，從而產(chǎn)生了結(jié)構(gòu)性開(kāi)銷(xiāo)。 總之，當(dāng)棧的使用過(guò)程中元素總之，當(dāng)棧的使用過(guò)程中元

24、素個(gè)數(shù)變化個(gè)數(shù)變化較大時(shí)，用較大時(shí)，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。鏈棧是適宜的，反之，應(yīng)該采用順序棧。 3.1 棧棧數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社3.2 隊(duì)列隊(duì)列隊(duì)列的邏輯結(jié)構(gòu)隊(duì)列的邏輯結(jié)構(gòu)p 隊(duì)列：隊(duì)列：只允許在只允許在一端一端進(jìn)行插入操作，而進(jìn)行插入操作，而另一端另一端進(jìn)進(jìn)行刪除操作的線性表。行刪除操作的線性表。p 允許插入（也稱入隊(duì)、進(jìn)隊(duì)）的一端稱為隊(duì)尾，允許插入（也稱入隊(duì)、進(jìn)隊(duì)）的一端稱為隊(duì)尾，允許刪除（也稱出隊(duì)）的一端稱為隊(duì)頭。允許刪除（也稱出隊(duì)）的一端稱為隊(duì)頭。p 空隊(duì)列：空隊(duì)列：不含任何數(shù)據(jù)元素的隊(duì)列。不含任何數(shù)據(jù)元素的隊(duì)列。（a1

25、, a2, , an）隊(duì)尾隊(duì)尾隊(duì)頭隊(duì)頭數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社隊(duì)列的操作特性：隊(duì)列的操作特性：先進(jìn)先出先進(jìn)先出a1a2a3入隊(duì)入隊(duì)隊(duì)尾隊(duì)尾隊(duì)頭隊(duì)頭出隊(duì)出隊(duì)隊(duì)頭隊(duì)頭隊(duì)列的邏輯結(jié)構(gòu)隊(duì)列的邏輯結(jié)構(gòu)3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義 ADT Queue Data 隊(duì)列中元素具有相同類(lèi)型及先進(jìn)先出特性，隊(duì)列中元素具有相同類(lèi)型及先進(jìn)先出特性， 相鄰元素具有前驅(qū)和后繼關(guān)系相鄰元素具有前驅(qū)和后繼關(guān)系Operation InitQueue 前置條件：隊(duì)列不存在前置條件：隊(duì)

26、列不存在 輸入：無(wú)輸入：無(wú) 功能：初始化隊(duì)列功能：初始化隊(duì)列 輸出：無(wú)輸出：無(wú) 后置條件：創(chuàng)建一個(gè)空隊(duì)列后置條件：創(chuàng)建一個(gè)空隊(duì)列3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 DestroyQueue 前置條件：隊(duì)列已存在前置條件：隊(duì)列已存在 輸入：無(wú)輸入：無(wú) 功能：銷(xiāo)毀隊(duì)列功能：銷(xiāo)毀隊(duì)列 輸出：無(wú)輸出：無(wú) 后置條件：釋放隊(duì)列所占用的存儲(chǔ)空間后置條件：釋放隊(duì)列所占用的存儲(chǔ)空間 EnQueue 前置條件：隊(duì)列已存在前置條件：隊(duì)列已存在 輸入：元素值輸入：元素值x 功能：在隊(duì)尾插入一個(gè)元素功能：在隊(duì)尾插入一個(gè)元素 輸出：如果插入不成功，拋出異常輸出：如果插入

27、不成功，拋出異常 后置條件：如果插入成功，隊(duì)尾增加了一個(gè)元素后置條件：如果插入成功，隊(duì)尾增加了一個(gè)元素隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義 3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 DeQueue 前置條件：隊(duì)列已存在前置條件：隊(duì)列已存在 輸入：無(wú)輸入：無(wú) 功能：刪除隊(duì)頭元素功能：刪除隊(duì)頭元素 輸出：如果刪除成功，返回被刪元素值輸出：如果刪除成功，返回被刪元素值 后置條件：如果刪除成功，隊(duì)頭減少了一個(gè)元素后置條件：如果刪除成功，隊(duì)頭減少了一個(gè)元素 GetQueue 前置條件：隊(duì)列已存在前置條件：隊(duì)列已存在 輸入：無(wú)輸入：無(wú) 功能：讀取隊(duì)頭元

28、素功能：讀取隊(duì)頭元素 輸出：若隊(duì)列不空，返回隊(duì)頭元素輸出：若隊(duì)列不空，返回隊(duì)頭元素 后置條件：隊(duì)列不變后置條件：隊(duì)列不變隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義 3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社Empty 前置條件：隊(duì)列已存在前置條件：隊(duì)列已存在 輸入：無(wú)輸入：無(wú) 功能：判斷隊(duì)列是否為空功能：判斷隊(duì)列是否為空 輸出：如果隊(duì)列為空，返回輸出：如果隊(duì)列為空，返回1，否則，返回，否則，返回0 后置條件：隊(duì)列不變后置條件：隊(duì)列不變endADT隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義 3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版

29、清華大學(xué)出版社清華大學(xué)出版社0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序隊(duì)列順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：例：a1a2a3a4依次入隊(duì)依次入隊(duì)a1a2a3a4rearrear rear rear入隊(duì)操作時(shí)間性能為入隊(duì)操作時(shí)間性能為O(1)3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：例：a1a2依次出隊(duì)依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0

30、 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a1a2a3a4rear3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：例：a1a2依次出隊(duì)依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a2a3a4rear3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：例：a1a2依次出隊(duì)依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入

31、隊(duì)入隊(duì)出隊(duì)出隊(duì)a3a4rear出隊(duì)操作時(shí)間性能為出隊(duì)操作時(shí)間性能為O(n)3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何改進(jìn)出隊(duì)的時(shí)間性能？如何改進(jìn)出隊(duì)的時(shí)間性能？放寬隊(duì)列的所有元素必須存儲(chǔ)在數(shù)組的前放寬隊(duì)列的所有元素必須存儲(chǔ)在數(shù)組的前n個(gè)單元這一個(gè)單元這一條件條件 ，只要求隊(duì)列的元素存儲(chǔ)在數(shù)組中連續(xù)的位置。，只要求隊(duì)列的元素存儲(chǔ)在數(shù)組中連續(xù)的位置。設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)指針設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)指針 3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)

32、現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)例：例：a1a2a3a4依次入隊(duì)依次入隊(duì)a1a2a3a4rearrear rear rear入隊(duì)操作時(shí)間性能仍為入隊(duì)操作時(shí)間性能仍為O(1)front rear3.2 隊(duì)列隊(duì)列約定：隊(duì)頭指針約定：隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，指向隊(duì)頭元素的前一個(gè)位置， 隊(duì)尾指針隊(duì)尾指針rear指向隊(duì)尾元素。指向隊(duì)尾元素。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社例：例：a1a2依次出隊(duì)依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a1a2a3a4rearfr

33、ont front front出隊(duì)操作時(shí)間性能提高為出隊(duì)操作時(shí)間性能提高為O(1)3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社例：例：a1a2依次出隊(duì)依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a3a4rearfront隊(duì)列的移動(dòng)有什么特點(diǎn)？隊(duì)列的移動(dòng)有什么特點(diǎn)？3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社例：例：a1a2依次出隊(duì)依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a3a4rearfront整個(gè)隊(duì)列向數(shù)組

34、下標(biāo)較大方向移動(dòng)整個(gè)隊(duì)列向數(shù)組下標(biāo)較大方向移動(dòng)單向移動(dòng)性單向移動(dòng)性3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社假溢出：假溢出：當(dāng)元素被插入到數(shù)組中下標(biāo)最大的位置上之當(dāng)元素被插入到數(shù)組中下標(biāo)最大的位置上之后，隊(duì)列的空間就用盡了，盡管此時(shí)數(shù)組的低端還有后，隊(duì)列的空間就用盡了，盡管此時(shí)數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出?？臻e空間，這種現(xiàn)象叫做假溢出。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 繼續(xù)入隊(duì)會(huì)出現(xiàn)什么情況？繼續(xù)入隊(duì)會(huì)出現(xiàn)什么情況？0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a3a4rearfronta5rear3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)

35、構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社循環(huán)隊(duì)列：循環(huán)隊(duì)列：將存儲(chǔ)隊(duì)列的數(shù)組頭尾相接。將存儲(chǔ)隊(duì)列的數(shù)組頭尾相接。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何解決假溢出？如何解決假溢出？0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a3a4fronta5rearreara63.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社不存在物理的循環(huán)結(jié)構(gòu)，用軟件方法實(shí)現(xiàn)。不存在物理的循環(huán)結(jié)構(gòu)，用軟件方法實(shí)現(xiàn)。求模求模：（：（41）mod 50隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何實(shí)現(xiàn)循環(huán)隊(duì)列？如何實(shí)現(xiàn)循環(huán)隊(duì)列？0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)

36、出隊(duì)a3a4frontreara63.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社如何判斷循環(huán)隊(duì)列隊(duì)空？如何判斷循環(huán)隊(duì)列隊(duì)空？隊(duì)空的臨界狀態(tài)隊(duì)空的臨界狀態(tài)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a3rearfront3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社如何判斷循環(huán)隊(duì)列隊(duì)空？如何判斷循環(huán)隊(duì)列隊(duì)空？執(zhí)行出隊(duì)操作執(zhí)行出隊(duì)操作隊(duì)空：隊(duì)空：front=rear隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a3front rearfr

37、ont3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社如何判斷循環(huán)隊(duì)列隊(duì)滿？如何判斷循環(huán)隊(duì)列隊(duì)滿？隊(duì)滿的臨界狀態(tài)隊(duì)滿的臨界狀態(tài)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a3a4fronta5reara63.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社如何判斷循環(huán)隊(duì)列隊(duì)滿？如何判斷循環(huán)隊(duì)列隊(duì)滿？執(zhí)行入隊(duì)操作執(zhí)行入隊(duì)操作隊(duì)滿：隊(duì)滿：front=rear隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a3a4fronta5reara6reara

38、73.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社方法一：方法一：附設(shè)一個(gè)存儲(chǔ)隊(duì)列中元素個(gè)數(shù)的變量附設(shè)一個(gè)存儲(chǔ)隊(duì)列中元素個(gè)數(shù)的變量num，當(dāng)當(dāng)num=0時(shí)隊(duì)空，當(dāng)時(shí)隊(duì)空，當(dāng)num=QueueSize時(shí)為隊(duì)滿；時(shí)為隊(duì)滿；方法二：方法二：修改隊(duì)滿條件，浪費(fèi)一個(gè)元素空間，隊(duì)滿時(shí)修改隊(duì)滿條件，浪費(fèi)一個(gè)元素空間，隊(duì)滿時(shí)數(shù)組中只有一個(gè)空閑單元數(shù)組中只有一個(gè)空閑單元；方法三：方法三：設(shè)置標(biāo)志設(shè)置標(biāo)志flag，當(dāng)當(dāng)front=rear且且flag=0時(shí)為隊(duì)時(shí)為隊(duì)空，當(dāng)空，當(dāng)front=rear且且flag=1時(shí)為隊(duì)滿。時(shí)為隊(duì)滿。如何確定不同的隊(duì)空、隊(duì)滿的判定條件？如何確定

39、不同的隊(duì)空、隊(duì)滿的判定條件？為什么要將隊(duì)空和隊(duì)滿的判定條件分開(kāi)？為什么要將隊(duì)空和隊(duì)滿的判定條件分開(kāi)？隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社隊(duì)滿的條件：隊(duì)滿的條件：(rear+1) mod QueueSize=front隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)入隊(duì)rearfronta3a4fronta5reara6出隊(duì)出隊(duì)3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社循循環(huán)環(huán)隊(duì)隊(duì)列列類(lèi)類(lèi)的的聲聲明明const int Queu

40、eSize=100; template class CirQueue public: CirQueue( )( )； CirQueue( )( )； void EnQueue( (DataType x) ); DataType DeQueue( )( ); DataType GetQueue( )( ); bool Empty( )( )； private: DataType dataQueueSize; int front, rear;3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template void CirQueue :EnQueue( (Da

41、taType x) ) if (rear+1) ) % QueueSize = front) ) throw 上溢上溢; rear =( (rear+1) ) % QueueSize; datarear = x; 循環(huán)隊(duì)列的實(shí)現(xiàn)循環(huán)隊(duì)列的實(shí)現(xiàn)入隊(duì)入隊(duì)0 1 2 3 4 入隊(duì)入隊(duì)出隊(duì)出隊(duì)a3a4rearfronta5rear3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社0 1 2 3 4 入隊(duì)入隊(duì)a4a5a6出隊(duì)出隊(duì)template DataType CirQueue :DeQueue( ) if (rear = front) throw 下溢下溢; fr

42、ont = (front + 1) % QueueSize; return datafront; 循環(huán)隊(duì)列的實(shí)現(xiàn)循環(huán)隊(duì)列的實(shí)現(xiàn)出隊(duì)出隊(duì)frontrearfronta33.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template DataType CirQueue :GetQueue( ) if (rear = front) throw 下溢下溢; i = (front + 1) % QueueSize; return datai;循環(huán)隊(duì)列的實(shí)現(xiàn)循環(huán)隊(duì)列的實(shí)現(xiàn)讀隊(duì)頭元素讀隊(duì)頭元素0 1 2 3 4 入隊(duì)入隊(duì)a4a5a6出隊(duì)出隊(duì)frontreara3 i3

43、.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 鏈隊(duì)列：鏈隊(duì)列：隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu) 隊(duì)頭指針即為鏈表的頭指針隊(duì)頭指針即為鏈表的頭指針firsta1a2an如何改造單鏈表實(shí)現(xiàn)隊(duì)列的鏈接存儲(chǔ)？如何改造單鏈表實(shí)現(xiàn)隊(duì)列的鏈接存儲(chǔ)？rearfront3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 非空鏈隊(duì)列非空鏈隊(duì)列fronta1a2anrear空鏈隊(duì)列空鏈隊(duì)列frontrear3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（

44、C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社鏈鏈隊(duì)隊(duì)列列類(lèi)類(lèi)的的聲聲明明template class LinkQueue public: LinkQueue( )( ); LinkQueue( )( ); void EnQueue( (DataType x) ); DataType DeQueue( )( ); DataType GetQueue( )( )； bool Empty( )( )； private: Node *front, *rear;3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社操作接口：操作接口： LinkQueue( ); 算

45、法描述：算法描述：template LinkQueue :LinkQueue( ) front = new Node; front-next = NULL; rear = front;鏈隊(duì)列的實(shí)現(xiàn)鏈隊(duì)列的實(shí)現(xiàn)構(gòu)造函數(shù)構(gòu)造函數(shù)frontrear3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 xs鏈隊(duì)列的實(shí)現(xiàn)鏈隊(duì)列的實(shí)現(xiàn)入隊(duì)入隊(duì)操作接口：操作接口： void EnQueue(DataType x);fronta1anrearrearfront xsrearrear算法描述：算法描述：s-next=NULL;rear-next=s; rear=s;如果沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？如果沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 xs鏈隊(duì)列的實(shí)現(xiàn)鏈隊(duì)列的實(shí)現(xiàn)入隊(duì)入隊(duì)操作接口：操作接口： void EnQueue(DataType x);fronta2anrearrear算法描述：算法描述：s-next=NULL;rear-next=s;