[文學(xué)]第四章 棧和隊(duì)列ppt課件

1、第4章 棧和隊(duì)列ADT STACK IS Data： 一個(gè)棧一個(gè)棧S，假定用標(biāo)識(shí)符，假定用標(biāo)識(shí)符StackType表示棧對(duì)象類(lèi)型表示棧對(duì)象類(lèi)型 Operation: void InitStack (StackType& S); /初始化初始化 void Push(StackType& S, ElemType item); /入棧入棧 ElemType Pop (StackType&S); /出棧出棧 ElemType Peek(StackType& S); /返回棧頂元素返回棧頂元素 bool EmptyStack (StackType& S);/判斷是否為空判斷是否為空 void Clear

2、Stack (StackType &S); /清空清空end STACKInitStack(a); /初始化初始化aPush(a,18); /1818進(jìn)棧進(jìn)棧int x=46; Push(a,x); /46進(jìn)棧進(jìn)棧Push(a,x/3); /1515進(jìn)棧進(jìn)棧x=Pop(a); /1515出棧，出棧，x=15x=15coutPeek(a); /讀取棧頂元素讀取棧頂元素46并輸出并輸出Pop(a); / 4646出棧出棧EmptyStack (a); /返回返回false，因?yàn)闂７强眨驗(yàn)闂７强誧outPop(a);endl; /屏幕顯示屏幕顯示1818，1818出棧出棧x=EmptyStack

3、(a); /返回返回x=1，因?yàn)闂？眨驗(yàn)闂？站毩?xí)：1.有a,b,c三個(gè)元素依次進(jìn)棧，任何時(shí)候都可以出棧，共有多少種出棧次序？ a,b,c a,c,b b,a,c b,c,a c,b,a2.P173習(xí)題4-1棧的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)棧的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)ntop - 棧頂棧頂n?？諚？?top =-1 棧滿棧滿 top=MaxSize-1Struct Stack ElemType stackMaxSize; int top; 進(jìn)棧進(jìn)棧/出棧都在棧頂進(jìn)行出棧都在棧頂進(jìn)行時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O（1） abc top d0123 top=-1 top=3 動(dòng)態(tài)分配數(shù)組空間Struct St

4、ack ElemType *stack; int top; int MaxSize; 1.初始化棧初始化棧S為空為空void InitStack(Stack& S) S.MaxSize=10; S.stack=new ElemTypes.MaxSize; if(!S.stack) cerr“動(dòng)態(tài)存儲(chǔ)分配失?。?dòng)態(tài)存儲(chǔ)分配失??！”endl; exit(1); S.top=-1; top=-1 2.元素元素item進(jìn)棧，即插入到棧頂進(jìn)棧，即插入到棧頂void Push(Stack& S，ElemType item) if(S.top=S.MaxSize-1) int k=sizeof(ElemTy

5、pe); S.stack=(ElemType*)realloc(S.stack,2*S.MaxSize*k); S.MaxSize=2*S.MaxSize; S.top+; S.stackS.top=item; 2.元素元素item進(jìn)棧，即插入到棧頂進(jìn)棧，即插入到棧頂void Push(Stack& S，ElemType item) if(S.top=S.MaxSize-1) cerr“Stack is Full!”endl; exit(1); S.top+; S.stackS.top=item; ba top 3. 刪除棧頂元素并返回刪除棧頂元素并返回ElemType Pop(Stack&

6、S) if(S.top=-1) cerr“Stack is Empty!”endl; exit(1); S.top-; return S.stackS.top+1;abcd0123 top=3 top 4.讀取棧頂元素的值讀取棧頂元素的值ElemType Peek(Stack& S) if(S.top=-1) cerr“Stack is empty!”data=item; newptr-next=HS; HS=newptr; data nextHSnewptr（3）從鏈棧中刪除一個(gè)元素并返回從鏈棧中刪除一個(gè)元素并返回 ElemType Pop(SNode*& HS) if(HS=NULL) c

