堆棧和隊(duì)列ppt課件

1、第第3章章 限定性線性表限定性線性表堆棧和隊(duì)列堆棧和隊(duì)列3.1 3.1 堆棧堆棧3.2 3.2 堆棧運(yùn)用堆棧運(yùn)用3.43.4* * 優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列 棧和隊(duì)列是兩種重要的籠統(tǒng)數(shù)據(jù)類型，是一類棧和隊(duì)列是兩種重要的籠統(tǒng)數(shù)據(jù)類型，是一類操作受限制的特殊線性表，其特殊性在于限制插入操作受限制的特殊線性表，其特殊性在于限制插入和刪除等運(yùn)算的位置。和刪除等運(yùn)算的位置。3.3 3.3 隊(duì)列隊(duì)列3.1 3.1 堆堆 棧棧3.1.1 3.1.1 堆棧的根本概念堆棧的根本概念 堆棧的定義：限定只能在固定一堆棧的定義：限定只能在固定一端進(jìn)展插入和刪除操作的線性表。端進(jìn)展插入和刪除操作的線性表。 通常將表中允許進(jìn)

2、展插入、刪除通常將表中允許進(jìn)展插入、刪除操作的一端稱為棧頂操作的一端稱為棧頂 (Top)，表的另，表的另一端被稱為棧底一端被稱為棧底 (Bottom)。 當(dāng)棧中沒有元素時(shí)稱為空棧。棧當(dāng)棧中沒有元素時(shí)稱為空棧。棧的插入操作被籠統(tǒng)地稱為進(jìn)?；蛉霔?，的插入操作被籠統(tǒng)地稱為進(jìn)?；蛉霔?，刪除操作稱為出棧或退棧。棧又稱為刪除操作稱為出?；蛲藯?。棧又稱為后進(jìn)先出的線性表，即后進(jìn)先出的線性表，即LIFO。 根據(jù)棧定義，每次進(jìn)棧的元素都被放在原棧根據(jù)棧定義，每次進(jìn)棧的元素都被放在原棧頂元素之上而成為新的棧頂，而每次出棧的總是頂元素之上而成為新的棧頂，而每次出棧的總是當(dāng)前棧中當(dāng)前棧中“最新的元素，即最后進(jìn)棧的元素

3、。因最新的元素，即最后進(jìn)棧的元素。因此，棧又稱為后進(jìn)先出的線性表。簡稱為此，棧又稱為后進(jìn)先出的線性表。簡稱為LIFO表。表。如以下圖所示：如以下圖所示： 進(jìn)棧、出棧圖例進(jìn)棧、出棧圖例進(jìn)棧進(jìn)棧出棧出棧ana2a1進(jìn)棧進(jìn)棧出棧出棧棧頂棧頂棧底棧底 例3-1 利用一個(gè)堆棧，假設(shè)輸入系列由A、B、C組成，試給出全部能夠的輸出系列和不能夠的輸出系列。 輸出系列有： ABC、ACB、BAC、BCA、CBA 不能夠的輸出系列為： CAB3.1.2 棧的籠統(tǒng)數(shù)據(jù)類型定義棧的籠統(tǒng)數(shù)據(jù)類型定義數(shù)據(jù)元素集合：描畫為數(shù)據(jù)元素集合：描畫為a0,a1,an-1，ai的數(shù)據(jù)類型為的數(shù)據(jù)類型為DataType。 關(guān)系：棧中數(shù)

4、據(jù)元素之間是線性關(guān)系。關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系。 根本操作：根本操作： (1)Initiate(S) 初始化堆棧初始化堆棧S (2)Push(S,x) 入棧入棧 (3)Pop(S,d) 出棧出棧 (4)GetTop(S) 取棧頂數(shù)據(jù)元素取棧頂數(shù)據(jù)元素 (5)NotEmpty(S) 堆棧堆棧S非空否非空否3.1.3 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn)順序堆棧類順序堆棧類 棧在計(jì)算機(jī)中主要有兩種根本的存儲(chǔ)構(gòu)造：棧在計(jì)算機(jī)中主要有兩種根本的存儲(chǔ)構(gòu)造： 順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造。順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造。 順序存儲(chǔ)的棧為順序棧；順序存儲(chǔ)的棧為順序棧； 鏈?zhǔn)酱鎯?chǔ)的棧為鏈棧。鏈?zhǔn)酱鎯?chǔ)的棧為鏈棧。1.

5、1.順序堆棧的存儲(chǔ)構(gòu)造順序堆棧的存儲(chǔ)構(gòu)造 順序棧是用順序存儲(chǔ)構(gòu)造實(shí)現(xiàn)的棧，即利用順序棧是用順序存儲(chǔ)構(gòu)造實(shí)現(xiàn)的棧，即利用一組地址延續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)囊唤M地址延續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)由于棧的操作的特殊性，還必需附數(shù)據(jù)元素，同時(shí)由于棧的操作的特殊性，還必需附設(shè)一個(gè)位置指針設(shè)一個(gè)位置指針top棧頂指針來動(dòng)態(tài)地指示棧棧頂指針來動(dòng)態(tài)地指示棧頂元素在順序棧中的位置。通常以頂元素在順序棧中的位置。通常以top = 0表示空棧。表示空棧。其構(gòu)造如下圖：其構(gòu)造如下圖：a0 a1 a2 a3 a4stack棧底棧頂MaxStackSize-1012345=top 其中，其中

