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

第三章棧和隊(duì)列兩種特殊的線性表回顧線性表 順序存儲(chǔ)的線性表 鏈表表示的線性表特點(diǎn)：插入和刪除操作可以在表的任何位置進(jìn)行。A123n12nL問(wèn)題棧（LIFO）——LastInFirstOut隊(duì)列（FIFO）——FirstInFirstOut問(wèn)：對(duì)這些數(shù)據(jù)的操作與線性表有哪些相同和不同？答：都是線性結(jié)構(gòu)的數(shù)據(jù)操作方式的差異134N2入口出口LIFO134N2出口入口FIFO3.1棧本節(jié)的主要內(nèi)容：

1.棧的定義

2.堆棧的表示和實(shí)現(xiàn)

3.堆棧的操作方式

4.順序棧和鏈棧的定義及其操作1.棧的抽象數(shù)據(jù)類型定義火車站的調(diào)度情況

一個(gè)有終結(jié)點(diǎn)火車道，每節(jié)車廂進(jìn)出該車道的規(guī)則應(yīng)該是怎樣的呢？必須遵循LIFO

原則123進(jìn)棧出棧棧：一個(gè)只能在棧頂進(jìn)行插入和刪除的線性表，其特征為L(zhǎng)IFO

空棧：不含元素的空表

遵循LIFO(lastinfirstout)的線性表。 思考：按此規(guī)則，如果進(jìn)棧的車廂序列為1，2，3，而且兩側(cè)鐵道均為單向行駛道，那么它們出棧的順序會(huì)有幾種，分別是怎樣排列的?抽象數(shù)據(jù)類型：

ADTStack{數(shù)據(jù)對(duì)象，數(shù)據(jù)關(guān)系同線性表

基本操作：

InitStack(&S),DestroyStock(&S),

ClearStack(&S),StackEmpty(S),

StackLength(&S),GetTop(S),Push(&S,e),Pop(&S,&e),

StackTraverse(S,visit())}

棧的表示和實(shí)現(xiàn)棧的表示：（1）順序棧：棧的順序存儲(chǔ)

優(yōu)點(diǎn)：處理方便；缺點(diǎn)：數(shù)組大小固定，易造成內(nèi)存資源的浪費(fèi)。（2）鏈棧：棧的動(dòng)態(tài)存儲(chǔ)

優(yōu)點(diǎn):能動(dòng)態(tài)改變鏈表的長(zhǎng)度，有效利用內(nèi)存資源；缺點(diǎn)：處理較為復(fù)雜。問(wèn)：TOP的作用是什么？順序棧的表示和實(shí)現(xiàn)順序表示#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;

typedef

struct{

SElemType*base;

SElemType*top;

int

stacksize;}SqStack;

其中stacksize表示棧當(dāng)前可以使用的最大容量。base為棧底，top為棧頂。棧頂指針指向棧頂元素的下一個(gè)位置（即下次壓棧時(shí)元素所放的位置）順序棧的結(jié)構(gòu)top指向壓棧時(shí)下一個(gè)元素將要存放的位置。top減一指向彈棧時(shí)下一個(gè)元素的取值位置。棧空的條件：top=base棧滿的條件：top-base>=stacksizetoptopbase空棧base非空非滿棧topABCABCbase滿棧DE基本操作的實(shí)現(xiàn)：初始化棧StatusInitStack(SqStack&S){//構(gòu)造一個(gè)空棧

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack壓棧:StatusPush(SqStack&S,SElemTypee){//元素e插入到棧中，成為新的棧頂

if(S.top-S.base>=S.stacksize)//棧滿

{newbase=(SElemType*)realloc

(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!newbase)exit(OVERFLOW);elseS.base=newbase;S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;}//if*S.top++=e;returnOK;}//Push出棧:StatusPop(SqStack&S,SElemType&e){//從棧頂讀取數(shù)據(jù)放入e內(nèi)，棧中下一元素所在位置成為新的棧頂

if（S.top==S.base）returnERROR;//棧空

e=*--S.top;returnOK;}//Pop注意top的操作順序和值的變化。壓棧：valuetop;top++;

彈棧：top--;top->value;鏈棧的結(jié)構(gòu)和表示定義棧結(jié)構(gòu)Typedef

structstack_node{

Elemtypedata;

structstack_node*next;}LinkStack;LinkStack*stk;問(wèn)：在這里為什么沒(méi)有用到top指針？這樣對(duì)棧結(jié)構(gòu)的定義有否影響？1^728stk棧頂棧底鏈棧的操作入棧PUSH()StatusPUSH(LinkStack*stk,Elemtypex){

LinkStack*top; top=malloc(sizeof(LinkStack)); top->data=x; top->next=*stk; *stk=top;}問(wèn)：在這里top指針的作用是什么？1^8stkxtop1^8stkxtop課堂練習(xí)：鏈棧的出棧操作取棧頂元素GETTOP()

3.2棧的應(yīng)用舉例1.數(shù)制轉(zhuǎn)換10--〉2，逐步除二，得余取反序用算法實(shí)現(xiàn)求任意非負(fù)十進(jìn)制數(shù)的八進(jìn)制數(shù) 分析：每次除8，余數(shù)壓棧，結(jié)束后依次出棧即可

voidconversion(){//非負(fù)十進(jìn)制數(shù)轉(zhuǎn)化為八進(jìn)制數(shù)

InitStack(S);

scanf(“%d”,N);while(N){Push(S,N%8);N=N/8;}while（！StackEmpty(s)）{pop(s,e);printf(“%d”,e);}}//conversion2.括號(hào)匹配算法{}[]（）的配對(duì)問(wèn)題。

[(5+(2-6)+10)+6]*2（正確）

[(5+(2-6)+10]+6)*2（╳）

((5+2-6)+10)+6)*2（╳）判斷的標(biāo)準(zhǔn)：