7、err“Linked stack is empty!”next; ElemType temp=p-data; delete p; return temp; data nextHS（4）讀取棧頂元素讀取棧頂元素 ElemType Peek(SNode * HS) if(HS=NULL) cerr“Linked stack is empty!”data; data nexttopHS（5）檢查鏈棧是否為空）檢查鏈棧是否為空 bool EmptyStack (SNode * HS) return HS=NULL; （6）清除鏈棧為空）清除鏈棧為空 void ClearStack(SNode *& H

8、S) SNode *p; while (HS!=NULL) p=HS; HS=HS-next; delete p; HS=NULL; data nexttopHS 4.5 4.5 算術(shù)表達(dá)式的計(jì)算算術(shù)表達(dá)式的計(jì)算4.5.1 4.5.1 算術(shù)表達(dá)式的兩種表示算術(shù)表達(dá)式的兩種表示 1. 1. 中綴算術(shù)表達(dá)式：中綴算術(shù)表達(dá)式： 雙目運(yùn)算符出現(xiàn)在兩個(gè)操作數(shù)中間的表達(dá)式雙目運(yùn)算符出現(xiàn)在兩個(gè)操作數(shù)中間的表達(dá)式 2 如：如：a+ba+b中綴算術(shù)表達(dá)式計(jì)算必須遵守以下三條規(guī)則：中綴算術(shù)表達(dá)式計(jì)算必須遵守以下三條規(guī)則：（1 1）先計(jì)算括號(hào)內(nèi)，后計(jì)算括號(hào)外；）先計(jì)算括號(hào)內(nèi)，后計(jì)算括號(hào)外；（2 2）先乘除，后加減；

9、）先乘除，后加減；（3 3）同一優(yōu)先級(jí)運(yùn)算，從左向右依次進(jìn)行；）同一優(yōu)先級(jí)運(yùn)算，從左向右依次進(jìn)行；2. 2. 后綴算術(shù)表達(dá)式（逆波蘭式）：后綴算術(shù)表達(dá)式（逆波蘭式）： 雙目運(yùn)算符出現(xiàn)在兩個(gè)操作數(shù)后面的表達(dá)式。雙目運(yùn)算符出現(xiàn)在兩個(gè)操作數(shù)后面的表達(dá)式。 如如:a b +:a b + 特點(diǎn)：特點(diǎn)：不存在括號(hào)，不存在優(yōu)先級(jí)的差別，計(jì)不存在括號(hào)，不存在優(yōu)先級(jí)的差別，計(jì)算過(guò)程完全按照運(yùn)算符出現(xiàn)的先后次序進(jìn)行，算過(guò)程完全按照運(yùn)算符出現(xiàn)的先后次序進(jìn)行，整個(gè)計(jì)算過(guò)程只需掃描表達(dá)式一次就可完成。整個(gè)計(jì)算過(guò)程只需掃描表達(dá)式一次就可完成。 例：（例：（12-412-4）/5 /5 中綴表達(dá)式中綴表達(dá)式 12 4 5

10、/ 12 4 5 / 后綴表達(dá)式后綴表達(dá)式 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的規(guī)則：中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的規(guī)則： 按照運(yùn)算符的優(yōu)先級(jí)，對(duì)中綴表達(dá)式作以下處理：按照運(yùn)算符的優(yōu)先級(jí)，對(duì)中綴表達(dá)式作以下處理：將運(yùn)算符移到運(yùn)算對(duì)象后面，相鄰與其最后一個(gè)運(yùn)算對(duì)將運(yùn)算符移到運(yùn)算對(duì)象后面，相鄰與其最后一個(gè)運(yùn)算對(duì)象，刪除掉所有的括號(hào)。象，刪除掉所有的括號(hào)。后綴算術(shù)表達(dá)式的運(yùn)算：后綴算術(shù)表達(dá)式的運(yùn)算： 3/5+6 -3/5+6 - 3 5 / 6 + 3 5 / 6 + 16-9 16-9* *(4+3) -(4+3) - 16 9 4 3 + 16 9 4 3 + * * - - 2 2* *(x+y)/(1

11、-x) -(x+y)/(1-x) - 2 x y + 2 x y + * * 1 x - / 1 x - / (25+x) (25+x)* *(a(a* *(a+b)+b)(a+b)+b)25 x + a a b + 25 x + a a b + * * b + b + * *特點(diǎn)：特點(diǎn)：運(yùn)算對(duì)象的相對(duì)次序不變運(yùn)算對(duì)象的相對(duì)次序不變4.5.2 4.5.2 后綴表達(dá)式求值的算法后綴表達(dá)式求值的算法 設(shè)置一個(gè)棧，掃描后綴表達(dá)式中的各個(gè)字符，設(shè)置一個(gè)棧，掃描后綴表達(dá)式中的各個(gè)字符， 如果掃描到的是運(yùn)算對(duì)象（操作數(shù)），將其壓棧，如果掃描到的是運(yùn)算對(duì)象（操作數(shù)），將其壓棧，若是運(yùn)算符，則從棧中彈出兩個(gè)數(shù)

