堆棧和隊列ppt課件

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

2、展插入、刪除通常將表中允許進(jìn)展插入、刪除操作的一端稱為棧頂操作的一端稱為棧頂 (Top)，表的另，表的另一端被稱為棧底一端被稱為棧底 (Bottom)。 當(dāng)棧中沒有元素時稱為空棧。棧當(dāng)棧中沒有元素時稱為空棧。棧的插入操作被籠統(tǒng)地稱為進(jìn)?；蛉霔＃牟迦氩僮鞅换\統(tǒng)地稱為進(jìn)?；蛉霔＃瑒h除操作稱為出?；蛲藯！Ｓ址Q為刪除操作稱為出?；蛲藯！Ｓ址Q為后進(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 利用一個堆棧，假設(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 棧的表示和實現(xiàn)棧的表示和實現(xiàn)順序堆棧類順序堆棧類 棧在計算機(jī)中主要有兩種根本的存儲構(gòu)造：棧在計算機(jī)中主要有兩種根本的存儲構(gòu)造： 順序存儲構(gòu)造和鏈?zhǔn)酱鎯?gòu)造。順序存儲構(gòu)造和鏈?zhǔn)酱鎯?gòu)造。 順序存儲的棧為順序棧；順序存儲的棧為順序棧； 鏈?zhǔn)酱鎯Φ臈殒湕！ｆ準(zhǔn)酱鎯Φ臈殒湕！?.

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