6、，a0, a1, a2, a3, a4表示順序堆棧中已存儲(chǔ)的數(shù)據(jù)元表示順序堆棧中已存儲(chǔ)的數(shù)據(jù)元素，素，stack表示存放數(shù)據(jù)元素的數(shù)組，表示存放數(shù)據(jù)元素的數(shù)組，MaxStackSize-1表示最表示最大存儲(chǔ)單元個(gè)數(shù)，大存儲(chǔ)單元個(gè)數(shù)，top表示當(dāng)前棧頂存儲(chǔ)下標(biāo)。表示當(dāng)前棧頂存儲(chǔ)下標(biāo)。class SeqStackprivate:DataType dataMaxStackSize; /順序堆棧數(shù)組順序堆棧數(shù)組int top; /棧頂位置指示器棧頂位置指示器 public:SeqStack(void) top=0; /構(gòu)造函數(shù)構(gòu)造函數(shù)SeqStack(void) /析構(gòu)函數(shù)析構(gòu)函數(shù)void Push(

7、const DataType item); /入棧入棧DataType Pop(void); /出棧出棧DataType GetTop(void)const; /取棧頂數(shù)據(jù)元素取棧頂數(shù)據(jù)元素int NotEmpty(void)const /堆棧非空否堆棧非空否return(top!=0);2.2.順序堆棧類的定義和實(shí)現(xiàn)順序堆棧類的定義和實(shí)現(xiàn)void SeqStack:Push(const DataType item) /入棧入棧/把元素把元素item入棧入棧;堆棧滿時(shí)出錯(cuò)退出堆棧滿時(shí)出錯(cuò)退出if(top=MaxStackSize)cout堆棧已滿堆棧已滿!endl;exit(0);datato

8、p=item; /先存儲(chǔ)先存儲(chǔ)itemtop+; /然后然后top加加1DataType SeqStack:Pop() /出棧出棧/出棧并前往棧頂元素出棧并前往棧頂元素;堆?？諘r(shí)出錯(cuò)退出堆棧空時(shí)出錯(cuò)退出if(top=0)cout堆棧已空堆棧已空!endl;exit(0);top-; /top先減先減1return datatop; /然后取元素前往然后取元素前往DataType SeqStack:GetTop(void)const /取棧頂數(shù)據(jù)元素取棧頂數(shù)據(jù)元素/取當(dāng)前棧頂數(shù)據(jù)元素并前往取當(dāng)前棧頂數(shù)據(jù)元素并前往if(top=0)cout堆?？斩褩？?endl;exit(0);return da

9、tatop-1; /前往當(dāng)前棧頂元素前往當(dāng)前棧頂元素測試主程序如下：測試主程序如下：#include #include const int MaxStackSize=100; /定義問題要求的元素?cái)?shù)目的最大值定義問題要求的元素?cái)?shù)目的最大值typedef int DataType; /定義詳細(xì)問題元素的數(shù)據(jù)類型定義詳細(xì)問題元素的數(shù)據(jù)類型#include seqstack.h3. 3. 順序堆棧類的測試順序堆棧類的測試void main(void) SeqStack myStack; /構(gòu)造函數(shù)無參數(shù)時(shí)，定義的對(duì)象后不帶括號(hào)構(gòu)造函數(shù)無參數(shù)時(shí)，定義的對(duì)象后不帶括號(hào)DataType test=1,3,

10、5,7,9;int n=5;for(int i=0;in;i+)myStack.Push(testi);while(myStack.NotEmpty()coutmyStack.Pop() ;程序運(yùn)轉(zhuǎn)輸出結(jié)果為：程序運(yùn)轉(zhuǎn)輸出結(jié)果為：9 7 5 3 13.1.4 3.1.4 鏈?zhǔn)蕉褩ｎ愭準(zhǔn)蕉褩ｎ?.1.鏈?zhǔn)蕉褩ｆ準(zhǔn)蕉褩?鏈?zhǔn)酱鎯?chǔ)構(gòu)造的堆棧。鏈?zhǔn)酱鎯?chǔ)構(gòu)造的堆棧。2.2.鏈?zhǔn)綏５拇鎯?chǔ)構(gòu)造鏈?zhǔn)綏５拇鎯?chǔ)構(gòu)造 它是以頭指針為棧頂，在頭指針處插入或刪除，其構(gòu)造它是以頭指針為棧頂，在頭指針處插入或刪除，其構(gòu)造如下圖：如下圖：頭結(jié)點(diǎn)an-1an-2a0h棧底棧頂鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)

11、成：datadata域和域和nextnext域，其結(jié)點(diǎn)域，其結(jié)點(diǎn)類和類定義分別如下：類和類定義分別如下：template class LinStack; /前視定義，否那么友元無法定義前視定義，否那么友元無法定義/結(jié)點(diǎn)類結(jié)點(diǎn)類 template /模板類型為模板類型為T class StackNode friend class LinStack ; /定義類定義類LinStack為友元為友元 private: T data; /數(shù)據(jù)元素?cái)?shù)據(jù)元素 StackNode *next; /指針指針 public:/構(gòu)造函數(shù)構(gòu)造函數(shù)1，用語構(gòu)造頭結(jié)點(diǎn)，用語構(gòu)造頭結(jié)點(diǎn)StackNode(StackNode

12、 *ptrNext=NULL) next=ptrNext;/構(gòu)造函數(shù)構(gòu)造函數(shù)2，用于構(gòu)造其他結(jié)點(diǎn)，用于構(gòu)造其他結(jié)點(diǎn)StackNode(const T& item,StackNode *ptrNext=NULL) data=item;next=ptrNext;StackNode();/鏈?zhǔn)蕉褩ｎ惖亩x鏈?zhǔn)蕉褩ｎ惖亩xtemplate class LinStack private: StackNode *head; /頭指針頭指針 int size; public: /數(shù)據(jù)元素個(gè)數(shù)數(shù)據(jù)元素個(gè)數(shù)public: LinStack(void); /構(gòu)造函數(shù)構(gòu)造函數(shù)LinStack(void) ;