12、據(jù)進(jìn)行運(yùn)算，若是運(yùn)算符，則從棧中彈出兩個(gè)數(shù)據(jù)進(jìn)行運(yùn)算，然后將運(yùn)算結(jié)果壓棧，依此類(lèi)推，直到掃描完所然后將運(yùn)算結(jié)果壓棧，依此類(lèi)推，直到掃描完所有的字符為止，此時(shí)，棧中只剩一個(gè)數(shù)據(jù)，即是有的字符為止，此時(shí)，棧中只剩一個(gè)數(shù)據(jù)，即是算術(shù)表達(dá)式運(yùn)算后的最后結(jié)果。算術(shù)表達(dá)式運(yùn)算后的最后結(jié)果。4.7.1 隊(duì)列的定義隊(duì)列的定義運(yùn)算受限的線性表運(yùn)算受限的線性表q隊(duì)列是只允許在一端刪除，在另一端插入的線隊(duì)列是只允許在一端刪除，在另一端插入的線性表性表q允許刪除的一端叫做隊(duì)頭允許刪除的一端叫做隊(duì)頭(front)，允許插入的，允許插入的一端叫做隊(duì)尾一端叫做隊(duì)尾(rear)q插入稱(chēng)進(jìn)隊(duì)插入稱(chēng)進(jìn)隊(duì)(入隊(duì)入隊(duì)), 刪除稱(chēng)離隊(duì)

13、刪除稱(chēng)離隊(duì)(出隊(duì)出隊(duì))q先進(jìn)先出先進(jìn)先出(FIFO, First In First Out)4.4.2 4.4.2 隊(duì)列的抽象數(shù)據(jù)類(lèi)型隊(duì)列的抽象數(shù)據(jù)類(lèi)型ADT QUEUE is Data: 一個(gè)隊(duì)列一個(gè)隊(duì)列Q Q，QueueTypeQueueType為存儲(chǔ)類(lèi)型為存儲(chǔ)類(lèi)型 Operation(基本操作基本操作): void InitQueue(QueueType & Q); void EnQueue(QueueType &Q, ElemType item); ElemType OutQueue(QueueType & Q); ElemType PeekQueue(QueueType Q); bo

14、ol EmptyQueue (QueueType & Q); void ClearQueue (QueueType & Q);end QUEUE 假定有一個(gè)隊(duì)列假定有一個(gè)隊(duì)列q，其元素類(lèi)型為整型，其元素類(lèi)型為整型int，下面給出調(diào)，下面給出調(diào)用上述操作的一些例子。用上述操作的一些例子。(1) InitQueue(q); /把隊(duì)列把隊(duì)列q置為一個(gè)空隊(duì)列置為一個(gè)空隊(duì)列(2) EnQueue(q,35); /元素元素35進(jìn)隊(duì)，隊(duì)列為（進(jìn)隊(duì)，隊(duì)列為（35）(3) int x=12; EnQueue(q,2*x+3); /元素元素2*x+3的值的值27進(jìn)隊(duì)，此時(shí)隊(duì)列為（進(jìn)隊(duì)，此時(shí)隊(duì)列為（35,27）(4

15、) EnQueue(q,-16); /元素元素-16進(jìn)隊(duì)，此時(shí)隊(duì)列為進(jìn)隊(duì)，此時(shí)隊(duì)列為(35,27,-16)(5) coutPeekQueue(q)endl; /輸出隊(duì)首元素輸出隊(duì)首元素35,原隊(duì)列保持不變?cè)?duì)列保持不變(6) OutQueue(q); OutQueue(q); /依次刪除隊(duì)列元素依次刪除隊(duì)列元素35和和27，此時(shí)隊(duì)列為，此時(shí)隊(duì)列為(-16)(7)while(!EmptyQueue(q) coutOutQueue(q)top=n) cout“隊(duì)列已滿！”endl; else push(s1,x); void OutQueue(s1,s2,x) stack s1,s2; int x