6、，a0, a1, a2, a3, a4表示順序堆棧中已存儲的數(shù)據(jù)元表示順序堆棧中已存儲的數(shù)據(jù)元素，素，stack表示存放數(shù)據(jù)元素的數(shù)組，表示存放數(shù)據(jù)元素的數(shù)組，MaxStackSize-1表示最表示最大存儲單元個數(shù)，大存儲單元個數(shù)，top表示當(dāng)前棧頂存儲下標(biāo)。表示當(dāng)前棧頂存儲下標(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.順序堆棧類的定義和實現(xiàn)順序堆棧類的定義和實現(xiàn)void SeqStack:Push(const DataType item) /入棧入棧/把元素把元素item入棧入棧;堆棧滿時出錯退出堆棧滿時出錯退出if(top=MaxStackSize)cout堆棧已滿堆棧已滿!endl;exit(0);datato

8、p=item; /先存儲先存儲itemtop+; /然后然后top加加1DataType SeqStack:Pop() /出棧出棧/出棧并前往棧頂元素出棧并前往棧頂元素;堆?？諘r出錯退出堆?？諘r出錯退出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; /定義問題要求的元素數(shù)目的最大值定義問題要求的元素數(shù)目的最大值typedef int DataType; /定義詳細(xì)問題元素的數(shù)據(jù)類型定義詳細(xì)問題元素的數(shù)據(jù)類型#include seqstack.h3. 3. 順序堆棧類的測試順序堆棧類的測試void main(void) SeqStack myStack; /構(gòu)造函數(shù)無參數(shù)時，定義的對象后不帶括號構(gòu)造函數(shù)無參數(shù)時，定義的對象后不帶括號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)酱鎯?gòu)造的堆棧。鏈?zhǔn)酱鎯?gòu)造的堆棧。2.2.鏈?zhǔn)綏５拇鎯?gòu)造鏈?zhǔn)綏５拇鎯?gòu)造 它是以頭指針為棧頂，在頭指針處插入或刪除，其構(gòu)造它是以頭指針為棧頂，在頭指針處插入或刪除，其構(gòu)造如下圖：如下圖：頭結(jié)點(diǎn)an-1an-2a0h棧底棧頂鏈棧中每個結(jié)點(diǎn)由兩個域構(gòu)成：鏈棧中每個結(jié)點(diǎn)由兩個域構(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ù)元素數(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ù)元素個數(shù)數(shù)據(jù)元素個數(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ù)/釋放一切動態(tài)懇求的結(jié)點(diǎn)空間釋放一切動態(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+; /元素個數(shù)加元素個數(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)個數(shù)減結(jié)點(diǎn)個數(shù)減1return data; /前往原棧頂結(jié)點(diǎn)的前往原棧頂結(jié)點(diǎn)的data域值域值template T LinStack :GetTop(void) const /取棧頂元素取棧頂元素return head-next-data;闡明：闡明：1)在鏈棧中的頭結(jié)點(diǎn)對操作的實現(xiàn)影響不大，棧頂表頭在鏈棧中的頭結(jié)點(diǎn)對操作的實現(xiàn)影響不大，棧頂表頭操作頻繁，可不設(shè)頭結(jié)點(diǎn)鏈棧。操作頻繁，可不設(shè)頭結(jié)點(diǎn)鏈棧。2)普通不會出現(xiàn)棧滿情況；除非沒有空間導(dǎo)致普通不會出現(xiàn)棧滿情況；除非沒有空間導(dǎo)致malloc分配分配失敗。失敗。3)鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c

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

18、對的函數(shù)。設(shè)計思緒：用棧暫存左括號設(shè)計思緒：用棧暫存左括號void ExpIsCorrect(char exp, int n)/判別有判別有n個字符的字符串個字符的字符串exp左右括號能否配對正確左右括號能否配對正確 SeqStack myStack; /定義順序堆棧類對象定義順序堆棧類對象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左、右括號配對次序不正確左、右括號配對次序不正確!endl; return;else if(expi = &myStack.NotEmpty()&myStack.GetTop()=)myStack.Pop(); /出棧出棧else if(expi=&myStack.NotEmpty()&myStack.GetTop()!=)cout左、右括號配對次序不正確左、右括號配對次序不正確!endl;return;el

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

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

22、中的一個算術(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è) Exp = S1 + OP + S2那么稱那么稱 OP + S1 + S2 為前綴表示法為前綴表示法 S1 + OP + S2 為中綴表示法 S1 + S2 + OP 為后綴表示法 編譯系統(tǒng)中表達(dá)式的計算分為兩個步驟：編譯系統(tǒng)中表達(dá)式的計算分為兩個步驟： 1 1把中綴表達(dá)式變換成相應(yīng)的后綴表達(dá)式；把中綴表達(dá)式變換成相應(yīng)的后綴表達(dá)式；

23、2 2根據(jù)后綴表達(dá)式計算表達(dá)式的值。根據(jù)后綴表達(dá)式計算表達(dá)式的值。后綴表達(dá)式的兩個特點(diǎn)：后綴表達(dá)式的兩個特點(diǎn)： P72 6P72 6、7 7行行中綴表達(dá)式變換為后綴表達(dá)式的算法步驟可以總結(jié)為：中綴表達(dá)式變換為后綴表達(dá)式的算法步驟可以總結(jié)為： (1) (1)設(shè)置一個堆棧，初始時將棧頂元素置為設(shè)置一個堆棧，初始時將棧頂元素置為“。 (2) (2)順序讀入中綴表達(dá)式，當(dāng)讀到的單詞為操作數(shù)時就將其輸出，順序讀入中綴表達(dá)式，當(dāng)讀到的單詞為操作數(shù)時就將其輸出，并接著讀下一個單詞。并接著讀下一個單詞。 (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)算符時就賦予變量，當(dāng)順序從中綴表達(dá)式中讀入的單詞為運(yùn)算符時就賦予x2x2，然，然后比較后比較x1x1的優(yōu)先級與的優(yōu)先級與x2x2的優(yōu)先級。的優(yōu)先級。x1x2,x2x1x2,x1x1x2,x1退棧，退棧，寫入后綴表達(dá)式中；寫入后綴表達(dá)式中；x1=x2=#,x1=x2=#,算法終了。算法終了。 利用堆棧計算后綴表達(dá)式值的函數(shù)編寫如下：利用堆棧計算后綴表達(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錯錯!;exit(0);else x1/=x2; break; s.P

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

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

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

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

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

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

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

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

34、器 int rear; /int rear; /隊尾指示器隊尾指示器 int count; /int count; /元素個數(shù)計數(shù)器元素個數(shù)計數(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); /入隊列入隊

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

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

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

38、列。(2)(2)鏈?zhǔn)疥犃械拇鎯?gòu)造鏈?zhǔn)疥犃械拇鎯?gòu)造 鏈?zhǔn)疥犃械年狀^指針指向隊列的當(dāng)前隊頭結(jié)鏈?zhǔn)疥犃械年狀^指針指向隊列的當(dāng)前隊頭結(jié)點(diǎn)點(diǎn); ;隊尾指針指在隊列的當(dāng)前隊尾結(jié)點(diǎn)隊尾指針指在隊列的當(dāng)前隊尾結(jié)點(diǎn), ,以下圖以下圖是一個不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥犃械臉?gòu)造：是一個不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥犃械臉?gòu)造：a0a1an-1an-1frontrear(3)(3)鏈?zhǔn)疥犃蓄惖亩x及實現(xiàn)鏈?zhǔn)疥犃蓄惖亩x及實現(xiàn)結(jié)點(diǎn)類的定義和實現(xiàn)如下：結(jié)點(diǎn)類的定義和實現(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ù)元素數(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è)計，添加了一個為了方便設(shè)計，添加了一個countcount域用來計算當(dāng)前的元素個數(shù)域用來計算當(dāng)前的元素個數(shù) 鏈?zhǔn)疥犃蓄惖亩x如下：鏈?zhǔn)疥犃蓄惖亩x如下：template template class LinQueue class LinQueue pprivate: pprivate: QueueNode QueueNode * *f