13、 /析構(gòu)函數(shù)析構(gòu)函數(shù)void Push(const T& item); /入棧入棧T Pop(void); /出棧出棧T GetTop(void) const; /取棧頂元素取棧頂元素int NotEmpty(void) const; /堆棧非空否堆棧非空否;template LinStack :LinStack() /構(gòu)造函數(shù)構(gòu)造函數(shù) head=new StackNode ; /頭指針指向頭結(jié)點(diǎn)頭指針指向頭結(jié)點(diǎn) size=0; /size的初值為的初值為0 template LinStack :LinStack(void) /析構(gòu)函數(shù)析構(gòu)函數(shù)/釋放一切動(dòng)態(tài)懇求的結(jié)點(diǎn)空間釋放一切動(dòng)態(tài)懇

14、求的結(jié)點(diǎn)空間 StackNode *p,*q;p=head; /p指向頭結(jié)點(diǎn)指向頭結(jié)點(diǎn)while(p!=NULL) /循環(huán)釋放結(jié)點(diǎn)空間循環(huán)釋放結(jié)點(diǎn)空間 q=p; p=p-next; delete q;template int LinStack :NotEmpty(void) const /堆棧非空否堆棧非空否if(size!=0) return 1;else return 0;template void LinStack :Push(const T& item) /入棧入棧/新結(jié)點(diǎn)新結(jié)點(diǎn)newNode的的data域值為域值為item,next域值為域值為head-nextStackNo

15、de *newNode=new StackNode (item,head-next);head-next=newNode; /新結(jié)點(diǎn)插入棧頂新結(jié)點(diǎn)插入棧頂size+; /元素個(gè)數(shù)加元素個(gè)數(shù)加1template T LinStack :Pop(void) /出棧出棧 if(size=0) cout堆棧已空無元素可刪堆棧已空無元素可刪!endl; exit(0); StackNode *p=head-next; /p指向棧頂元素結(jié)點(diǎn)指向棧頂元素結(jié)點(diǎn)T data=p-data;head-next=head-next-next; /原棧頂元素結(jié)點(diǎn)脫鏈原棧頂元素結(jié)點(diǎn)脫鏈delete p; /釋放原棧頂結(jié)

16、點(diǎn)空間釋放原棧頂結(jié)點(diǎn)空間size-; /結(jié)點(diǎn)個(gè)數(shù)減結(jié)點(diǎn)個(gè)數(shù)減1return data; /前往原棧頂結(jié)點(diǎn)的前往原棧頂結(jié)點(diǎn)的data域值域值template T LinStack :GetTop(void) const /取棧頂元素取棧頂元素return head-next-data;闡明：闡明：1)在鏈棧中的頭結(jié)點(diǎn)對(duì)操作的實(shí)現(xiàn)影響不大，棧頂表頭在鏈棧中的頭結(jié)點(diǎn)對(duì)操作的實(shí)現(xiàn)影響不大，棧頂表頭操作頻繁，可不設(shè)頭結(jié)點(diǎn)鏈棧。操作頻繁，可不設(shè)頭結(jié)點(diǎn)鏈棧。2)普通不會(huì)出現(xiàn)棧滿情況；除非沒有空間導(dǎo)致普通不會(huì)出現(xiàn)棧滿情況；除非沒有空間導(dǎo)致malloc分配分配失敗。失敗。3)鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c

17、刪除操作，修鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修正指針即可完成。正指針即可完成。4)采用鏈棧存儲(chǔ)方式的優(yōu)點(diǎn)是，可使多個(gè)棧共享空間；當(dāng)采用鏈棧存儲(chǔ)方式的優(yōu)點(diǎn)是，可使多個(gè)棧共享空間；當(dāng)棧中元素個(gè)數(shù)變化較大，且存在多個(gè)棧的情況下，鏈棧中元素個(gè)數(shù)變化較大，且存在多個(gè)棧的情況下，鏈棧是棧的首選存儲(chǔ)方式。棧是棧的首選存儲(chǔ)方式。3.2 3.2 堆棧運(yùn)用堆棧運(yùn)用1、括號(hào)匹配問題、括號(hào)匹配問題例：假設(shè)一個(gè)算法表達(dá)式中包含圓括號(hào)、方括號(hào)和花例：假設(shè)一個(gè)算法表達(dá)式中包含圓括號(hào)、方括號(hào)和花括號(hào)三種類型的括號(hào)，編寫一個(gè)判別表達(dá)式中括號(hào)能括號(hào)三種類型的括號(hào)，編寫一個(gè)判別表達(dá)式中括號(hào)能否正確配對(duì)的函數(shù)。否正確配

