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

第3章棧和隊(duì)列學(xué)習(xí)要點(diǎn)

從數(shù)據(jù)結(jié)構(gòu)上看，棧和隊(duì)列也是線性表，不過是兩種特殊的線性表。棧只允許在表的一端進(jìn)行插入或刪除操作，而隊(duì)列只允許在表的一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作，棧和隊(duì)列也可以被稱作為操作受限的線性表。通過本章的學(xué)習(xí)，應(yīng)掌握棧和隊(duì)列的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及棧和隊(duì)列的基本運(yùn)算以及實(shí)現(xiàn)算法。3.1棧什么是棧？

釋義：供儲存貨物的建筑物。設(shè)想有一個直徑不大、一端開口一端封閉的竹筒。有若干個寫有編號的小球，小球的直徑比竹筒的直徑略小。現(xiàn)在把不同編號的小球放到竹筒里面，可以發(fā)現(xiàn)一種規(guī)律：先放進(jìn)去的小球只能后拿出來，反之，后放進(jìn)去的小球能夠先拿出來。3.1棧1000：×××1001：×××1002：×××1003：×××1004：call20001005：×××1006：×××1007：×××1008：ENDS2000：×××2001：×××2002：×××2003：call30002004：×××2005：×××2006：RET3000：×××3001：×××3002：×××3003：×××3004：call40003005：×××3006：RET4000：×××4001：×××4002：×××4003：×××4004：×××4005：×××4006：×××4007：RET主程序子程序1子程序2子程序3(a1,a2,...,ai-1,ai

,ai+1,…,an)插入刪除3.1棧

棧是限定僅能在表的一端進(jìn)行插入、刪除操作的線性表。能進(jìn)行插入和刪除的一端為棧頂（top），另一端為棧底（bottom）。

稱插入操作為進(jìn)棧，刪除操作為出棧。進(jìn)棧出棧操作只能在棧頂進(jìn)行。棧頂棧底第一個進(jìn)棧的元素在棧底；最后一個進(jìn)棧的元素在棧頂；第一個出棧的元素為棧頂元素；最后一個出棧的元素為棧底元素。棧的特點(diǎn)后進(jìn)先出(LIFO)出棧進(jìn)棧棧的示意圖an：：a2a11.初始化操作InitStack(&S)

功能：構(gòu)造一個空棧S2.銷毀棧操作DestroyStack(&S)

功能：銷毀一個已存在的棧3.置空棧操作ClearStack(&S)

功能：將棧S置為空棧4.取棧頂元素操作GetTop(S,&e)

功能：取棧頂元素，并用e返回棧的基本操作5.進(jìn)棧操作Push(&S,e)

功能：元素e進(jìn)棧6.出棧操作Pop(&S,&e)

功能：棧頂元素退棧，并用e返回7.判空操作StackEmpty(S)

功能：若棧S為空，則返回True，否則返回False棧的基本操作棧的表示和實(shí)現(xiàn)——順序存儲#defineSTACK_INIT_SIZE100//棧存儲空間的初始分配量

#defineSTACKINCREMENT10//棧存儲空間的分配增量

typedef

struct{

SElemType*base;//棧空間基址

SElemType*top;//棧頂指針

intstacksize;//當(dāng)前分配的?？臻g大小

}SqStack;

SqStackS;//S是存放棧的結(jié)構(gòu)變量棧的表示和實(shí)現(xiàn)說明

base稱為棧底指針，始終指向棧底；當(dāng)base=NULL時，表明棧結(jié)構(gòu)不存在。

top為棧頂指針

top的初始值指向棧底，即top=base

空棧：當(dāng)top=base時為?？盏臉?biāo)記當(dāng)棧非空時，top的位置是指向當(dāng)前棧頂元素的下一個位置

stacksize——當(dāng)前?？墒褂玫淖畲笕萘縎.stacksizeS.topS.base10099nn-1n-210anan-1a2a1約定棧頂指針指向棧頂元素的下一個位置當(dāng)棧用順序結(jié)構(gòu)存儲時，棧的基本操作如建空棧、進(jìn)棧、出棧等如何實(shí)現(xiàn)？？順序棧的圖示baseAABCDEAB空棧A進(jìn)棧BCDE進(jìn)棧EDC出棧順序棧的操作圖示topbasetopbasebasetoptop初始化操作InitStack(SqStack&S)