16、; s2.top=-1; while(!EmptyStack(s1) push(s2,pop(s1); x=pop(s2); while(!EmptyStack(s2) push(s1,pop(s2); bool EmptyQueue(s1) stack s1; if(EmptyStack(s1) return ture; else return false; 4.7.3 4.7.3 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn) 使用數(shù)組和兩個(gè)整型變量分別存儲(chǔ)隊(duì)首和使用數(shù)組和兩個(gè)整型變量分別存儲(chǔ)隊(duì)首和隊(duì)尾元素的下標(biāo)位置隊(duì)尾元素的下標(biāo)位置 struct Queue ElemType

17、queueMaxSize; int front, rear; ;front = rear =0 時(shí)時(shí), ,初始化；初始化； 進(jìn)隊(duì)時(shí)隊(duì)尾指針先進(jìn)進(jìn)隊(duì)時(shí)隊(duì)尾指針先進(jìn)1 1 rear = rear + 1，再寫(xiě)入，再寫(xiě)入， rear 指向尾元素指向尾元素 出隊(duì)時(shí)隊(duì)頭指針先進(jìn)出隊(duì)時(shí)隊(duì)頭指針先進(jìn)1 front = front + 1，再刪除，再刪除， front 指向隊(duì)列頭元素指向隊(duì)列頭元素 當(dāng)當(dāng)frontrear時(shí)，隊(duì)列是什么狀態(tài)呢？時(shí)，隊(duì)列是什么狀態(tài)呢？規(guī)定：規(guī)定：讓讓front指向隊(duì)首元素的前一單元的位置。指向隊(duì)首元素的前一單元的位置。 當(dāng)當(dāng)frontrear時(shí)，隊(duì)列為空時(shí)，隊(duì)列為空注意：數(shù)組長(zhǎng)度

18、為注意：數(shù)組長(zhǎng)度為N，隊(duì)列只能使用其中的，隊(duì)列只能使用其中的N-1個(gè)。個(gè)。 假設(shè)數(shù)組長(zhǎng)度為N，則 （1）當(dāng)front0，rearN1時(shí)， 隊(duì)滿，入隊(duì)則溢出（真溢出） （2）當(dāng)front！0，rearN1時(shí)， 入隊(duì)也會(huì)溢出（假溢出）解決方案： （1）隊(duì)首固定：每次出隊(duì)后，剩余元素向前移動(dòng)，隊(duì)首元素永遠(yuǎn)在數(shù)組第一個(gè)位置上。 缺點(diǎn)：造成大量數(shù)據(jù)的移動(dòng)，浪費(fèi)時(shí)間 （2）循環(huán)隊(duì)列：利用模運(yùn)算n存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。n隊(duì)頭、隊(duì)尾指針加隊(duì)頭、隊(duì)尾指針加1 1時(shí)從時(shí)從maxSize -1直接進(jìn)到直接進(jìn)到0 0，可用語(yǔ)言的取?？捎谜Z(yǔ)言的取模( (余數(shù)余數(shù))

19、)運(yùn)算實(shí)現(xiàn)。運(yùn)算實(shí)現(xiàn)。n隊(duì)頭指針進(jìn)隊(duì)頭指針進(jìn)1: 1: front = (front + 1) % MaxSize;n隊(duì)尾指針進(jìn)隊(duì)尾指針進(jìn)1: 1: rear = (rear + 1) % MaxSize;n隊(duì)列初始化：隊(duì)列初始化：front = rear = 0;n隊(duì)空條件：隊(duì)空條件：front = rear;n隊(duì)滿條件：隊(duì)滿條件：(rear + 1) % MaxSize = front n隊(duì)列元素個(gè)數(shù)：隊(duì)列元素個(gè)數(shù)：(rear-front+Maxsize)%Maxsizen插入和刪除的時(shí)間復(fù)雜度為插入和刪除的時(shí)間復(fù)雜度為O（1）；）；123450J3J5J4Q.frontQ.rear一般情

20、況一般情況123450J3J5J4Q.frontQ.rearJ6J7J8隊(duì)滿隊(duì)滿123450Q.frontQ.rear隊(duì)空隊(duì)空練習(xí)：1. 棧和隊(duì)列的共同點(diǎn)是_2. A. 都實(shí)先進(jìn)后出 B. 都是先進(jìn)先出3. C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn)C2. 已知一個(gè)棧的進(jìn)棧序列是1，2，3，n，其輸出序列是p1,p2,pn,若p1=n,則pi= _ A. i B. n-i C. n-i+1 D.不確定C3.將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用_保存中間結(jié)果 A. 隊(duì)列 B. 棧 C. 鏈表 D.樹(shù)B4. 元素A、B、C、D依次進(jìn)順序棧后，棧頂元素是_，棧底元素是_A. A

21、 B.B C.C D.DDA5. 元素A、B、C、D順序連續(xù)進(jìn)入隊(duì)列qu后，隊(duì)頭元素是_，隊(duì)尾元素是_A. A B.B C.C D.DAD6. 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)rear和front的值分別為0和3.當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？A. 1和5 B.2和4 C.4和2 D.5和1B7. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是_。 A.6 B.4 C.3 D.28.若tail=

22、32指向隊(duì)尾元素，head=15指向隊(duì)頭元素的前一個(gè)空位置，隊(duì)列空間m=60，則循環(huán)隊(duì)列中元素?cái)?shù)目是_。 A. 42 B. 16 C.17 D.41CC判斷題1.棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。2.有n個(gè)數(shù)順序（依次）進(jìn)棧，出棧序列有Cn種，即：3.即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同。4.消除遞歸不一定需要使用棧。5.棧的輸入序列為123n，輸出序列為a1a2an，若ai=n（1iai+1an.21(2 )!*1 ( !)nCnnn4.7.3 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn) 使用數(shù)組和兩個(gè)整型變量分別存