41、ront; /front; /隊頭指針隊頭指針QueueNode QueueNode * *rear; /rear; /隊尾指針隊尾指針 int count; /int count; /計數(shù)器計數(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); /入隊列入隊列 T Delete(void); /T Delete(v

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

43、 :LinQueue(void) /析構(gòu)函數(shù)析構(gòu)函數(shù)QueueNode *p,*q;p=front; /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;count=0; /置為初始化值置為初始化值0front=rear=NULL;template void LinQueue :Append(const T& item) /入隊列入隊列/把數(shù)據(jù)元素把數(shù)據(jù)元素item插入隊列作為新隊尾結(jié)點(diǎn)插入隊列作為新隊尾結(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; /隊尾指針指向新隊尾結(jié)點(diǎn)隊尾指針指向新隊尾結(jié)點(diǎn)/假設(shè)隊頭指針原先為空那么置為指向新結(jié)點(diǎn)假設(shè)隊頭指針原先為空那么置為指向新結(jié)點(diǎn)if(front=NULL) front=newNode;count+; /計數(shù)器加計數(shù)器加1template template T LinQueue :Delete(void) /T LinQueue :Delete(void)

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

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

47、要判別的字符串。把字符數(shù)組中的中存放了要判別的字符串。把字符數(shù)組中的字符逐個分別存入隊列和堆棧，然后逐個出隊列和退棧并比較字符逐個分別存入隊列和堆棧，然后逐個出隊列和退棧并比較出隊列的字符和退棧的字符能否相等，假設(shè)全部相等那么該字出隊列的字符和退棧的字符能否相等，假設(shè)全部相等那么該字符序列是回文，否那么就不是回文。符序列是回文，否那么就不是回文。設(shè)計函數(shù)如下：設(shè)計函數(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)先級隊列優(yōu)先級隊列、優(yōu)先級隊列帶有優(yōu)先級的隊列。、優(yōu)先級隊列帶有優(yōu)先級的隊列。、順序優(yōu)先級隊列用順序存儲構(gòu)造存儲的優(yōu)先級隊列。、順序優(yōu)先級隊列用順序存儲構(gòu)造存儲的優(yōu)先級隊列。、優(yōu)先級隊列和普通隊列的主要區(qū)別、優(yōu)先級隊列和普通隊列的主要區(qū)別優(yōu)先級隊列的出隊列操作不是把隊頭元素出隊列，而是把優(yōu)先級隊列的出隊列操作不是把隊頭元素出隊列，而是把隊列中優(yōu)先級最高的元素出隊列。隊列中優(yōu)先級最高的元素出隊列。它的數(shù)據(jù)元素定義為如下構(gòu)造體：它的數(shù)據(jù)元素定義為如下構(gòu)造體：struct DataType ElemType elem; /數(shù)據(jù)元素數(shù)據(jù)元素int priority; /優(yōu)先級優(yōu)先級;注：順序優(yōu)先級隊列除出隊列操作外的其他操作的實現(xiàn)方法與注：順序優(yōu)先級隊列除出隊列操作外的其他操作的實現(xiàn)方法與前邊討論的順序隊列操作的實現(xiàn)方法一樣。前邊討論的順序隊列操作的實現(xiàn)方法一樣。出隊列操作出隊列操作( (把優(yōu)先級最高的元素出隊列并由函數(shù)前