1、第3章 限定性線性表堆棧和隊列3.1 堆棧3.2 堆棧應(yīng)用3.4* 優(yōu)先級隊列 棧和隊列是兩種重要的抽象數(shù)據(jù)類型，是一類操作受限制的特殊線性表，其特殊性在于限制插入和刪除等運算的位置。3.3 隊列13.1 堆 棧3.1.1 堆棧的基本概念 堆棧的定義：限定只能在固定一端進行插入和刪除操作的線性表。 通常將表中允許進行插入、刪除操作的一端稱為棧頂 (Top)，表的另一端被稱為棧底 (Bottom)。 當(dāng)棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進棧或入棧，刪除操作稱為出?；蛲藯！Ｓ址Q為后進先出的線性表，即LIFO。2 根據(jù)棧定義，每次進棧的元素都被放在原棧頂元素之上而成為新的棧頂，而每次

2、出棧的總是當(dāng)前棧中“最新”的元素，即最后進棧的元素。因此，棧又稱為后進先出的線性表。簡稱為LIFO表。如下圖所示： 進棧、出棧圖例進棧出棧ana2a1進棧出棧棧頂棧底3 例3-1 利用一個堆棧，如果輸入系列由A、B、C組成，試給出全部可能的輸出系列和不可能的輸出系列。 輸出系列有： ABC、ACB、BAC、BCA、CBA 不可能的輸出系列為： CAB43.1.3 棧的表示和實現(xiàn)順序堆棧類 棧在計算機中主要有兩種基本的存儲結(jié)構(gòu)： 順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。 順序存儲的棧為順序棧； 鏈式存儲的棧為鏈棧。61.順序堆棧的存儲結(jié)構(gòu) 順序棧是用順序存儲結(jié)構(gòu)實現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放

3、自棧底到棧頂?shù)臄?shù)據(jù)元素，同時由于棧的操作的特殊性，還必須附設(shè)一個位置指針top（棧頂指針）來動態(tài)地指示棧頂元素在順序棧中的位置。通常以top = 0表示空棧。其結(jié)構(gòu)如圖所示：a0a1a2a3a4stack棧底棧頂MaxStackSize-1012345=top 其中，a0, a1, a2, a3, a4表示順序堆棧中已存儲的數(shù)據(jù)元素，stack表示存放數(shù)據(jù)元素的數(shù)組，MaxStackSize-1表示最大存儲單元個數(shù)，top表示當(dāng)前棧頂存儲下標。7void SeqStack:Push(const DataType item) /入棧/把元素item入棧;堆棧滿時出錯退出if(top=MaxSta

4、ckSize)cout堆棧已滿!endl;exit(0);datatop=item; /先存儲itemtop+; /然后top加19DataType SeqStack:Pop() /出棧/出棧并返回棧頂元素;堆?？諘r出錯退出if(top=0)cout堆棧已空!endl;exit(0);top-; /top先減1return datatop; /然后取元素返回10DataType SeqStack:GetTop(void)const /取棧頂數(shù)據(jù)元素/取當(dāng)前棧頂數(shù)據(jù)元素并返回if(top=0)cout堆?？?endl;exit(0);return datatop-1; /返回當(dāng)前棧頂元素11測試

5、主程序如下：#include #include const int MaxStackSize=100; /定義問題要求的元素數(shù)目的最大值typedef int DataType; /定義具體問題元素的數(shù)據(jù)類型#include seqstack.h3. 順序堆棧類的測試void main(void) SeqStack myStack; /構(gòu)造函數(shù)無參數(shù)時，定義的對象后不帶括號DataType test=1,3,5,7,9;int n=5;for(int i=0;in;i+)myStack.Push(testi);while(myStack.NotEmpty()coutmyStack.Pop()

6、;程序運行輸出結(jié)果為：9 7 5 3 1123.1.4 鏈式堆棧類1.鏈式堆棧 鏈式存儲結(jié)構(gòu)的堆棧。2.鏈式棧的存儲結(jié)構(gòu) 它是以頭指針為棧頂，在頭指針處插入或刪除，其結(jié)構(gòu)如圖所示：頭結(jié)點an-1an-2a0h棧底棧頂鏈棧中每個結(jié)點由兩個域構(gòu)成：data域和next域，其結(jié)點類和類定義分別如下：template class LinStack; /前視定義，否則友元無法定義13/結(jié)點類 template /模板類型為T class StackNode friend class LinStack ; /定義類LinStack為友元 private: T data; /數(shù)據(jù)元素 StackNode *

