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

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

釋義：供儲存貨物的建筑物。設(shè)想有一個直徑不大、一端開口一端封閉的竹筒。有若干個寫有編號的小球，小球的直徑比竹筒的直徑略小?，F(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棧的基本操作棧的表示和實現(xiàn)——順序存儲#defineSTACK_INIT_SIZE100//棧存儲空間的初始分配量

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

typedef

struct{

SElemType*base;//?？臻g基址

SElemType*top;//棧頂指針

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

}SqStack;

SqStackS;//S是存放棧的結(jié)構(gòu)變量棧的表示和實現(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)前棧可使用的最大容量S.stacksizeS.topS.base10099nn-1n-210anan-1a2a1約定棧頂指針指向棧頂元素的下一個位置當(dāng)棧用順序結(jié)構(gòu)存儲時，棧的基本操作如建空棧、進(jìn)棧、出棧等如何實現(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);//回收棧空間

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;//?？?/p>

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;//棧空

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

e=*S.top;

returnOK;

}//Pop順序棧的基本操作在前面學(xué)習(xí)了線性鏈表的插入、刪除操作算法，不難寫出鏈?zhǔn)綏３跏蓟⑦M(jìn)棧、出棧等操作的算法。DatanextS棧頂棧底an-2a1an-1an棧的表示和實現(xiàn)——鏈?zhǔn)酱鎯Σ粠ь^結(jié)點(diǎn)的單鏈表，其插入和刪除操作僅限制在表頭位置上進(jìn)行。鏈表的頭指針即棧頂指針。棧的表示和實現(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輸出順序計算順序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隊列什么是隊列?

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

a1

a2

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

(FIFO)

隊列的示意圖

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

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

功能：銷毀已存在隊列Q

3.置空操作ClearQueue(&Q)

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

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

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

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

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

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

typedef

struct

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

QElemTypedata;

struct

QNode*next;}QNode,*QueuePtr;

typedef

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

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

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

}LinkQueue;鏈隊列——隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)3.鏈隊列的有關(guān)操作空隊Q.frontQ.rear∧XQ.front∧Q.rearX入隊YQ.front∧Q.rearY入隊XYQ.front∧Q.rearX出隊XY出隊Q.frontQ.rear∧鏈隊列——隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)鏈隊列初始化StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}鏈隊列的有關(guān)操作Q.frontQ.rear∧鏈隊列的銷毀StatusDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}鏈隊列的有關(guān)操作鏈隊列的插入(入隊)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;}鏈隊列的有關(guān)操作鏈隊列的刪除(出隊)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;}鏈隊列的有關(guān)操作

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

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

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

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

typedef

struct{

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

int

front;//隊頭指針，指向隊頭元素

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

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

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

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

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

124

05J7Q.rear54

03

12Q.frontJ6J7J8J9J4J5隊滿Q.rearQ.front540312隊空解決方法1.

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

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

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

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

隊列初始化：Q.front=Q.rear=0;

隊空條件：Q.front==Q.rear;

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

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

功能：建一個空隊列Q

算法：StatusInitQueue_Sq(SqQueue&Q){

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

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

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

Q.front=Q.rear=0;

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

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

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

03

12J1J3J2eQ.frontQ.rear54

03

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

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

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

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

returnOK;

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

出隊操作

DeQueue_Sq(SqQueue&Q,QElemType&e)

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

03

12J1J3J2出隊操作前Q.frontQ.rear54

03

12J1J3J2出隊操作后eJ1出隊操作算法

StatusDeQueue_Sq(SqQueue&Q,ElemType&e)

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

e=Q.