方法：見(jiàn)到左括號(hào)壓棧，見(jiàn)到右括號(hào)彈棧，并和彈出的數(shù)據(jù)配對(duì)。編寫算法：假設(shè)表達(dá)式結(jié)束符為#,試寫出判斷表達(dá)式是否正確的算法intMatchJudge(){//匹配返回1，不匹配返回0

InitStack(S);

scanf(“%c”,ch);while(ch!=“#”){if(ch==“(”||ch==“[”||ch==“{”)push(s,ch);if(ch==“)”||ch==“]”||ch==“}”）{ifStackEmpty(S)return0; pop(s,e);if(e與ch不匹配)return0;}

scanf(“%c”,ch);}//whileifStackEmpty(s)return1elsereturn0;}//MatchJudge算法：先乘除，后加減，括號(hào)先。（從左到右）算符優(yōu)先算法：利用運(yùn)算優(yōu)先關(guān)系的規(guī)定來(lái)實(shí)現(xiàn)對(duì)表達(dá)式的編譯或解釋執(zhí)行。（算符優(yōu)先關(guān)系參看P53）比較兩個(gè)表達(dá)式的計(jì)算過(guò)程：4＋2×15－10/5和4＋2×(15－10)/5分析：如何利用棧實(shí)現(xiàn)計(jì)算過(guò)程？設(shè)置兩個(gè)工作棧：OPTR(運(yùn)算符棧)和OPND(操作數(shù)棧)

OPND初始為空，OPTR棧底置“＃” 依次讀入表達(dá)式中的字符： 操作數(shù)壓OPND棧； 運(yùn)算符：與OPTR棧頂元素比較優(yōu)先級(jí)表達(dá)式求值問(wèn)題OperandType