參數(shù)：S是存放棧的結(jié)構(gòu)變量功能：建一個空棧SS.stacksizeS.topS.base10099nn-1n-210順序棧的基本操作初始化操作算法StatusInitStack(SqStack&S){

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//為順序棧動態(tài)分配存儲空間

if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}//InitStack順序棧的基本操作

銷毀棧操作

DestroyStack(SqStack&S)

功能：銷毀一個已存在的棧順序棧的基本操作99nn-1n-210anan-1a2a1S.stacksizeS.topS.base100NULL0NULL銷毀操作算法StatusDetroyStack(SqStack&S){if(!S.base)returnERROR;//若棧未建立(尚未分配?？臻g)

free(S.base);//回收?？臻g

S.base=S.top=NULL;

S.stacksize=0;

returnOK;

}//DetroyStack順序棧的基本操作置空棧操作ClearStack(SqStack&S)

功能：將棧S置為空棧順序棧的基本操作99nn-1n-210anan-1a2a1S.stacksizeS.topS.base100S.stacksizeS.topS.base99nn-1n-210anan-1a2a1100置空置空操作算法StatusClearStack(SqStack&S){if(!S.base)returnERROR;//若棧未建立(尚未分配棧空間)

S.top=S.base;

returnOK;

}//ClearStack順序棧的基本操作取棧頂元素操作GetTop(SqStackS,SElemType&e)

功能：取棧頂元素，并用e返回順序棧的基本操作99nn-1n-210anan-1a2a1S.stacksizeS.topS.base100ean取棧頂元素操作算法StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;//棧空

e=*(S.top-1);

returnOK;

}//GetTop順序棧的基本操作

進(jìn)棧操作Push(SqStack&S,ElemTypee)

功能：元素e進(jìn)棧順序棧的基本操作99nn-1n-210anan-1a2a1S.stacksizeS.topS.base100e元素進(jìn)棧S.stacksizeS.topS.base99nn-1n-210anan-1a2a1100e進(jìn)棧操作算法StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//棧滿，追加存儲空間

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}

*S.top++=e;//*S.top=e；S.top++;

returnOK;}//Push順序棧的基本操作

出棧操作Pop(SqStack&S,ElemType&e)

功能：棧頂元素退棧，并用e返回順序棧的基本操作棧頂元素進(jìn)棧99nn-1n-210anan-1a2a1S.stacksizeS.topS.base100S.stacksizeS.topS.base99nn-1n-210anan-1a2a1100ean出棧操作算法StatusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;//?？?/p>

e=*--S.top;//--S.top;

e=*S.top;

returnOK;

}//Pop順序棧的基本操作在前面學(xué)習(xí)了線性鏈表的插入、刪除操作算法，不難寫出鏈?zhǔn)綏３跏蓟?、進(jìn)棧、出棧等操作的算法。DatanextS棧頂棧底an-2a1an-1an棧的表示和實(shí)現(xiàn)——鏈?zhǔn)酱鎯Σ粠ь^結(jié)點(diǎn)的單鏈表，其插入和刪除操作僅限制在表頭位置上進(jìn)行。鏈表的頭指針即棧頂指針。棧的表示和實(shí)現(xiàn)——鏈?zhǔn)酱鎯Σ迦氩僮鳎簆->next=s；s=p。刪除操作：q=s；s=s->next；free(q)。s棧頂棧底anan-1……a1∧1.數(shù)制轉(zhuǎn)換p48算法3.12.行編輯程序p50算法3.23.表達(dá)式求值p53~p54算法3.43.2棧的應(yīng)用舉例

數(shù)制轉(zhuǎn)換

N=(N/d)×d+N%d(d代表d進(jìn)制數(shù))

例如：(1348)10=(2504)8

，其運(yùn)算過程如下：

NN/8N%8

13481684

168210

2125

202輸出順序計(jì)算順序voidconversion(){InitStack(S);

scanf("%d",&N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);

printf("%d",e);}}//conversion3.2棧的應(yīng)用舉例(a1,a2,...,ai-1,ai

,ai+1,…,an)插入刪除3.4隊(duì)列什么是隊(duì)列?