7、next; /指針 public:/構(gòu)造函數(shù)1，用語構(gòu)造頭結(jié)點StackNode(StackNode *ptrNext=NULL) next=ptrNext;/構(gòu)造函數(shù)2，用于構(gòu)造其他結(jié)點StackNode(const T& item,StackNode *ptrNext=NULL) data=item;next=ptrNext;StackNode();14template LinStack :LinStack() /構(gòu)造函數(shù) head=new StackNode ; /頭指針指向頭結(jié)點 size=0; /size的初值為0 template LinStack :LinStack(void)

8、/析構(gòu)函數(shù)/釋放所有動態(tài)申請的結(jié)點空間 StackNode *p,*q;p=head; /p指向頭結(jié)點while(p!=NULL) /循環(huán)釋放結(jié)點空間 q=p; p=p-next; delete q;16template int LinStack :NotEmpty(void) const /堆棧非空否if(size!=0) return 1;else return 0;template void LinStack :Push(const T& item) /入棧/新結(jié)點newNode的data域值為item,next域值為head-nextStackNode *newNode=new Sta

9、ckNode (item,head-next);head-next=newNode; /新結(jié)點插入棧頂size+; /元素個數(shù)加117template T LinStack :GetTop(void) const /取棧頂元素return head-next-data;說明：1)在鏈棧中的頭結(jié)點對操作的實現(xiàn)影響不大，棧頂（表頭）操作頻繁，可不設(shè)頭結(jié)點鏈棧。2)一般不會出現(xiàn)棧滿情況；除非沒有空間導(dǎo)致malloc分配失敗。3)鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。4)采用鏈棧存儲方式的優(yōu)點是，可使多個棧共享空間；當(dāng)棧中元素個數(shù)變化較大，且存在多個棧的情況下，鏈棧是棧的首選

10、存儲方式。193.2 堆棧應(yīng)用1、括號匹配問題例：假設(shè)一個算法表達式中包含圓括號、方括號和花括號三種類型的括號，編寫一個判別表達式中括號是否正確配對的函數(shù)。設(shè)計思路：用棧暫存左括號20void 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()&mySt

11、ack.GetTop()=()myStack.Pop(); /出棧21else 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;22else if(expi = &myStack.No

12、tEmpty()&myStack.GetTop()=)myStack.Pop(); /出棧else if(expi=&myStack.NotEmpty()&myStack.GetTop()!=) cout左、右括號配對次序不正確!endl; return;23else if(expi=)|(expi=)|(expi=)&!myStack.NotEmpty()cout右括號多于左括號!endl;return;if(myStack.NotEmpty()cout左括號多于右括號!endl;elsecout左、右括號匹配正確!endl;24 表達式的三種標識方法：設(shè) Exp = S1 + OP + S

13、2則稱 OP + S1 + S2 為前綴表示法 S1 + OP + S2 為中綴表示法 S1 + S2 + OP 為后綴表示法 26編譯系統(tǒng)中表達式的計算分為兩個步驟： （1）把中綴表達式變換成相應(yīng)的后綴表達式； （2）根據(jù)后綴表達式計算表達式的值。后綴表達式的兩個特點： （P72 6、7行）中綴表達式變換為后綴表達式的算法步驟可以總結(jié)為： (1)設(shè)置一個堆棧，初始時將棧頂元素置為“”。 (2)順序讀入中綴表達式，當(dāng)讀到的單詞為操作數(shù)時就將其輸出，并接著讀下一個單詞。 (3)令x1為當(dāng)前棧頂運算符的變量，x2為當(dāng)前掃描讀到運算符的變量，當(dāng)順序從中綴表達式中讀入的單詞為運算符時就賦予x2，然后比

14、較x1的優(yōu)先級與x2的優(yōu)先級。x1x2,x1退棧，寫入后綴表達式中；x1=x2=#,算法結(jié)束。 27elsex2=s.Pop(); /退棧得操作數(shù)x1=s.Pop(); /退棧得被操作數(shù)switch(ch)case+:x1+=x2;break; case-:x1-=x2;break; case*:x1*=x2;break; case/:if(x2=0.0)cout除數(shù)為0錯!;exit(0);29else x1/=x2; break; s.Push(x1); /運算結(jié)果入棧 cout后綴表達式計算結(jié)果為:s.Pop()endl;void main() LinStack s; PostExp(s

15、);303.3 隊 列1、隊列的基本概念(1)定義:只能在表的一端進行插入操作，在表的另一端進行刪除操作的線性表。一個隊列的示意圖如下：隊列的特點：先進先出（FIFO）隊列中允許進行插入操作的一端稱為隊尾； 允許進行刪除操作的一端稱為隊頭。隊頭和隊尾分別設(shè)定隊頭指示器和隊尾指示器。隊列的插入操作通常稱為入隊列；隊列的刪除操作通常稱做出隊列。隊尾插入隊頭刪除a0a1a2an-1隊頭隊尾312、隊列抽象數(shù)據(jù)類型數(shù)據(jù)集合:a0,a1,an-1，ai的數(shù)據(jù)類型為DataType。操作集合：(1)Initiate(Q) 初始化隊列Q (2)Append(Q,x) 入隊列 (3)Delete(Q) 出隊列