EvaluateExpression(){//算符優(yōu)先算法求表達(dá)式的值

InitStack(OPTR);Push(OPTR,‘＃’)；//OPTR運(yùn)算符棧

InitStack(OPND);c=getchar();//OPND操作數(shù)棧

while(c!=‘#’||GetTop(OPTR)!=‘#’){ if(!In(c,OP)){Push(OPND,c);c=getchar()}//操作數(shù)入棧OPND elseswitch(Precede(GetTop(OPTR),c)){ case’<’://棧頂運(yùn)算符優(yōu)先級(jí)低

Push(OPTR,c)；c=getchar();break; case’=’://去括號(hào)

Pop(OPTR,x);c=getchar();break; case’>’: //退棧并計(jì)算結(jié)果入棧 Pop(OPTR,theta); Pop(OPND,a);Pop(OPND,b); Push(OPND,Operate(a,theta,b));break; }//switch }//while returnGetTop(OPND);}//EvaluateExpression

表達(dá)式的前綴、中綴、后綴表示問(wèn)題：對(duì)a+b的表示有：前綴+ab、中綴a+b、后綴ab+；各種表示方式對(duì)如a+b*c運(yùn)算的優(yōu)先次序的表示： 前綴+a*bc,中綴a+b*c,后綴abc*+編譯中，需要將表達(dá)式化成前綴、后綴方式 例如#a+(b+(c/d-e))*f#轉(zhuǎn)化為后綴的表示方法結(jié)果：abcd/e-+f*+課堂練習(xí)：寫出a+(b+(c/d-e))*f的前綴、中綴、后綴表示。棧在遞歸調(diào)用中的作用遞歸函數(shù)：直接或間接調(diào)用自身的函數(shù)。遞歸的應(yīng)用：遞歸定義的數(shù)學(xué)函數(shù)數(shù)據(jù)結(jié)構(gòu)：二叉樹、廣義表，結(jié)構(gòu)本生的遞歸性質(zhì)用遞歸解決更簡(jiǎn)單的問(wèn)題，如Hanoi塔問(wèn)題。遞歸調(diào)用是一種顯式的自嵌套調(diào)用，將大規(guī)模數(shù)據(jù)問(wèn)題轉(zhuǎn)化為小規(guī)模數(shù)據(jù)問(wèn)題，調(diào)用時(shí)遵循“后調(diào)用先返回”的原則。系統(tǒng)在遞歸的實(shí)現(xiàn)上實(shí)際使用了棧為潛在的工具。3.3棧與遞歸的實(shí)現(xiàn)例：漢諾塔問(wèn)題有XYZ三塔座，X上插有n個(gè)直徑不同、由小到大的圓盤。要求借助Y將其全部移到Z上，按照原來(lái)的順序疊放。移動(dòng)規(guī)則：每次移動(dòng)一個(gè)；任何時(shí)刻都是小盤在上，大盤在下。分析：當(dāng)n=1時(shí)，直接移動(dòng)即可；當(dāng)n>=2時(shí)，首先將上面的n-1個(gè)圓盤移至Y，第n個(gè)放到Z；然后的問(wèn)題就是n-1個(gè)圓盤的問(wèn)題提示：雖然n-1個(gè)圓盤的問(wèn)題與n個(gè)圓盤的問(wèn)題相同，但規(guī)模變小。XYZ算法：voidhanoi(intn,charx,chary,charz){ if(n==1) move(x,1,z); else{ hanoi(n-1,x,z,y) move(x,n,z); hanoi(n-1,y,x,z) }}問(wèn)題：遞歸函數(shù)是如何執(zhí)行的，棧在其中的作用是什么？3.4

隊(duì)列

隊(duì)列：一個(gè)只能在隊(duì)首進(jìn)行刪除、隊(duì)尾進(jìn)行插入的線性表，其特征為FIFO(先進(jìn)先出)。關(guān)鍵基本操作：出隊(duì)和入隊(duì)

抽象數(shù)據(jù)類型：

ADTStack{數(shù)據(jù)對(duì)象，數(shù)據(jù)關(guān)系同線性表

基本操作：

InitQueue(&Q),DestroyQueue(&Q),

ClearQueue(&Q),QueueEmpty(Q),

QueueLength(&S),GetHead(S),

EnQueue(&Q,e),DeQueue(&S,&e),

QueueTraverse(Q,visit())}隊(duì)列的表示和實(shí)現(xiàn)鏈?zhǔn)疥?duì)列

typedef

struct

Qnode{

QElemTypedata;

struct

Qnode*next;}Qnode,*QueuePtr;

typedef

struct{

QueuePtrfront;

QueuePtrrear;}LinkQueue;課堂練習(xí)：鏈隊(duì)列的操作入對(duì)列、出隊(duì)列Q.frontQ.rear^鏈隊(duì)列結(jié)構(gòu)入隊(duì)列：在隊(duì)尾插入P=LinkQueue

malloc(sizeof(Qnode))P->next=NULL;Q.rear->next=p;Q.rear=P;出隊(duì)列：在隊(duì)頭刪除

r=Q.front->next; Q.front->next=r->next; free(r);Q.frontQ.rear^P順序隊(duì)列

#defineMAXQSIZE100

typedef

struct{

QElemType*base;

intfront;

intrear;}SqQueue;

其中base為連續(xù)空間首地址，front為隊(duì)首，rear為隊(duì)尾。為什么用循環(huán)隊(duì)列來(lái)實(shí)現(xiàn)順序隊(duì)列？rearfront空隊(duì)front非空非滿隊(duì)1rearABCC滿隊(duì)DECfront非空非滿隊(duì)2Drearrearfront順序隊(duì)列的結(jié)構(gòu)——循環(huán)隊(duì)列：空隊(duì)：初始化隊(duì)列時(shí)，兩個(gè)指針rear＝front＝0入隊(duì)：隊(duì)尾插入元素，尾指針rear后移出隊(duì)：隊(duì)頭刪除元素，頭指針