18、對(duì)的函數(shù)。設(shè)計(jì)思緒：用棧暫存左括號(hào)設(shè)計(jì)思緒：用棧暫存左括號(hào)void ExpIsCorrect(char exp, int n)/判別有判別有n個(gè)字符的字符串個(gè)字符的字符串exp左右括號(hào)能否配對(duì)正確左右括號(hào)能否配對(duì)正確 SeqStack myStack; /定義順序堆棧類對(duì)象定義順序堆棧類對(duì)象myStack int i;for(i=0;in;i+)if(expi=()|(expi= )|(expi= )myStack.Push(expi); /入棧入棧else if(expi = ) &myStack.NotEmpty()&myStack.GetTop()=()myStack.P

19、op(); /出棧出棧else if(expi=)&myStack.NotEmpty()&myStack.GetTop()!=() cout左、右括號(hào)配對(duì)次序不正確左、右括號(hào)配對(duì)次序不正確!endl; return;else if(expi = &myStack.NotEmpty()&myStack.GetTop()=)myStack.Pop(); /出棧出棧else if(expi=&myStack.NotEmpty()&myStack.GetTop()!=)cout左、右括號(hào)配對(duì)次序不正確左、右括號(hào)配對(duì)次序不正確!endl;return;el

20、se if(expi = &myStack.NotEmpty()&myStack.GetTop()=)myStack.Pop(); /出棧出棧else if(expi=&myStack.NotEmpty()&myStack.GetTop()!=) cout左、右括號(hào)配對(duì)次序不正確左、右括號(hào)配對(duì)次序不正確!endl; return;else if(expi=)|(expi=)|(expi=)&!myStack.NotEmpty()cout右括號(hào)多于左括號(hào)右括號(hào)多于左括號(hào)!endl;return;if(myStack.NotEmpty()cout左括號(hào)多于右

21、括號(hào)左括號(hào)多于右括號(hào)!endl;elsecout左、右括號(hào)匹配正確左、右括號(hào)匹配正確!endl;2、表達(dá)式計(jì)算問題、表達(dá)式計(jì)算問題 表達(dá)式計(jì)算是編譯系統(tǒng)中的根本問題，其實(shí)現(xiàn)方法是堆表達(dá)式計(jì)算是編譯系統(tǒng)中的根本問題，其實(shí)現(xiàn)方法是堆棧的一個(gè)典型運(yùn)用。在編譯系統(tǒng)中，要把便于人了解的表達(dá)棧的一個(gè)典型運(yùn)用。在編譯系統(tǒng)中，要把便于人了解的表達(dá)式翻譯成能正確求值的機(jī)器指令序列，通常需求先把表達(dá)式式翻譯成能正確求值的機(jī)器指令序列，通常需求先把表達(dá)式變換成機(jī)器便于了解的方式，這就要變換表達(dá)式的表示序列。變換成機(jī)器便于了解的方式，這就要變換表達(dá)式的表示序列。假設(shè)計(jì)算機(jī)高級(jí)言語中的一個(gè)算術(shù)表達(dá)式為假設(shè)計(jì)算機(jī)高級(jí)言語

22、中的一個(gè)算術(shù)表達(dá)式為 A+(B-C/D)A+(B-C/D)* *E E這種表達(dá)式稱為中綴表達(dá)式，寫成滿足四那么運(yùn)算規(guī)那么的相應(yīng)這種表達(dá)式稱為中綴表達(dá)式，寫成滿足四那么運(yùn)算規(guī)那么的相應(yīng)的后綴表達(dá)式即為的后綴表達(dá)式即為 ABCD/-E*+ 表達(dá)式的三種標(biāo)識(shí)方法：設(shè)設(shè) Exp = S1 + OP + S2那么稱那么稱 OP + S1 + S2 為前綴表示法為前綴表示法 S1 + OP + S2 為中綴表示法 S1 + S2 + OP 為后綴表示法 編譯系統(tǒng)中表達(dá)式的計(jì)算分為兩個(gè)步驟：編譯系統(tǒng)中表達(dá)式的計(jì)算分為兩個(gè)步驟： 1 1把中綴表達(dá)式變換成相應(yīng)的后綴表達(dá)式；把中綴表達(dá)式變換成相應(yīng)的后綴表達(dá)式；

23、2 2根據(jù)后綴表達(dá)式計(jì)算表達(dá)式的值。根據(jù)后綴表達(dá)式計(jì)算表達(dá)式的值。后綴表達(dá)式的兩個(gè)特點(diǎn)：后綴表達(dá)式的兩個(gè)特點(diǎn)： P72 6P72 6、7 7行行中綴表達(dá)式變換為后綴表達(dá)式的算法步驟可以總結(jié)為：中綴表達(dá)式變換為后綴表達(dá)式的算法步驟可以總結(jié)為： (1) (1)設(shè)置一個(gè)堆棧，初始時(shí)將棧頂元素置為設(shè)置一個(gè)堆棧，初始時(shí)將棧頂元素置為“。 (2) (2)順序讀入中綴表達(dá)式，當(dāng)讀到的單詞為操作數(shù)時(shí)就將其輸出，順序讀入中綴表達(dá)式，當(dāng)讀到的單詞為操作數(shù)時(shí)就將其輸出，并接著讀下一個(gè)單詞。并接著讀下一個(gè)單詞。 (3) (3)令令x1x1為當(dāng)前棧頂運(yùn)算符的變量，為當(dāng)前棧頂運(yùn)算符的變量，x2x2為當(dāng)前掃描讀到運(yùn)算符的為

24、當(dāng)前掃描讀到運(yùn)算符的變量，當(dāng)順序從中綴表達(dá)式中讀入的單詞為運(yùn)算符時(shí)就賦予變量，當(dāng)順序從中綴表達(dá)式中讀入的單詞為運(yùn)算符時(shí)就賦予x2x2，然，然后比較后比較x1x1的優(yōu)先級(jí)與的優(yōu)先級(jí)與x2x2的優(yōu)先級(jí)。的優(yōu)先級(jí)。x1x2,x2x1x2,x1x1x2,x1退棧，退棧，寫入后綴表達(dá)式中；寫入后綴表達(dá)式中；x1=x2=#,x1=x2=#,算法終了。算法終了。 利用堆棧計(jì)算后綴表達(dá)式值的函數(shù)編寫如下：利用堆棧計(jì)算后綴表達(dá)式值的函數(shù)編寫如下：void PostExp(LinStack &s)char ch; /ch為為char類型變量類型變量T x,x1,x2;coutch&ch!=#) /

25、循環(huán)直到輸入為循環(huán)直到輸入為#if(isdigit(ch) /ch為數(shù)字類型為數(shù)字類型 cin.putback(ch); /回退一位回退一位cinx; /按數(shù)值類型重新輸入按數(shù)值類型重新輸入s.Push(x); /x入棧入棧elsex2=s.Pop(); /退棧得操作數(shù)退棧得操作數(shù)x1=s.Pop(); /退棧得被操作數(shù)退棧得被操作數(shù)switch(ch)case+:x1+=x2;break; case-:x1-=x2;break; case*:x1*=x2;break; case/:if(x2=0.0)cout除數(shù)為除數(shù)為0錯(cuò)錯(cuò)!;exit(0);else x1/=x2; break; s.P

26、ush(x1); /運(yùn)算結(jié)果入棧運(yùn)算結(jié)果入棧 cout后綴表達(dá)式計(jì)算結(jié)果為后綴表達(dá)式計(jì)算結(jié)果為:s.Pop()endl;void main() LinStack s; PostExp(s);3.3 3.3 隊(duì)隊(duì) 列列1、隊(duì)列的根本概念、隊(duì)列的根本概念(1)(1)定義定義: :只能在表的一端進(jìn)展插入操作，在表的另一端進(jìn)展只能在表的一端進(jìn)展插入操作，在表的另一端進(jìn)展刪除操作的線性表。一個(gè)隊(duì)列的表示圖如下：刪除操作的線性表。一個(gè)隊(duì)列的表示圖如下：隊(duì)列的特點(diǎn)：先進(jìn)先出隊(duì)列的特點(diǎn)：先進(jìn)先出FIFO隊(duì)列中允許進(jìn)展插入操作的一端稱為隊(duì)尾；隊(duì)列中允許進(jìn)展插入操作的一端稱為隊(duì)尾； 允許進(jìn)展刪除操作的一端稱為隊(duì)頭

27、。允許進(jìn)展刪除操作的一端稱為隊(duì)頭。隊(duì)頭和隊(duì)尾分別設(shè)定隊(duì)頭指示器和隊(duì)尾指示器。隊(duì)頭和隊(duì)尾分別設(shè)定隊(duì)頭指示器和隊(duì)尾指示器。隊(duì)列的插入操作通常稱為入隊(duì)列；隊(duì)列的插入操作通常稱為入隊(duì)列；隊(duì)列的刪除操作通常稱做出隊(duì)列。隊(duì)列的刪除操作通常稱做出隊(duì)列。隊(duì)尾插隊(duì)尾插入入隊(duì)頭刪隊(duì)頭刪除除a0a1a2an-1隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾2、隊(duì)列籠統(tǒng)數(shù)據(jù)類型、隊(duì)列籠統(tǒng)數(shù)據(jù)類型數(shù)據(jù)集合數(shù)據(jù)集合:a0,a1,an-1，ai的數(shù)據(jù)類型為的數(shù)據(jù)類型為DataType。操作集合：操作集合：(1)Initiate(Q) 初始化隊(duì)列初始化隊(duì)列Q (2)Append(Q,x) 入隊(duì)列入隊(duì)列 (3)Delete(Q) 出隊(duì)列出隊(duì)列 (4)Get

28、Front(Q) 取隊(duì)頭數(shù)據(jù)元素取隊(duì)頭數(shù)據(jù)元素 (5)NotEmpty(Q) 隊(duì)列隊(duì)列Q非空否非空否3 3、順序隊(duì)列、順序隊(duì)列(1)(1)順序隊(duì)列順序隊(duì)列 順序存儲(chǔ)構(gòu)造的隊(duì)列。順序存儲(chǔ)構(gòu)造的隊(duì)列。(2)(2)順序隊(duì)列的存儲(chǔ)構(gòu)造順序隊(duì)列的存儲(chǔ)構(gòu)造 以下圖是一個(gè)有以下圖是一個(gè)有6 6個(gè)存儲(chǔ)空間的順序隊(duì)列的動(dòng)態(tài)表示圖個(gè)存儲(chǔ)空間的順序隊(duì)列的動(dòng)態(tài)表示圖(a)空隊(duì)列空隊(duì)列front rear=012345CBA(b)入隊(duì)列入隊(duì)列A、B、C后的形狀后的形狀front =012345C(c)出隊(duì)列出隊(duì)列A、B后的形狀后的形狀front=012345rear =EDC(d)入隊(duì)列入隊(duì)列D、E后的形狀后的形狀fr

29、ont=012345rear =rear =(3)(3)順序隊(duì)列的順序隊(duì)列的“假溢出問題假溢出問題假溢出假溢出順序隊(duì)列因多次入隊(duì)列和出隊(duì)列操作后出現(xiàn)的有順序隊(duì)列因多次入隊(duì)列和出隊(duì)列操作后出現(xiàn)的有存儲(chǔ)空間但不能進(jìn)展入隊(duì)列操作的溢出。存儲(chǔ)空間但不能進(jìn)展入隊(duì)列操作的溢出。如何處理順序隊(duì)列的假溢出問題？如何處理順序隊(duì)列的假溢出問題？可采取四種方法：可采取四種方法：1)1)采用循環(huán)隊(duì)列；采用循環(huán)隊(duì)列； 2) 2)按最大能夠的進(jìn)隊(duì)操作次數(shù)設(shè)置順序隊(duì)列的最大按最大能夠的進(jìn)隊(duì)操作次數(shù)設(shè)置順序隊(duì)列的最大元素個(gè)數(shù)；元素個(gè)數(shù)； 3) 3)修正出隊(duì)算法，使每次出隊(duì)列后都把隊(duì)列中剩余修正出隊(duì)算法，使每次出隊(duì)列后都把隊(duì)列