隊(duì)列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插入的線性表，能進(jìn)行插入的一端稱為隊(duì)尾，能進(jìn)行刪除的一端稱為隊(duì)頭。稱插入操作為入隊(duì)，刪除操作為出隊(duì)。

a1

a2

a3…………an隊(duì)頭隊(duì)尾出隊(duì)列第一個入隊(duì)的元素在隊(duì)頭最后一個入隊(duì)的元素在隊(duì)尾第一個出隊(duì)的元素為隊(duì)頭元素最后一個出隊(duì)的元素為隊(duì)尾元素進(jìn)隊(duì)列隊(duì)列的特點(diǎn)先進(jìn)先出

(FIFO)

隊(duì)列的示意圖

隊(duì)列的基本操作1.初始化操作InitQueue(&Q)

功能：構(gòu)造一個空隊(duì)列Q2.銷毀操作DestroyQueue(&Q)

功能：銷毀已存在隊(duì)列Q

3.置空操作ClearQueue(&Q)

功能：將隊(duì)列Q置為空隊(duì)列4.判空操作QueueEmpty(Q)

功能：若隊(duì)列Q為空，則返回True，否則返回False

隊(duì)列的基本操作5.取隊(duì)頭元素操作GetHead(Q,&e)

功能：取隊(duì)頭元素，并用e返回6.入隊(duì)操作EnQueue(&Q,e)

功能：將元素e插入Q的隊(duì)尾7.出隊(duì)操作DeQueue(&Q,&e)

功能：刪除Q的隊(duì)頭元素空鏈隊(duì)列Q.frontQ.rear∧鏈隊(duì)列——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)∧J1J2JnQ.frontQ.rear非空鏈隊(duì)列1.鏈隊(duì)列表示2.鏈隊(duì)列的類型定義

typedef

struct

QNode{//鏈隊(duì)列結(jié)點(diǎn)的類型定義

QElemTypedata;

struct

QNode*next;}QNode,*QueuePtr;

typedef

struct{//鏈隊(duì)列的表頭結(jié)點(diǎn)的的類型定義

QueuePtrfront;//隊(duì)頭指針，指向鏈表的頭結(jié)點(diǎn)

QueuePtrrear;//隊(duì)尾指針，指向隊(duì)尾結(jié)點(diǎn)

}LinkQueue;鏈隊(duì)列——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)3.鏈隊(duì)列的有關(guān)操作空隊(duì)Q.frontQ.rear∧XQ.front∧Q.rearX入隊(duì)YQ.front∧Q.rearY入隊(duì)XYQ.front∧Q.rearX出隊(duì)XY出隊(duì)Q.frontQ.rear∧鏈隊(duì)列——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)鏈隊(duì)列初始化StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}鏈隊(duì)列的有關(guān)操作Q.frontQ.rear∧鏈隊(duì)列的銷毀StatusDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}鏈隊(duì)列的有關(guān)操作鏈隊(duì)列的插入(入隊(duì))StatusEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e; p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}鏈隊(duì)列的有關(guān)操作鏈隊(duì)列的刪除(出隊(duì))StatusDeQueue(LinkQueue&Q,ElemType&e){if(Q.front==Q.rear)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); returnOK;}鏈隊(duì)列的有關(guān)操作

判斷鏈隊(duì)列是否為空StatusQueueEmpty(LinkQueueQ){ if(Q.front==Q.rear)returnTrue; returnFalse;}

取鏈隊(duì)列的第一個元素結(jié)點(diǎn)StatusGetHead(LinkQueue

Q,QElemType&e){ if(QueueEmpty(Q))returnERROR; e=Q.front->next->data; returnOK;}鏈隊(duì)列的有關(guān)操作

隊(duì)列的順序存貯結(jié)構(gòu)#defineMAXSIZE100//最大隊(duì)列長度

typedef