16、 (4)GetFront(Q) 取隊頭數(shù)據(jù)元素 (5)NotEmpty(Q) 隊列Q非空否323、順序隊列(1)順序隊列 順序存儲結(jié)構(gòu)的隊列。(2)順序隊列的存儲結(jié)構(gòu) 下圖是一個有6個存儲空間的順序隊列的動態(tài)示意圖(a)空隊列front rear=012345CBA(b)入隊列A、B、C后的狀態(tài)front=012345C(c)出隊列A、B后的狀態(tài)front=012345rear =EDC(d)入隊列D、E后的狀態(tài)front=012345rear =rear =33(3)順序隊列的“假溢出”問題假溢出順序隊列因多次入隊列和出隊列操作后出現(xiàn)的有存儲空間但不能進行入隊列操作的溢出。如何解決順序隊列的

17、假溢出問題？可采取四種方法：1)采用循環(huán)隊列； 2)按最大可能的進隊操作次數(shù)設(shè)置順序隊列的最大元素個數(shù)； 3)修改出隊算法，使每次出隊列后都把隊列中剩余數(shù)據(jù)元素向隊頭方向移動一個位置；)修改入隊算法，增加判斷條件，當(dāng)假溢出時，把隊列中的數(shù)據(jù)元素向隊頭移動，然后方完成入隊操作。34(4)順序循環(huán)隊列的基本原理 把順序隊列所使用的存儲空間構(gòu)造成一個邏輯上首尾相連的循環(huán)隊列。當(dāng)rear和front達到MaxQueueSize-1后，再前進一個位置就自動到。順序隊列a3a2a1frontrear 0 1 2 3 . .N-1a3a2a10123N-1rearfront循環(huán)隊列35(5)順序循環(huán)隊列的隊

18、空和隊滿判斷問題（見P77圖3-9）140235frontrear(a)入隊前空隊列140235e6e7e8e4e3e5frontrear(b) 隊列滿時140235e4e3e5frontrear(c) 一般情況（考慮出對后情況）36新問題：在循環(huán)隊列中，空隊特征是front=rear；隊滿時也會有front=rear；判決條件將出現(xiàn)二義性！解決方案有三：使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；判隊滿：count0 & rear=front 判隊空：count=0加設(shè)標志位，出隊時置,入隊時置,則可識別當(dāng)前front=rear屬于何種情況判隊滿：tag=1 & rear=front 判

19、隊空：tag=0 & rear=front 少用一個存儲單元判隊滿： front=(rear+1)%MaxQueueSize 判隊空： rear=front374、順序循環(huán)隊列類采用設(shè)置計數(shù)器方法來判斷隊空狀態(tài)和隊滿狀態(tài)，類定義如下:class SeqQueue private: DataType dataMaxQueueSize; /順序隊列數(shù)組 int front; /隊頭指示器 int rear; /隊尾指示器 int count; /元素個數(shù)計數(shù)器 public: SeqQueue(void) /構(gòu)造函數(shù)front=rear=0;count=0; SeqQueue(void) /析構(gòu)函

20、數(shù) void Append(const DataType& item); /入隊列 DataType Delete(void); /出隊列 DataType GetFront(void)const; /取隊頭數(shù)據(jù)元素 int NotEmpty(void)const /非空否 return count!=0;38void SeqQueue:Append(const DataType& item) /入隊列/把數(shù)據(jù)元素item插入隊列作為當(dāng)前的新隊尾if(count0&front=rear)cout隊列已滿!endl;exit(0);datarear=item; /把元素item加在隊尾rear=