30、中剩余數(shù)據(jù)元素向隊(duì)頭方向挪動(dòng)一個(gè)位置；數(shù)據(jù)元素向隊(duì)頭方向挪動(dòng)一個(gè)位置；) )修正入隊(duì)算法，添加判別條件，當(dāng)假溢出時(shí)，把修正入隊(duì)算法，添加判別條件，當(dāng)假溢出時(shí)，把隊(duì)列中的數(shù)據(jù)元素向隊(duì)頭挪動(dòng)，然后方完成入隊(duì)操隊(duì)列中的數(shù)據(jù)元素向隊(duì)頭挪動(dòng)，然后方完成入隊(duì)操作。作。(4)(4)順序循環(huán)隊(duì)列的根本原理順序循環(huán)隊(duì)列的根本原理 把順序隊(duì)列所運(yùn)用的存儲(chǔ)空間構(gòu)呵斥一個(gè)邏輯上首尾相連把順序隊(duì)列所運(yùn)用的存儲(chǔ)空間構(gòu)呵斥一個(gè)邏輯上首尾相連的循環(huán)隊(duì)列。當(dāng)?shù)难h(huán)隊(duì)列。當(dāng)rearrear和和frontfront到達(dá)到達(dá)MaxQueueSize-1MaxQueueSize-1后，再前后，再前進(jìn)一個(gè)位置就自動(dòng)到。進(jìn)一個(gè)位置就自動(dòng)到

