堆棧和隊列ppt課件

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

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

3、。因最新的元素，即最后進棧的元素。因此，棧又稱為后進先出的線性表。簡稱為此，棧又稱為后進先出的線性表。簡稱為LIFO表。表。如以下圖所示：如以下圖所示： 進棧、出棧圖例進棧、出棧圖例進棧進棧出棧出棧ana2a1進棧進棧出棧出棧棧頂棧頂棧底棧底 例3-1 利用一個堆棧，假設輸入系列由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。 關系：棧中數(shù)

4、據(jù)元素之間是線性關系。關系：棧中數(shù)據(jù)元素之間是線性關系。 根本操作：根本操作： (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)順序堆棧類順序堆棧類 棧在計算機中主要有兩種根本的存儲構造：棧在計算機中主要有兩種根本的存儲構造： 順序存儲構造和鏈式存儲構造。順序存儲構造和鏈式存儲構造。 順序存儲的棧為順序棧；順序存儲的棧為順序棧； 鏈式存儲的棧為鏈棧。鏈式存儲的棧為鏈棧。1.

5、1.順序堆棧的存儲構造順序堆棧的存儲構造 順序棧是用順序存儲構造實現(xiàn)的棧，即利用順序棧是用順序存儲構造實現(xiàn)的棧，即利用一組地址延續(xù)的存儲單元依次存放自棧底到棧頂?shù)囊唤M地址延續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時由于棧的操作的特殊性，還必需附數(shù)據(jù)元素，同時由于棧的操作的特殊性，還必需附設一個位置指針設一個位置指針top棧頂指針來動態(tài)地指示棧棧頂指針來動態(tài)地指示棧頂元素在順序棧中的位置。通常以頂元素在順序棧中的位置。通常以top = 0表示空棧。表示空棧。其構造如下圖：其構造如下圖：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表示當前棧頂存儲下標。表示當前棧頂存儲下標。class SeqStackprivate:DataType dataMaxStackSize; /順序堆棧數(shù)組順序堆棧數(shù)組int top; /棧頂位置指示器棧頂位置指示器 public:SeqStack(void) top=0; /構造函數(shù)構造函數(shù)SeqStack(void) /析構函數(shù)析構函數(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ù)元素/取當前棧頂數(shù)據(jù)元素并前往取當前棧頂數(shù)據(jù)元素并前往if(top=0)cout堆?？斩褩？?endl;exit(0);return da

9、tatop-1; /前往當前棧頂元素前往當前棧頂元素測試主程序如下：測試主程序如下：#include #include const int MaxStackSize=100; /定義問題要求的元素數(shù)目的最大值定義問題要求的元素數(shù)目的最大值typedef int DataType; /定義詳細問題元素的數(shù)據(jù)類型定義詳細問題元素的數(shù)據(jù)類型#include seqstack.h3. 3. 順序堆棧類的測試順序堆棧類的測試void main(void) SeqStack myStack; /構造函數(shù)無參數(shù)時，定義的對象后不帶括號構造函數(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() ;程序運轉輸出結果為：程序運轉輸出結果為：9 7 5 3 13.1.4 3.1.4 鏈式堆棧類鏈式堆棧類1.1.鏈式堆棧鏈式堆棧 鏈式存儲構造的堆棧。鏈式存儲構造的堆棧。2.2.鏈式棧的存儲構造鏈式棧的存儲構造 它是以頭指針為棧頂，在頭指針處插入或刪除，其構造它是以頭指針為棧頂，在頭指針處插入或刪除，其構造如下圖：如下圖：頭結點an-1an-2a0h棧底棧頂鏈棧中每個結點由兩個域構成：鏈棧中每個結點由兩個域構

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

