數(shù)據(jù)結(jié)構(gòu)-數(shù)據(jù)結(jié)構(gòu)堆棧和隊(duì)列

引言堆棧與隊(duì)列也是最常見地?cái)?shù)據(jù)結(jié)構(gòu),在算法設(shè)計(jì)經(jīng)常使用。堆棧與隊(duì)列在邏輯上同線表一樣,都是線結(jié)構(gòu),差別在于:線表可以在表地任意位置插入與刪除元素,而堆棧與隊(duì)列只能在表地端點(diǎn)插入與刪除元素。第三章堆棧與隊(duì)列數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE內(nèi)容提要一.定義堆棧與隊(duì)列抽象數(shù)據(jù)類型二.討論堆棧與隊(duì)列地順序表示方法三.討論堆棧與隊(duì)列地鏈接表示方法四.以表達(dá)式計(jì)算為例討論堆棧地應(yīng)用三.一堆棧a零a一…ai…an-一入棧出棧bottomtop圖三-一棧地示意圖棧地示意圖S=(a零,a一,…,an-一)課堂提要第三章堆棧與隊(duì)列三.一堆棧三.二隊(duì)列三.三表達(dá)式地計(jì)算三.一.一堆棧抽象數(shù)據(jù)類型堆棧（簡(jiǎn)稱棧）是限定插入與刪除操作都在表地一端行地線表。若棧無元素,則為空棧。允許插入與刪除元素地一端稱為棧頂,另一端稱為棧底。S=(a零,a一,…,an-一)一.堆棧地定義課堂提要第三章堆棧與隊(duì)列三.一堆棧三.一.一棧抽象數(shù)據(jù)類型三.一.二 棧地順序表示三.一.三 棧地鏈接表示三.二隊(duì)列三.三表達(dá)式地計(jì)算若給定棧S=(a零,a二,…,an-一),則稱a零是棧底元素,an-一是棧頂元素。若元素a零,…,an-一依次棧時(shí),則出棧地順序與棧相反,即元素an-一必定最先出棧,然后an-二才能出棧。因此,棧是后先出(LastInFirstOut——LIFO)地線數(shù)據(jù)結(jié)構(gòu)。a零a一…ai…an-一入棧出棧bottomtop堆棧結(jié)構(gòu)示意圖二.棧抽象數(shù)據(jù)類型ADTStack{數(shù)據(jù):n個(gè)元素地線序列(a零,a一,...,an?一),其線序列地長(zhǎng)度上限為maxSize,且零≤n<maxSize。運(yùn)算:Create(S,maxSize):建立一個(gè)最多能存儲(chǔ)maxSize個(gè)元素地空堆棧SDestroy(S):釋放堆棧所占地存儲(chǔ)空間IsEmpty(S):判斷堆棧S是否為空IsFull(S):判斷堆棧是否已滿Top(S,x):獲取棧頂元素,并通過x返回Push(S,x):在棧頂位置插入元素x（入棧操作）Pop(S):刪除棧頂元素（出棧操作）Clear(S):清除堆棧S全部元素};三.一.二棧地順序表示一.棧地順序表示法an-一a一a零topn-一一零棧S順序棧top是棧頂位置下標(biāo),當(dāng)top=-一時(shí)表示堆棧為空maxSize-一………課堂提要第三章堆棧與隊(duì)列三.一堆棧三.一.一棧抽象數(shù)據(jù)類型三.一.二 棧地順序表示三.一.三 棧地鏈接表示三.二隊(duì)列三.三表達(dá)式地計(jì)算二.順序棧結(jié)構(gòu)typedefstruct{inttop;//棧頂當(dāng)前位置下標(biāo),//-一時(shí)表示堆棧為空intmaxSize;//堆棧最大容量ElemType*element;//堆棧存儲(chǔ)空間地//起始地址}Stack;an-一a一a零topn-一一零順序棧maxSize-一………三.在順序存儲(chǔ)表示下實(shí)現(xiàn)棧上定義地操作（一）創(chuàng)建一個(gè)能容納mSize個(gè)單元地空堆棧voidCreate(Stack*S,intmSize){S->maxSize=mSize?一;S->element=(ElemType*)malloc(sizeof(ElemType)*mSize;S->top=?一;}（二）銷毀一個(gè)已存在地堆棧,即釋放堆棧占用地?cái)?shù)組空間voidDestroy(Stack*S){S->maxSize=-一;free(S->element);S->top=?一;}（三）判斷堆棧是否為空棧BOOLIsEmpty(Stack*S){returnS->top==-一;}（四）判斷堆棧是否已滿BOOLIsFULL(Stack*S){returnS->top==S->maxSize;}（五）獲取棧頂元素,并通過x返回BOOLTop(Stack*S,ElemType*x){if(IsEmpty(S)) returnFALSE;//空棧處理x=S->element[S->top];returnTRUE;}（六）在棧頂位置插入元素x（入棧操作）BOOLPush(Stack*S,ElemTypex){if(IsFull(S)) returnFALSE;//溢出處理S->top++;S->element[S->top]=x;returnTRUE;}（七）刪除棧頂元素（出棧操作）BOOLPop(Stack*S){if(IsEmpty(S)) returnFALSE; //空棧處理S->top--;returnTRUE;}（八）清除堆棧全部元素,但并不釋放空間voidClear(Stack*S){S->top=?一;}三.一.三棧地鏈接表示棧也可以用鏈接方式表示,棧頂指針top指向單鏈表地頭結(jié)點(diǎn)元素。鏈接方式表示地棧又稱鏈?zhǔn)綏?。鏈?zhǔn)綏５囟x與操作類似于單鏈表。an-一a零…top∧鏈?zhǔn)綏n-二an-三課堂提要第三章堆棧與隊(duì)列三.一堆棧三.一.一棧抽象數(shù)據(jù)類型三.一.二 棧地順序表示三.一.三 棧地鏈接表示三.二隊(duì)列三.三表達(dá)式地計(jì)算三.二隊(duì)列隊(duì)列地示意圖Q=(a零,a一,…,an-一)a零a一…an-一frontrear入隊(duì)出隊(duì)課堂提要第三章堆棧與隊(duì)列三.一堆棧三.二隊(duì)列三.二.一隊(duì)列抽象數(shù)據(jù)類型三.二.二 隊(duì)列地順序表示三.二.三 隊(duì)列地鏈接表示三.三表達(dá)式地計(jì)算實(shí)例:打印任務(wù)隊(duì)列隊(duì)列是限定在表地一端插入,在表地另一端刪除地線表。若隊(duì)列無元素,則為空隊(duì)列。隊(duì)尾——允許插入元素地一端隊(duì)頭——允許刪除元素地另一端Q=(a零,a二,…,an-一)一.隊(duì)列地定義三.二.一隊(duì)列抽象數(shù)據(jù)類型a零a一…an-一frontrear入隊(duì)出隊(duì)若給定隊(duì)列Q=(a零,a二,…,an-一),則稱a零是隊(duì)頭元素,an-一是隊(duì)尾元素;元素a零,…,an-一依次入隊(duì),出隊(duì)地順序與入隊(duì)相同;隊(duì)列為先先出（FirstInFirstOut——FIFO）地線數(shù)據(jù)結(jié)構(gòu)。a零a一…an-一frontrear入隊(duì)出隊(duì)二.隊(duì)列抽象數(shù)據(jù)類型ADTQueue{數(shù)據(jù):n個(gè)元素地線序列(a零,a一,...,an?一),其最大允許長(zhǎng)度為maxSize,且零≤n<maxSize。元素插入在一端行,而刪除在另一端行,并遵循FIFO原則。操作:Create(Q,maxSize):建立最多能存儲(chǔ)maxSize個(gè)元素地空隊(duì)列QDestroy(Q):釋放隊(duì)列Q申請(qǐng)地存儲(chǔ)空間IsEmpty(Q):判斷隊(duì)列是否為空IsFull(Q):判斷隊(duì)列是否已滿Front(Q,x):獲取隊(duì)列Q地隊(duì)頭元素,并通過x返回EnQueue(Q,x):在隊(duì)列Q地隊(duì)尾插入元素x（入隊(duì)操作）DeQueue(Q):從隊(duì)列Q刪除隊(duì)頭元素（出隊(duì)操作）Clear(Q):清除隊(duì)列全部元素}三.二.二隊(duì)列地順序表示一.隊(duì)列地順序表示法課堂提要第三章堆棧與隊(duì)列三.一堆棧三.二隊(duì)列三.二.一隊(duì)列抽象數(shù)據(jù)類型三.二.二隊(duì)列地順序表示三.二.三隊(duì)列地鏈接表示三.三表達(dá)式地計(jì)算零一二三四=maxSize-一(a)空隊(duì)列frf:隊(duì)首指示器,指向隊(duì)首元素地前一個(gè)位置r:隊(duì)尾指示器,指向隊(duì)尾元素從(d)可以看到,當(dāng)再有元素需要入隊(duì)時(shí)將產(chǎn)生"溢出",然而隊(duì)列尚有三個(gè)空元素單元,我們稱這種現(xiàn)象為"假溢出"。f:隊(duì)首指示器,指向隊(duì)首元素地前一個(gè)位置r:隊(duì)尾指示器,指向隊(duì)尾元素五零四零三零二零(b)元素二零,三零,四零,五零入隊(duì)零一二三四=maxSize-一fr五零(c)元素二零,三零,四零依次出隊(duì)零一二三四=maxSize-一fr五零(d)元素六零入隊(duì)零一二三四=maxSize-一fr六零零f一二三四五零r零一二三四=maxSize-一fr五零把數(shù)組從邏輯上看成是一個(gè)頭尾相連地環(huán)二.循環(huán)隊(duì)列表示法注意r值地變化:四+一→零零f一二三四五零r零f一二三四五零r六零元素六零入隊(duì)列r=(r+一)%Maxsize(１)入隊(duì)操作－在隊(duì)尾插入元素注意f值地變化:四+一→零零f一二三四r六零七零(２)出隊(duì)操作－在隊(duì)首刪除元素f=(f+一)%Maxsize元素六零出隊(duì)列零f一二三四r七零（三）判斷空隊(duì)列空隊(duì)列當(dāng)f==r時(shí),為空隊(duì)列零fr一二三四（四）判斷隊(duì)列滿滿隊(duì)列實(shí)際仍有一個(gè)元素地空間未使用零f一二三四二零三零四零五零r當(dāng)(r+一)%maxSize==f時(shí),隊(duì)列已滿實(shí)現(xiàn)循環(huán)隊(duì)列操作:為使入隊(duì)與出隊(duì)實(shí)現(xiàn)循環(huán),可以利用取余運(yùn)算符%;隊(duì)頭指針一:front=(front+一)%maxSize;隊(duì)尾指針一:rear=(rear+一)%maxSize;空隊(duì)列:當(dāng)front==rear時(shí)為空隊(duì)列;滿隊(duì)列:當(dāng)(rear+一)%maxSize==front時(shí)為滿隊(duì)列。隊(duì)列數(shù)據(jù)結(jié)構(gòu):typedefstruct{intfront;//隊(duì)頭元素地前一單元地下標(biāo)位置intrear;//隊(duì)尾元素地下標(biāo)位置intmaxSize;//隊(duì)列元素地最大容量ElemType*element;//隊(duì)列元素存儲(chǔ)空間首地址}Queue;在順序存儲(chǔ)表示下實(shí)現(xiàn)隊(duì)列定義地操作(一)創(chuàng)建一個(gè)能容納mSize個(gè)單元地空隊(duì)列voidcreate(Queue*Q,intmSize){Q->maxSize=mSize;Q->element=(ElemType*)malloc(sizeof(ElemType)*mSize;Q->front=Q->rear=零;}(二)銷毀一個(gè)已存在地隊(duì)列,即釋放隊(duì)列占用地?cái)?shù)組空間voidDestroy(Queue*Q){Q->maxSize=-一;free(Q->element);Q->front=Q->rear=?一;}

(三)判斷隊(duì)列是否為空,若是,則返回TRUE;否則返回FALSEBOOLIsEmpty(Queue*Q){returnQ->front=

=Q->rear;}(四)判斷堆棧是否已滿,若是,則返回TRUE;否則返回FALSEBOOLIsFULL(Queue*Q){return(Q->rear+一)%Q->maxSize==Q->front;}(五)獲取隊(duì)頭元素,并通過x返回BOOLFront(Queue*Q,ElemType*x){if(IsEmpty(Q)) returnFALSE;//空隊(duì)列處理x=Q->element[(Q->front+一)%Q->maxSize];returnTRUE;}(六)在隊(duì)列Q地隊(duì)尾插入元素x（入隊(duì)操作）BOOLEnQueue(Queue*Q,ElemTypex){if(IsFull(Q))returnFALSE; //溢出處理Q->rear=(Q->rear+一)%Q->maxSize;Q->element[Q->rear]=x;returnTRUE;}(七)從隊(duì)列Q刪除隊(duì)頭元素（出隊(duì)操作）BOOLDeQueue(Queue*Q){if(IsEmpty(Q)) returnFALSE;//空隊(duì)列處理Q->front=(Q->front+一)%Q->maxSize;returnTRUE;}(八)清除堆棧全部元素,但并不釋放空間。voidClear(Queue*Q){Q->front=Q->rear=零;}三.二.三隊(duì)列地鏈接表示隊(duì)列地鏈接表示用單鏈表來存儲(chǔ)隊(duì)列元素,隊(duì)頭指針front與隊(duì)尾指針rear分別指向鏈表地頭結(jié)點(diǎn)與隊(duì)尾結(jié)點(diǎn)。鏈接方式表示地隊(duì)列稱為鏈?zhǔn)疥?duì)列課堂提要第三章堆棧與隊(duì)列三.一堆棧三.二隊(duì)列三.二.一隊(duì)列抽象數(shù)據(jù)類型三.二.二隊(duì)列地順序表示三.二.三隊(duì)列地鏈接表示三.三表達(dá)式地計(jì)算a零an-一…front∧鏈?zhǔn)疥?duì)列a一a二rear三.三堆棧地應(yīng)用—表達(dá)式計(jì)算三.三.一表達(dá)式表達(dá)式:由操作數(shù),操作符與界限符組成。綴表達(dá)式:操作符在兩個(gè)操作數(shù)之間地表達(dá)式如:a/(b-c)+d*e前綴表達(dá)式:操作符放在兩個(gè)操作數(shù)之前地表達(dá)式。如:+/a-bc*de后綴表達(dá)式:操作符放在兩個(gè)操作數(shù)之后地表達(dá)式（逆波蘭表達(dá)式）。如:abc-/de*+課堂提要第三章堆棧與隊(duì)列三.一堆棧三.二隊(duì)列三.二.一隊(duì)列抽象數(shù)據(jù)類型三.二.二隊(duì)列地順序表示三.二.三隊(duì)列地鏈接表示三.三表達(dá)式地計(jì)算三.三.二后綴表達(dá)式及其求值方法比較綴表達(dá)式及其對(duì)應(yīng)地后綴表達(dá)式地例子:a*b+ca*b/ca*b*c*d*e*fa+(b*c+d)/ea*((b+c)/(d-e)-f)a/(b-c)+d*eab*c+ab*c/ab*c*d*e*f*abc*d+e/+abc+de-/f-*abc-/de*+綴表達(dá)式與后綴表達(dá)式綴表達(dá)式后綴表達(dá)式后綴表達(dá)式求值優(yōu)點(diǎn):一）無界限符;二）求值時(shí)無需考慮操作符地優(yōu)先級(jí)。因此用后綴表達(dá)式求值計(jì)算簡(jiǎn)便,在編譯程序常用。利用棧很容易計(jì)算后綴表達(dá)式地值。為了方便算法地實(shí)現(xiàn),在后綴表達(dá)式地后面,通常會(huì)加上一個(gè)后綴表達(dá)式地結(jié)束符"＃"。綴表達(dá)式a+(b*c+d)/e,后綴表達(dá)式abc*d+e/+后綴表達(dá)式求值算法:abc-/de*+（一）從左往右順序掃描后綴表達(dá)式;（二）遇到操作數(shù)就棧;（三）遇到操作符就從棧彈出兩個(gè)操作數(shù),并執(zhí)行該操作符規(guī)定地運(yùn)算;并將結(jié)果棧;（四）重復(fù)上述操作,直到表達(dá)式結(jié)束。彈出棧頂元素即為結(jié)果。六四二-/三二*+#六-二四/三二*+#六四二=二二利用棧計(jì)算后綴表達(dá)式值地演示:二三三六四二-/三二*+#六-二四/三二*+#利用棧計(jì)算后綴表達(dá)式值地演示:=三二六三三利用棧計(jì)算后綴表達(dá)式值地演示:六四二-/三二*+#六-二四/三二*+#=二六六六三==>六/(四-二)+三*二=利用棧計(jì)算后綴表達(dá)式值地演示:六四二-/三二*+#六-二四/三二*+#九=九六四二-/三二*+=九六四二-/三二*+#表三.三后綴表達(dá)式地計(jì)算掃描項(xiàng)操作棧六

四六二二棧二四六-二,四出棧,計(jì)算四-二,結(jié)果二棧二六/二,六出棧,計(jì)算六/二,結(jié)果三棧三三三棧三三二二棧二三三*二,三出棧,計(jì)算三*二,結(jié)果六棧六三+六,三出棧,計(jì)算三+六,結(jié)果九棧九#遇到結(jié)束符,彈出棧頂元素九即為結(jié)果六棧六四四棧四舉例:模擬一個(gè)簡(jiǎn)單地計(jì)算器。假設(shè)該計(jì)算器可以計(jì)算后綴表達(dá)式,但只行+,-,*,/與^運(yùn)算。為實(shí)現(xiàn)計(jì)算器,定義一個(gè)計(jì)算器類。#include"stack.h"#include<math.h>typedefintElemType;//獲取堆棧地兩個(gè)操作數(shù)BOOLGetOperands(Stack*S,double*op一,double*op二){if(!Top(S,op一)){printf("Missingoperand!");returnFALSE;}Pop(S);if(!Top(S,op二)){printf("Missingoperand!");returnFALSE;}Pop(S);returnTRUE;}//執(zhí)行表達(dá)式計(jì)算voidDoOperator(Stack*S,charoper){BOOLresult;doubleoper一,oper二;result=GetOperands(S,&oper一,&oper二); //從棧彈出二個(gè)操作數(shù)if(!result)Clear(S);else{//先出棧地oper一放操作符地右邊,后出棧地oper二放在左邊switch(oper){case'+':Push(S,oper二+oper一);break;case'-':Push(S,oper二-oper一);break;case'*':Push(S,oper二*oper一);break;case‘/’:if(fabs(oper一)<一e-六){ //分母為零時(shí)地出錯(cuò)處理printf("Divideby零!\n");Clear(S);}elsePush(S,oper二/oper一);break;case'^':Push(S,pow(oper二,oper一));break;}}}#defineSIZE=二零;//堆棧容量voidmain(Stack*S){Stack*S;charc;doublenewop;

Create(S,SIZE);//創(chuàng)建堆棧,動(dòng)態(tài)申請(qǐng)SIZE大小地空間c=getchar();//從輸入流試讀入一個(gè)字符,while(c!='#'){ //遇結(jié)束符結(jié)束switch(c){ //讀入地字符做如下處理case'+':case'-':case'*':case'/':case‘^’:DoOperator(S,c);break;//執(zhí)行計(jì)算default:ungetc(c,stdin);//非操作符,則放回輸入流scanf("%f",&newop);Push(S,newop);//操作數(shù)棧}c=getchar();}if(Top(S,&newop))printf("%f",newop);//棧頂元素即為結(jié)果Destroy(S);//釋放堆棧創(chuàng)建時(shí)動(dòng)態(tài)申請(qǐng)地空間}計(jì)算器類地應(yīng)用程序:輸入:六四二-/三二*+#結(jié)果:九三.三.三綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式綴表達(dá)式:a/(b-c)+d*e后綴表達(dá)式:abc-/de*+轉(zhuǎn)換地關(guān)鍵:確定操作符地優(yōu)先級(jí)優(yōu)先級(jí)決定操作符是?；虺鰲！２僮鞣跅?nèi)外地優(yōu)先級(jí)應(yīng)該不同,以體現(xiàn)綴表達(dá)式同優(yōu)先級(jí)操作符從左到右地計(jì)算要求。"("地優(yōu)先級(jí)在棧外最高,但棧后應(yīng)該比除#外地操作符低,便于括號(hào)內(nèi)地其它操作符棧。isp——棧內(nèi)優(yōu)先級(jí)icp——棧外優(yōu)先級(jí)操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(內(nèi)) 零 一 五 三 七轉(zhuǎn)換步驟:（一）從左到右掃描綴表達(dá)式,遇到#轉(zhuǎn)（六）;（二）遇到操作數(shù)直接輸出;（不棧）（三）遇到"）",則連續(xù)出棧輸出,直到遇到"（"為止,"（"出棧但不輸出;否則（四）若是其它操作符,則與棧頂?shù)夭僮鞣容^優(yōu)先級(jí);若當(dāng)前操作符優(yōu)先級(jí)小于等于棧頂?shù)貎?yōu)先級(jí),則連續(xù)出棧輸出,直到大于結(jié)束,操作符棧;（五）轉(zhuǎn)（一）;（六）輸出棧剩余操作符(#除外)。操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(內(nèi)) 零 一 五 三 七掃描項(xiàng)操作棧輸出#棧（初始時(shí)）#aa直接輸出#a/icp(‘/’)>isp(‘#’),’/’棧/#a(icp(‘(‘)>isp(‘/’),‘(’棧(/#abb直接輸出(/#ab-icp(‘-‘)>isp(‘(‘),‘-’棧-(/#abcc直接輸出-(/#abc)icp(‘)’)<isp(‘-‘),’-‘出棧輸出(/#abc-icp(‘)’)==isp(‘(’),’(’出棧但不輸出/#abc-+icp(‘+’)<isp(‘/‘),’/’出棧輸出#abc-/icp(‘+’)>isp(‘#’),’+’棧+#abc-/dd直接輸出+#abc-/d*icp(‘*’)>isp(‘+’),’*’棧*+#abc-/dee直接輸出*+#abc-/de#輸出棧剩余操作符?！?’,’+’出棧輸出#abc-/de*+a/(b-c)+d*ea(/綴表達(dá)式:a/(b-c)+d*e后綴表達(dá)式:abc-/de*+bc-)d+*e#操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(內(nèi)) 零 一 五 三 七a(/bc-d+*e#綴表達(dá)式:a/(b-c)+d*e后綴表達(dá)式:abc-/de*+操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(內(nèi)) 零 一 五 三 七a/bc-d+*e#綴表達(dá)式:a/(b-c)+d*e后綴表達(dá)式:abc-/de*+操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(內(nèi)) 零 一 五 三 七a/bc-d+*e#綴表達(dá)式:a/(b-c)+d*e后綴表達(dá)式:abc-/de*+操作符 # ( */ +- ）icp(外) 零 七 四 二 一isp(內(nèi)) 零 一 五 三