31、。a3a2a1frontrear 0 1 2 3 . .N-1a3a2a10123N-1rearfront(5)順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判別問題見順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判別問題見P77圖圖3-91 14 40 02 23 35 5frontrear(a)(a)入隊(duì)前入隊(duì)前空隊(duì)列空隊(duì)列1 14 40 02 23 35 5e6e6e7e7e8e8e4e4e3e3e5e5frontrear(b) (b) 隊(duì)列滿隊(duì)列滿時(shí)時(shí)1 14 40 02 23 35 5e4e4e3e3e5e5frontrear(c) (c) 普通情況普通情況思索出對(duì)后思索出對(duì)后情況情況新問題：在循環(huán)隊(duì)列中，空隊(duì)特征是新問題：在

32、循環(huán)隊(duì)列中，空隊(duì)特征是front=rear；隊(duì)；隊(duì)滿時(shí)也會(huì)有滿時(shí)也會(huì)有front=rear；判決條件將出現(xiàn)二義性??；判決條件將出現(xiàn)二義性！處理方案有三：處理方案有三：運(yùn)用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)即隊(duì)列長運(yùn)用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)即隊(duì)列長度；度；判隊(duì)滿：判隊(duì)滿：count0 & rear=front 判隊(duì)空：判隊(duì)空：count=0加設(shè)標(biāo)志位，出隊(duì)時(shí)置加設(shè)標(biāo)志位，出隊(duì)時(shí)置,入隊(duì)時(shí)置入隊(duì)時(shí)置,那么可識(shí)別那么可識(shí)別當(dāng)前當(dāng)前front=rear屬于何種情況屬于何種情況判隊(duì)滿：判隊(duì)滿：tag=1 & rear=front 判隊(duì)空：判隊(duì)空：tag=0 & rear=fron

33、t 少用一個(gè)存儲(chǔ)單元少用一個(gè)存儲(chǔ)單元判隊(duì)滿：判隊(duì)滿： front=(rear+1)%MaxQueueSize 判隊(duì)空：判隊(duì)空： rear=front4 4、順序循環(huán)隊(duì)列類、順序循環(huán)隊(duì)列類采用設(shè)置計(jì)數(shù)器方法來判別隊(duì)空形狀和隊(duì)滿形狀，類定義如下采用設(shè)置計(jì)數(shù)器方法來判別隊(duì)空形狀和隊(duì)滿形狀，類定義如下: :class SeqQueue class SeqQueue private: private: DataType dataMaxQueueSize; /DataType dataMaxQueueSize; /順序隊(duì)列數(shù)組順序隊(duì)列數(shù)組 int front; /int front; /隊(duì)頭指示器隊(duì)頭指示

34、器 int rear; /int rear; /隊(duì)尾指示器隊(duì)尾指示器 int count; /int count; /元素個(gè)數(shù)計(jì)數(shù)器元素個(gè)數(shù)計(jì)數(shù)器 public: public: SeqQueue(void) /SeqQueue(void) /構(gòu)造函數(shù)構(gòu)造函數(shù)front=rear=0;count=0; front=rear=0;count=0; SeqQueue(void) /SeqQueue(void) /析構(gòu)函數(shù)析構(gòu)函數(shù) void Append(const DataType& item); /void Append(const DataType& item); /入隊(duì)列入隊(duì)

35、列 DataType Delete(void); /DataType Delete(void); /出隊(duì)列出隊(duì)列 DataType GetFront(void)const; /DataType GetFront(void)const; /取隊(duì)頭數(shù)據(jù)元素取隊(duì)頭數(shù)據(jù)元素 int NotEmpty(void)const /int NotEmpty(void)const /非空否非空否 return count!=0;return count!=0;void SeqQueue:Append(const DataType& item) /入隊(duì)列入隊(duì)列/把數(shù)據(jù)元素把數(shù)據(jù)元素item插入隊(duì)列作為當(dāng)前

36、的新隊(duì)尾插入隊(duì)列作為當(dāng)前的新隊(duì)尾if(count0&front=rear)cout隊(duì)列已滿隊(duì)列已滿!endl;exit(0);datarear=item; /把元素把元素item加在隊(duì)尾加在隊(duì)尾rear=(rear+1) % MaxQueueSize; /隊(duì)尾指示器加隊(duì)尾指示器加1cout+; /計(jì)數(shù)器加計(jì)數(shù)器加1DataType SeqQueue:Delete(void) /出隊(duì)列出隊(duì)列/把隊(duì)頭元素出隊(duì)列，出隊(duì)列元素由函數(shù)前往把隊(duì)頭元素出隊(duì)列，出隊(duì)列元素由函數(shù)前往if(count=0)cout隊(duì)列已空隊(duì)列已空!endl;exit(0);DataType temp=datafront;

37、 /保管原隊(duì)頭元素保管原隊(duì)頭元素front=(front+1) % MaxQueueSize; /隊(duì)頭指示器加隊(duì)頭指示器加1count-; /計(jì)數(shù)器減計(jì)數(shù)器減1return temp; /前往原隊(duì)頭元素前往原隊(duì)頭元素DataType SeqQueue:GetFront(void)const /取隊(duì)頭數(shù)據(jù)元素取隊(duì)頭數(shù)據(jù)元素/取隊(duì)頭元素并由函數(shù)前往取隊(duì)頭元素并由函數(shù)前往if(count=0)cout隊(duì)列已空隊(duì)列已空!endl;exit(0);return dataFront; /前往隊(duì)頭元素前往隊(duì)頭元素5 5、鏈?zhǔn)疥?duì)列類、鏈?zhǔn)疥?duì)列類(1)(1)鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列 鏈?zhǔn)酱鎯?chǔ)構(gòu)造的隊(duì)列。鏈?zhǔn)酱鎯?chǔ)構(gòu)造的隊(duì)