struct{

QElemType*base;//初始化時動態(tài)分配存儲空間的基址

int

front;//隊(duì)頭指針，指向隊(duì)頭元素

intrear;//隊(duì)尾指針，指向隊(duì)尾元素的下一個位置}SqQueue;循環(huán)隊(duì)列——隊(duì)列的順序表示和實(shí)現(xiàn)初始狀態(tài)為front=rear=0；每插入一個元素尾指針增1，每刪除一個元素，頭指針增1。順序隊(duì)列的有關(guān)操作空隊(duì)列Q.front012345Q.rearJ1J2J3J1,J2和J3相繼入隊(duì)列012345Q.frontQ.rearQ.frontJ3J1,J2相繼出隊(duì)列012345Q.rearJ3J4,J5,J6相繼入隊(duì)列012345Q.frontJ4J5J6Q.rear此時又有J7入隊(duì),該怎么辦？

？進(jìn)隊(duì)時，將新元素按Q.rear指示位置加入，再將隊(duì)尾指針增1，Q.rear=Q.rear+1。

出隊(duì)時，將下標(biāo)為Q.front的元素取出，再將隊(duì)頭指針增1，Q.front=Q.front+1。

隊(duì)滿時再進(jìn)隊(duì)將溢出出錯；隊(duì)空時再出隊(duì)作隊(duì)空處理。上圖為“假溢”。有關(guān)操作具體說明什么叫“假溢出”？如何解決？在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。解決假溢出的途徑———采用循環(huán)隊(duì)列將順序隊(duì)列假想為一個環(huán)狀的空間。隊(duì)空、隊(duì)滿都有Q.front=Q.rear如何判斷循環(huán)隊(duì)列隊(duì)空、隊(duì)滿？

？循環(huán)隊(duì)列Q.frontQ.rearJ6J4J53

124

05J7Q.rear54

03

12Q.frontJ6J7J8J9J4J5隊(duì)滿Q.rearQ.front540312隊(duì)空解決方法1.

另設(shè)一個標(biāo)志位tag讓刪除動作使其為1，插入動作使其為0，tag=1時，導(dǎo)致front=rear為隊(duì)空；tag=0時，導(dǎo)致front=rear則為隊(duì)滿。2.

用一個計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)(即隊(duì)列長度)；3.

少用一個存儲單元，隊(duì)滿條件：Q.front=Q.rear+1。隊(duì)頭、隊(duì)尾指針加1，可用取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1:Q.front=(Q.front+1)%MAXSIZE;

隊(duì)尾指針進(jìn)1:Q.rear=(Q.rear+1)%MAXSIZE;

隊(duì)列初始化：Q.front=Q.rear=0;

隊(duì)空條件：Q.front==Q.rear;

隊(duì)滿條件：(Q.rear+1)%MAXSIZE==Q.front;

隊(duì)列長度：(Q.rear-Q.front+MAXSIZE)%MAXSIZE。有關(guān)循環(huán)隊(duì)列操作說明初始化操作InitQueue_Sq(SqQueue&Q)

功能：建一個空隊(duì)列Q

算法：StatusInitQueue_Sq(SqQueue&Q){

//構(gòu)造一個空隊(duì)列Q

Q.base=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));

if(!Q.base)exit(OVERFLOW);//存儲分配失敗

Q.front=Q.rear=0;

returnOK;}//InitQueue_Sq循環(huán)隊(duì)列操作Q.frontQ.rear540312

入隊(duì)操作EnQueue_Sq(SqQueue&Q,ElemTypee)

功能：將元素e插入隊(duì)尾循環(huán)隊(duì)列操作Q.frontQ.rear54

03

12J1J3J2eQ.frontQ.rear54

03

12J1J3J2元素e入隊(duì)前元素e入隊(duì)后入隊(duì)操作算法StatusEnQueue_Sq(SqQueue&Q,ElemTypee)

{if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;//隊(duì)滿

Q.base[Q.rear]=e;//將元素e插入隊(duì)尾

Q.rear=(Q.rear+1)%MAXSIZE;//修改隊(duì)尾指針

returnOK;

}//EnQueue_Sq循環(huán)隊(duì)列操作

出隊(duì)操作

DeQueue_Sq(SqQueue&Q,QElemType&e)

功能：刪除隊(duì)頭元素，用e返回其值循環(huán)隊(duì)列操作Q.frontQ.rear54

03

12J1J3J2出隊(duì)操作前Q.frontQ.rear54

03

12J1J3J2出隊(duì)操作后eJ1出隊(duì)操作算法

StatusDeQueue_Sq(SqQueue&Q,ElemType&e)

{//刪除隊(duì)頭元素，用e返回其值，并返回OK；否則返回ERRORif((Q.rear==Q.front)returnERROR;//隊(duì)空

e=Q.