23、儲(chǔ)隊(duì)首和隊(duì)尾元素使用數(shù)組和兩個(gè)整型變量分別存儲(chǔ)隊(duì)首和隊(duì)尾元素的下標(biāo)位置的下標(biāo)位置 struct Queue ElemType queueMaxSize; int front, rear; ; ElemType *queue=new ElemTypen; /動(dòng)態(tài)分配數(shù)組空間動(dòng)態(tài)分配數(shù)組空間隊(duì)列運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)隊(duì)列運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)（1） 初始化隊(duì)列初始化隊(duì)列 void InitQueue(Queue& Q) Q.front=Q.rear=0; （2） 把一個(gè)隊(duì)列清空把一個(gè)隊(duì)列清空 void ClearQueue(Queue& Q) Q.front=Q.rear=0; Q.rea

24、r123450Q.front隊(duì)空隊(duì)空（3） 檢查一個(gè)隊(duì)列是否為空檢查一個(gè)隊(duì)列是否為空 bool EmptyQueue (Queue& Q) return Q.front=Q.rear; /yes:1, no:0（4） 讀取隊(duì)首元素讀取隊(duì)首元素 ElemType PeekQueue(Queue& Q) if(Q.front=Q.rear) cerr“The Queue is Empty!”endl; exit(1); return Q.queue(Q.front+1)% Q.MaxSize; （5） 插入一個(gè)元素插入一個(gè)元素 void EnQueue (Queue& Q, ElemType& i

25、tem) int k= (Q.rear+1)% Q.MaxSize; if(k=Q.front) cerr“The Queue is Full!”endl; exit(1); Q.rear=k; Q.queuerear=item; 123450J3J5J4Q.frontQ.rear（6） 刪除一個(gè)元素刪除一個(gè)元素ElemType OutQueue (Queue& Q) if(Q.front=Q.rear) cerr“The Queue is Empty!”data=item; newptr-next=NULL: if (HQ.rear=NULL) /Empty Queue HQ.rear=HQ

26、.front=newptr; else HQ.rear=HQ.rear-next=newptr; （3） 從隊(duì)列中刪除一個(gè)元素從隊(duì)列中刪除一個(gè)元素ElemType OutQueue(LinkQueue& HQ) if(HQ.front=NULL) cerr“The Queue is Empty!”data; LNode *p=HQ.front; HQ.front=p-next; if (HQ.front=NULL) HQ.rear=NULL; delete p; return temp; （4） 讀取隊(duì)首元素讀取隊(duì)首元素ElemType PeekQueue (LinkQueue& HQ) if(HQ.front=NULL) cerr“The Queue is Empty!”data; （5） 檢查鏈隊(duì)是否為空檢查鏈隊(duì)是否為空 bool EmptyQueue(LinkQueue& HQ) return HQ.front=NULL; /HQ.rear=NULL（6） 清除鏈隊(duì)中的所有元素，使之變?yōu)榭贞?duì)清除鏈隊(duì)中的所有元素，使之變?yōu)榭贞?duì) void ClearQueue(LinkQueue & HQ)