38、列。(2)(2)鏈?zhǔn)疥?duì)列的存儲(chǔ)構(gòu)造鏈?zhǔn)疥?duì)列的存儲(chǔ)構(gòu)造 鏈?zhǔn)疥?duì)列的隊(duì)頭指針指向隊(duì)列的當(dāng)前隊(duì)頭結(jié)鏈?zhǔn)疥?duì)列的隊(duì)頭指針指向隊(duì)列的當(dāng)前隊(duì)頭結(jié)點(diǎn)點(diǎn); ;隊(duì)尾指針指在隊(duì)列的當(dāng)前隊(duì)尾結(jié)點(diǎn)隊(duì)尾指針指在隊(duì)列的當(dāng)前隊(duì)尾結(jié)點(diǎn), ,以下圖以下圖是一個(gè)不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列的構(gòu)造：是一個(gè)不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列的構(gòu)造：a0a1an-1an-1frontrear(3)(3)鏈?zhǔn)疥?duì)列類的定義及實(shí)現(xiàn)鏈?zhǔn)疥?duì)列類的定義及實(shí)現(xiàn)結(jié)點(diǎn)類的定義和實(shí)現(xiàn)如下：結(jié)點(diǎn)類的定義和實(shí)現(xiàn)如下：template template class LinQueue;/class LinQueue;/前視定義，否那么友元無法定義前視定義，否那么友元無法定義templa

39、te template class QueueNodeclass QueueNode friend class LinQueue ; /friend class LinQueue ; /定義類定義類LinQueueLinQueue為友元為友元private: private: QueueNode QueueNode * *next; /next; /指針指針 T data; /T data; /數(shù)據(jù)元素?cái)?shù)據(jù)元素 public: public: / /構(gòu)造函數(shù)構(gòu)造函數(shù)QueueNode(const T& item,QueueNode QueueNode(const T& item

40、,QueueNode * *ptrNext=NULL)ptrNext=NULL):data(item),next(ptrNext):data(item),next(ptrNext)QueueNode(); /QueueNode(); /析構(gòu)函數(shù)析構(gòu)函數(shù);為了方便設(shè)計(jì)，添加了一個(gè)為了方便設(shè)計(jì)，添加了一個(gè)countcount域用來計(jì)算當(dāng)前的元素個(gè)數(shù)域用來計(jì)算當(dāng)前的元素個(gè)數(shù) 鏈?zhǔn)疥?duì)列類的定義如下：鏈?zhǔn)疥?duì)列類的定義如下：template template class LinQueue class LinQueue pprivate: pprivate: QueueNode QueueNode * *f

41、ront; /front; /隊(duì)頭指針隊(duì)頭指針QueueNode QueueNode * *rear; /rear; /隊(duì)尾指針隊(duì)尾指針 int count; /int count; /計(jì)數(shù)器計(jì)數(shù)器 public: public: LinQueue(void); /LinQueue(void); /構(gòu)造函數(shù)構(gòu)造函數(shù)LinQueue(void); /LinQueue(void); /析構(gòu)函數(shù)析構(gòu)函數(shù)void Append(const T& item); /void Append(const T& item); /入隊(duì)列入隊(duì)列 T Delete(void); /T Delete(v

42、oid); /出隊(duì)列出隊(duì)列 T GetFront(void)const; /T GetFront(void)const; /取隊(duì)頭數(shù)據(jù)元素取隊(duì)頭數(shù)據(jù)元素int NotEmpty(void)const /int NotEmpty(void)const /非空否非空否return count!=0;return count!=0;鏈?zhǔn)疥?duì)列類的實(shí)現(xiàn)如下：鏈?zhǔn)疥?duì)列類的實(shí)現(xiàn)如下：template LinQueue :LinQueue() /構(gòu)造函數(shù)構(gòu)造函數(shù)front=rear=NULL; /鏈?zhǔn)疥?duì)列無頭結(jié)點(diǎn)鏈?zhǔn)疥?duì)列無頭結(jié)點(diǎn)count=0; /count的初值為的初值為0template LinQueue

43、 :LinQueue(void) /析構(gòu)函數(shù)析構(gòu)函數(shù)QueueNode *p,*q;p=front; /p指向第一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)while(p!=NULL) /循環(huán)直至全部結(jié)點(diǎn)空間釋放循環(huán)直至全部結(jié)點(diǎn)空間釋放q=p;p=p-next;delete q;count=0; /置為初始化值置為初始化值0front=rear=NULL;template void LinQueue :Append(const T& item) /入隊(duì)列入隊(duì)列/把數(shù)據(jù)元素把數(shù)據(jù)元素item插入隊(duì)列作為新隊(duì)尾結(jié)點(diǎn)插入隊(duì)列作為新隊(duì)尾結(jié)點(diǎn)/構(gòu)造新結(jié)點(diǎn)構(gòu)造新結(jié)點(diǎn)newNode，newNode的的data域值為域值為

44、item，next域值為域值為NULLQueueNode *newNode=new QueueNode (item,NULL);if(rear!=NULL) rear-next=newNode; /新結(jié)點(diǎn)鏈入新結(jié)點(diǎn)鏈入rear=newNode; /隊(duì)尾指針指向新隊(duì)尾結(jié)點(diǎn)隊(duì)尾指針指向新隊(duì)尾結(jié)點(diǎn)/假設(shè)隊(duì)頭指針原先為空那么置為指向新結(jié)點(diǎn)假設(shè)隊(duì)頭指針原先為空那么置為指向新結(jié)點(diǎn)if(front=NULL) front=newNode;count+; /計(jì)數(shù)器加計(jì)數(shù)器加1template template T LinQueue :Delete(void) /T LinQueue :Delete(void)