21、(rear+1) % MaxQueueSize; /隊尾指示器加1cout+; /計數(shù)器加139DataType SeqQueue:Delete(void) /出隊列/把隊頭元素出隊列，出隊列元素由函數(shù)返回if(count=0)cout隊列已空!endl;exit(0);DataType temp=datafront; /保存原隊頭元素front=(front+1) % MaxQueueSize; /隊頭指示器加1count-; /計數(shù)器減1return temp; /返回原隊頭元素40DataType SeqQueue:GetFront(void)const /取隊頭數(shù)據(jù)元素/取隊頭元素并由

22、函數(shù)返回if(count=0)cout隊列已空!endl;exit(0);return dataFront; /返回隊頭元素415、鏈式隊列類(1)鏈式隊列 鏈式存儲結(jié)構(gòu)的隊列。(2)鏈式隊列的存儲結(jié)構(gòu) 鏈式隊列的隊頭指針指向隊列的當(dāng)前隊頭結(jié)點;隊尾指針指在隊列的當(dāng)前隊尾結(jié)點,下圖是一個不帶頭結(jié)點的鏈式隊列的結(jié)構(gòu)：a0a1an-1an-1frontrear42(3)鏈式隊列類的定義及實現(xiàn)結(jié)點類的定義和實現(xiàn)如下：template class LinQueue;/前視定義，否則友元無法定義template class QueueNode friend class LinQueue ; /定義類Li

23、nQueue為友元private: QueueNode *next; /指針 T data; /數(shù)據(jù)元素 public: /構(gòu)造函數(shù)QueueNode(const T& item,QueueNode *ptrNext=NULL):data(item),next(ptrNext)QueueNode(); /析構(gòu)函數(shù);43為了方便設(shè)計，增加了一個count域用來計算當(dāng)前的元素個數(shù) 鏈式隊列類的定義如下：template class LinQueue pprivate: QueueNode *front; /隊頭指針QueueNode *rear; /隊尾指針 int count; /計數(shù)器 pub

24、lic: LinQueue(void); /構(gòu)造函數(shù)LinQueue(void); /析構(gòu)函數(shù)void Append(const T& item); /入隊列 T Delete(void); /出隊列 T GetFront(void)const; /取隊頭數(shù)據(jù)元素int NotEmpty(void)const /非空否return count!=0;44鏈式隊列類的實現(xiàn)如下：template LinQueue :LinQueue() /構(gòu)造函數(shù)front=rear=NULL; /鏈式隊列無頭結(jié)點count=0; /count的初值為045template LinQueue :LinQueue(

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

26、NULL) rear-next=newNode; /新結(jié)點鏈入rear=newNode; /隊尾指針指向新隊尾結(jié)點/若隊頭指針原先為空則置為指向新結(jié)點if(front=NULL) front=newNode;count+; /計數(shù)器加147template T LinQueue :Delete(void) /出隊列 /把隊頭結(jié)點刪除并由函數(shù)返回 if(count=0) cout隊列已空!endl; exit(0); QueueNode *p=front-next; /p指向新的隊頭結(jié)點T data=front-data; /保存原隊頭結(jié)點的data域值delete front; /釋放原隊頭結(jié)

27、點空間front=p; /front指向新的對頭結(jié)點count-; /計數(shù)器減1return data; /返回原隊頭結(jié)點的data域值48template T LinQueue :GetFront(void)const /取隊頭數(shù)據(jù)元素if(count=0)cout隊列已空!data;496、隊列的應(yīng)用例：編寫判斷一個字符序列是否是回文的函數(shù)。編程思想：設(shè)字符數(shù)組str中存放了要判斷的字符串。把字符數(shù)組中的字符逐個分別存入隊列和堆棧，然后逐個出隊列和退棧并比較出隊列的字符和退棧的字符是否相等，若全部相等則該字符序列是回文，否則就不是回文。設(shè)計函數(shù)如下：50void HuiWen(char s

28、tr) LinStack myStack; LinQueue myQueue; int n=strlen(str); /求字符串長度for(int i=0;in;i+) myQueue.Append(stri); myStack.Push(stri); while(myQueue.NotEmpty()&myStack.NotEmpty() if(myQueue.Delete()!=myStack.Pop() cout不是回文!endl; return; cout是回文!endl;513.4 優(yōu)先級隊列、優(yōu)先級隊列帶有優(yōu)先級的隊列。、順序優(yōu)先級隊列用順序存儲結(jié)構(gòu)存儲的優(yōu)先級隊列。、優(yōu)先級隊列和一般隊列的主要區(qū)別優(yōu)先級隊列的出隊列操作不是把隊頭元素出隊列，而是把隊列中優(yōu)先級最高的元素出隊列。它的數(shù)據(jù)元素定義為如下結(jié)構(gòu)體：struct DataType ElemTy