12、 *ptrNext=NULL) next=ptrNext;/構造函數(shù)構造函數(shù)2，用于構造其他結點，用于構造其他結點StackNode(const T& item,StackNode *ptrNext=NULL) data=item;next=ptrNext;StackNode();/鏈式堆棧類的定義鏈式堆棧類的定義template class LinStack private: StackNode *head; /頭指針頭指針 int size; public: /數(shù)據(jù)元素個數(shù)數(shù)據(jù)元素個數(shù)public: LinStack(void); /構造函數(shù)構造函數(shù)LinStack(void) ;

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

14、求的結點空間 StackNode *p,*q;p=head; /p指向頭結點指向頭結點while(p!=NULL) /循環(huán)釋放結點空間循環(huá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) /入棧入棧/新結點新結點newNode的的data域值為域值為item,next域值為域值為head-nextStackNo

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

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

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

18、對的函數(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、表達式計算問題、表達式計算問題 表達式計算是編譯系統(tǒng)中的根本問題，其實現(xiàn)方法是堆表達式計算是編譯系統(tǒng)中的根本問題，其實現(xiàn)方法是堆棧的一個典型運用。在編譯系統(tǒng)中，要把便于人了解的表達棧的一個典型運用。在編譯系統(tǒng)中，要把便于人了解的表達式翻譯成能正確求值的機器指令序列，通常需求先把表達式式翻譯成能正確求值的機器指令序列，通常需求先把表達式變換成機器便于了解的方式，這就要變換表達式的表示序列。變換成機器便于了解的方式，這就要變換表達式的表示序列。假設計算機高級言語中的一個算術表達式為假設計算機高級言語

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

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

24、當前掃描讀到運算符的變量，當順序從中綴表達式中讀入的單詞為運算符時就賦予變量，當順序從中綴表達式中讀入的單詞為運算符時就賦予x2x2，然，然后比較后比較x1x1的優(yōu)先級與的優(yōu)先級與x2x2的優(yōu)先級。的優(yōu)先級。x1x2,x2x1x2,x1x1x2,x1退棧，退棧，寫入后綴表達式中；寫入后綴表達式中；x1=x2=#,x1=x2=#,算法終了。算法終了。 利用堆棧計算后綴表達式值的函數(shù)編寫如下：利用堆棧計算后綴表達式值的函數(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); /運算結果入棧運算結果入棧 cout后綴表達式計算結果為后綴表達式計算結果為:s.Pop()endl;void main() LinStack s; PostExp(s);3.3 3.3 隊隊 列列1、隊列的根本概念、隊列的根本概念(1)(1)定義定義: :只能在表的一端進展插入操作，在表的另一端進展只能在表的一端進展插入操作，在表的另一端進展刪除操作的線性表。一個隊列的表示圖如下：刪除操作的線性表。一個隊列的表示圖如下：隊列的特點：先進先出隊列的特點：先進先出FIFO隊列中允許進展插入操作的一端稱為隊尾；隊列中允許進展插入操作的一端稱為隊尾； 允許進展刪除操作的一端稱為隊頭

27、。允許進展刪除操作的一端稱為隊頭。隊頭和隊尾分別設定隊頭指示器和隊尾指示器。隊頭和隊尾分別設定隊頭指示器和隊尾指示器。隊列的插入操作通常稱為入隊列；隊列的插入操作通常稱為入隊列；隊列的刪除操作通常稱做出隊列。隊列的刪除操作通常稱做出隊列。隊尾插隊尾插入入隊頭刪隊頭刪除除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)順序隊列順序隊列 順序存儲構造的隊列。順序存儲構造的隊列。(2)(2)順序隊列的存儲構造順序隊列的存儲構造 以下圖是一個有以下圖是一個有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)的有存儲空間但不能進展入隊列操作的溢出。存儲空間但不能進展入隊列操作的溢出。如何處理順序隊列的假溢出問題？如何處理順序隊列的假溢出問題？可采取四種方法：可采取四種方法：1)1)采用循環(huán)隊列；采用循環(huán)隊列； 2) 2)按最大能夠的進隊操作次數(shù)設置順序隊列的最大按最大能夠的進隊操作次數(shù)設置順序隊列的最大元素個數(shù)；元素個數(shù)； 3) 3)修正出隊算法，使每次出隊列后都把隊列中剩余修正出隊算法，使每次出隊列后都把隊列

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

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)二義性?。慌袥Q條件將出現(xiàn)二義性！處理方案有三：處理方案有三：運用一個計數(shù)器記錄隊列中元素個數(shù)即隊列長運用一個計數(shù)器記錄隊列中元素個數(shù)即隊列長度；度；判隊滿：判隊滿：count0 & rear=front 判隊空：判隊空：count=0加設標志位，出隊時置加設標志位，出隊時置,入隊時置入隊時置,那么可識別那么可識別當前當前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ù)器方法來判別隊空形狀和隊滿形狀，類定義如下: :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) /構造函數(shù)構造函數(shù)front=rear=0;count=0; front=rear=0;count=0; SeqQueue(void) /SeqQueue(void) /析構函數(shù)析構函數(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插入隊列作為當前

36、的新隊尾插入隊列作為當前的新隊尾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、鏈式隊列類、鏈式隊列類(1)(1)鏈式隊列鏈式隊列 鏈式存儲構造的隊列。鏈式存儲構造的隊

38、列。(2)(2)鏈式隊列的存儲構造鏈式隊列的存儲構造 鏈式隊列的隊頭指針指向隊列的當前隊頭結鏈式隊列的隊頭指針指向隊列的當前隊頭結點點; ;隊尾指針指在隊列的當前隊尾結點隊尾指針指在隊列的當前隊尾結點, ,以下圖以下圖是一個不帶頭結點的鏈式隊列的構造：是一個不帶頭結點的鏈式隊列的構造：a0a1an-1an-1frontrear(3)(3)鏈式隊列類的定義及實現(xiàn)鏈式隊列類的定義及實現(xiàn)結點類的定義和實現(xià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: / /構造函數(shù)構造函數(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(); /析構函數(shù)析構函數(shù);為了方便設計，添加了一個為了方便設計，添加了一個countcount域用來計算當前的元素個數(shù)域用來計算當前的元素個數(shù) 鏈式隊列類的定義如下：鏈式隊列類的定義如下：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); /構造函數(shù)構造函數(shù)LinQueue(void); /LinQueue(void); /析構函數(shù)析構函數(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;鏈式隊列類的實現(xiàn)如下：鏈式隊列類的實現(xiàn)如下：template LinQueue :LinQueue() /構造函數(shù)構造函數(shù)front=rear=NULL; /鏈式隊列無頭結點鏈式隊列無頭結點count=0; /count的初值為的初值為0template LinQueue

43、 :LinQueue(void) /析構函數(shù)析構函數(shù)QueueNode *p,*q;p=front; /p指向第一個結點指向第一個結點while(p!=NULL) /循環(huán)直至全部結點空間釋放循環(huá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插入隊列作為新隊尾結點插入隊列作為新隊尾結點/構造新結點構造新結點newNode，newNode的的data域值為域值為

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

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

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

47、要判別的字符串。把字符數(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)先級隊列用順序存儲構造存儲的優(yōu)先級隊列。、順序優(yōu)先級隊列用順序存儲構造存儲的優(yōu)先級隊列。、優(yōu)先級隊列和普通隊列的主要區(qū)別、優(yōu)先級隊列和普通隊列的主要區(qū)別優(yōu)先級隊列的出隊列操作不是把隊頭元素出隊列，而是把優(yōu)先級隊列的出隊列操作不是把隊頭元素出隊列，而是把隊列中優(yōu)先級最高的元素出隊列。隊列中優(yōu)先級最高的元素出隊列。它的數(shù)據(jù)元素定義為如下構造體：它的數(shù)據(jù)元素定義為如下構造體：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ù)前