45、 /出隊(duì)列出隊(duì)列 /把隊(duì)頭結(jié)點(diǎn)刪除并由函數(shù)前往把隊(duì)頭結(jié)點(diǎn)刪除并由函數(shù)前往 if(count=0) if(count=0) coutcout隊(duì)列已空隊(duì)列已空!endl; !endl; exit(0); exit(0); QueueNode QueueNode * *p=front-next; /pp=front-next; /p指向新的隊(duì)頭結(jié)點(diǎn)指向新的隊(duì)頭結(jié)點(diǎn)T data=front-data; /T data=front-data; /保管原隊(duì)頭結(jié)點(diǎn)的保管原隊(duì)頭結(jié)點(diǎn)的datadata域值域值delete front; /delete front; /釋放原隊(duì)頭結(jié)點(diǎn)空間釋放原隊(duì)頭結(jié)點(diǎn)空間fron

46、t=p; /frontfront=p; /front指向新的對(duì)頭結(jié)點(diǎn)指向新的對(duì)頭結(jié)點(diǎn)count-; /count-; /計(jì)數(shù)器減計(jì)數(shù)器減1 1return data; /return data; /前往原隊(duì)頭結(jié)點(diǎn)的前往原隊(duì)頭結(jié)點(diǎn)的datadata域值域值 template T LinQueue :GetFront(void)const /取隊(duì)頭數(shù)據(jù)元素取隊(duì)頭數(shù)據(jù)元素if(count=0)cout隊(duì)列已空隊(duì)列已空!data;6 6、隊(duì)列的運(yùn)用、隊(duì)列的運(yùn)用例：編寫判別一個(gè)字符序列能否是回文的函數(shù)。例：編寫判別一個(gè)字符序列能否是回文的函數(shù)。編程思想：編程思想：設(shè)字符數(shù)組設(shè)字符數(shù)組strstr中存放了

47、要判別的字符串。把字符數(shù)組中的中存放了要判別的字符串。把字符數(shù)組中的字符逐個(gè)分別存入隊(duì)列和堆棧，然后逐個(gè)出隊(duì)列和退棧并比較字符逐個(gè)分別存入隊(duì)列和堆棧，然后逐個(gè)出隊(duì)列和退棧并比較出隊(duì)列的字符和退棧的字符能否相等，假設(shè)全部相等那么該字出隊(duì)列的字符和退棧的字符能否相等，假設(shè)全部相等那么該字符序列是回文，否那么就不是回文。符序列是回文，否那么就不是回文。設(shè)計(jì)函數(shù)如下：設(shè)計(jì)函數(shù)如下：void HuiWen(char str) void HuiWen(char str) LinStack myStack; LinStack myStack; LinQueue myQueue; LinQueue myQue

48、ue; int n=strlen(str); /int n=strlen(str); /求字符串長度求字符串長度for(int i=0;in;i+) for(int i=0;in;i+) myQueue.Append(stri); myQueue.Append(stri); myStack.Push(stri); myStack.Push(stri); while(myQueue.NotEmpty()&myStack.NotEmpty() while(myQueue.NotEmpty()&myStack.NotEmpty() if(myQueue.Delete()!=mySta

49、ck.Pop() if(myQueue.Delete()!=myStack.Pop() cout cout不是回文不是回文!endl; !endl; return; return; coutcout是回文是回文!endl;!endl; 3.4 3.4 優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列、優(yōu)先級(jí)隊(duì)列帶有優(yōu)先級(jí)的隊(duì)列。、優(yōu)先級(jí)隊(duì)列帶有優(yōu)先級(jí)的隊(duì)列。、順序優(yōu)先級(jí)隊(duì)列用順序存儲(chǔ)構(gòu)造存儲(chǔ)的優(yōu)先級(jí)隊(duì)列。、順序優(yōu)先級(jí)隊(duì)列用順序存儲(chǔ)構(gòu)造存儲(chǔ)的優(yōu)先級(jí)隊(duì)列。、優(yōu)先級(jí)隊(duì)列和普通隊(duì)列的主要區(qū)別、優(yōu)先級(jí)隊(duì)列和普通隊(duì)列的主要區(qū)別優(yōu)先級(jí)隊(duì)列的出隊(duì)列操作不是把隊(duì)頭元素出隊(duì)列，而是把優(yōu)先級(jí)隊(duì)列的出隊(duì)列操作不是把隊(duì)頭元素出隊(duì)列，而是把隊(duì)列中優(yōu)先級(jí)最高的元素出隊(duì)列。隊(duì)列中優(yōu)先級(jí)最高的元素出隊(duì)列。它的數(shù)據(jù)元素定義為如下構(gòu)造體：它的數(shù)據(jù)元素定義為如下構(gòu)造體：struct DataType ElemType elem; /數(shù)據(jù)元素?cái)?shù)據(jù)元素int priority; /優(yōu)先級(jí)優(yōu)先級(jí);注：順序優(yōu)先級(jí)隊(duì)列除出隊(duì)列操作外的其他操作的實(shí)現(xiàn)方法與注：順序優(yōu)先級(jí)隊(duì)列除出隊(duì)列操作外的其他操作的實(shí)現(xiàn)方法與前邊討論的順序隊(duì)列操作的實(shí)現(xiàn)方法一樣。前邊討論的順序隊(duì)列操作的實(shí)現(xiàn)方法一樣。出隊(duì)列操作出隊(duì)列操作( (把優(yōu)先級(jí)最高的元素出隊(duì)列并由函數(shù)前