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

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

從數(shù)據(jù)結(jié)構(gòu)上看，棧和隊(duì)列也是線(xiàn)性表，不過(guò)是兩種特殊的線(xiàn)性表。棧只允許在表的一端進(jìn)行插入或刪除操作，而隊(duì)列只允許在表的一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作。堆棧和隊(duì)列在各種類(lèi)型的軟件系統(tǒng)中應(yīng)用廣泛。堆棧技術(shù)被廣泛應(yīng)用于編譯軟件和程序設(shè)計(jì)中，在操作系統(tǒng)和事務(wù)管理中廣泛應(yīng)用了隊(duì)列技術(shù)。通過(guò)本章的學(xué)習(xí)，讀者應(yīng)能掌握棧和隊(duì)列的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及棧和隊(duì)列的基本運(yùn)算以及實(shí)現(xiàn)算法。3.1棧3.2隊(duì)列3.1棧

1、棧(Stack)的定義：

棧是一種特殊的線(xiàn)性表，限定僅在表的一端進(jìn)行插入或刪除操作的線(xiàn)性表。棧的插入操作通常稱(chēng)為入棧或進(jìn)棧(push)，而棧的刪除操作則稱(chēng)為出棧或退棧(pop)。當(dāng)棧中無(wú)數(shù)據(jù)元素時(shí)，稱(chēng)為空棧。特點(diǎn):

（1）只允許在一端插入和刪除的順序表（2）允許插入和刪除的一端稱(chēng)為棧頂(top)，另一端稱(chēng)為棧底(bottom)

（3）后進(jìn)先出(LIFO，lastinfirstout)第3章棧和隊(duì)列

2、棧的存儲(chǔ)結(jié)構(gòu)：（1）順序存儲(chǔ)結(jié)構(gòu)兩種存儲(chǔ)結(jié)構(gòu):

（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

順序棧：利用數(shù)組存放自棧底到棧頂?shù)臄?shù)據(jù)元素，附設(shè)指針top指示棧頂元素在順序棧中的位置。

#defineMAXNUM<最大元素?cái)?shù)>//棧的最大數(shù)據(jù)元素?cái)?shù)目

typedefstruct{Elemtypestack[MAXNUM];//存放棧中數(shù)據(jù)元素的存儲(chǔ)單元

inttop;//棧頂指針

}sqstack;

鑒于C語(yǔ)言中數(shù)組的下標(biāo)約定是從0開(kāi)始的，因而使用C語(yǔ)言的一維數(shù)組作為棧時(shí)，應(yīng)設(shè)棧頂指針top=-1時(shí)為空棧。一般有：

s->top=s->base是為空棧?；静僮魉惴ǎ海?）初始化棧操作

intinitStack(sqstack*s){/*創(chuàng)建一個(gè)空棧由指針S指出*/s=(sqstack*)malloc(sizeof(sqstack));if(s==NULL)

{returnFALSE；}else{s->top=s->base;returnTRUE;}}（2）進(jìn)棧操作

intpush(sqstack*s,Elemtypex){/*將元素x插入到棧s中，作為s的新棧頂*/if(s->top>=MAXNUM-1)returnFALSE;/*棧滿(mǎn)*/

s->stack[s->top]=x;s->top++;returnTRUE;}（3）出棧操作

intpop(sqstack*s){/*若棧s不為空，則刪除棧頂元素*/if(s->top<0)returnNULL;/*棧空*/

s->top--;x=s->stack[s->top];returnx;}（4）取棧頂元素操作

intgettop(sqstack*s){/*若棧s不為空，則返回棧頂元素*/if(s->top<0)returnNULL;/*棧空*/

return(s->stack[--s->top]);}

注：取棧頂元素與出棧不同之處在于出棧操作改變棧頂指針top的位置，而取棧頂元素操作不改變棧的棧頂指針。（5）判斷空操作

intEmpty(sqstack*s){//棧s為空時(shí)，返回為T(mén)RUE；

//非空時(shí)，返回為FALSE

if(s->top<0)returnTRUE;

returnFALSE;}

鏈?zhǔn)綏＃喝羰菞Ｖ性氐臄?shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。人們將用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的棧稱(chēng)作“鏈棧”。由于棧的插入刪除操作只能在一端進(jìn)行，而對(duì)于單鏈表來(lái)說(shuō)，在首端插入刪除結(jié)點(diǎn)要比尾端相對(duì)地容易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。datanexttop棧頂棧底鏈棧示意圖

typestructnode{//鏈棧的結(jié)點(diǎn)結(jié)構(gòu)

ELEMTPdata;//棧的數(shù)據(jù)元素類(lèi)型

structnode*next;//指向后繼結(jié)點(diǎn)的指針

}SNode;基本操作算法：（1）建立一個(gè)空棧

StatusInitLStack(Linkstack&S){

S=NULL;

returnok;

}//InitLStack

（2）取棧頂元素

StatusGettopLStack(Linkstack&S,SElemType&e){

//若棧不為空，則用e返回S的棧頂元素，

//并返回OK,否則返回ERROR.

if(S==NULL)returnERROR;

e=S->data;

return(OK);

}//GettopLStack（3）入棧操作

voidPush(LinkStack*s，ELEMTPx){s=(LinkStack*)malloc(sizeof(LinkStack));s->data=x;s->next=top；top=s;

returntop;}（4）出棧操作

voidPop(LinkStack*s,ELEMTP*x){if(s==NULL)returnNULL;/*空棧*/else{

p=top;*x=p->data;top=p->next;free(p);

}returntop;}

例：十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題，其解決方法很多，其中一個(gè)簡(jiǎn)單算法基于下列原理：N=(Ndivd)×d+Nmodd(其中：div為整除運(yùn)算，mod為求余運(yùn)算）

voidconversion(){//對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)

InitStack(S);//構(gòu)造空棧

scanf("%d",N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}//conversion3.2隊(duì)列

1、隊(duì)列（Queue）的定義：

隊(duì)列是一種特殊的線(xiàn)性表，限定插入在線(xiàn)性表的一端進(jìn)行，刪除在線(xiàn)性表的另外一端進(jìn)行。特點(diǎn):

（1）只允許在一端插入，在另外一端刪除的順序表（2）允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)

（3）后進(jìn)先出(FIFO，F(xiàn)irstinFirstOut)frontreara0

a1

a2

an-1

2、隊(duì)列的存儲(chǔ)結(jié)構(gòu)：（1）順序存儲(chǔ)結(jié)構(gòu)兩種存儲(chǔ)結(jié)構(gòu):

（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

順序隊(duì)列：利用一組地址連續(xù)的存儲(chǔ)單元依次將數(shù)據(jù)元素存放到隊(duì)列中。附設(shè)一個(gè)為指向隊(duì)頭元素位置的指針front，另一個(gè)為指向隊(duì)尾的元素位置的指針rear。

（1）進(jìn)隊(duì)時(shí)：隊(duì)尾指針先進(jìn)一rear=rear+1，再將新元素按rear指示位置加入。（2）出隊(duì)時(shí)：隊(duì)頭指針先進(jìn)一front=front+1，再將下標(biāo)為front的元素取出。插入端和刪除端都是浮動(dòng)的。通常我們將插入端稱(chēng)為隊(duì)尾，用“rear”指示；而刪除端被稱(chēng)為隊(duì)頭，用“front”指示。frontrear空隊(duì)列frontrearA進(jìn)隊(duì)AfrontrearB進(jìn)隊(duì)ABfrontrearC,D進(jìn)隊(duì)ABCDfrontrearA退隊(duì)BCDfrontrearB退隊(duì)CDfrontrearE,F,G進(jìn)隊(duì)CDEFGCDEFGfrontrearH進(jìn)隊(duì),溢出

用C語(yǔ)言定義的順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列如下：

#defineMAXNUM<最大元素?cái)?shù)>//隊(duì)列的最大數(shù)據(jù)元素?cái)?shù)目

typedefstruct{ElemtypeQueue[MAXNUM];//存放隊(duì)列中數(shù)據(jù)元素的存儲(chǔ)單元

intrear,front;//隊(duì)頭隊(duì)尾指針

}SeqQueue;SeqQueue*sq;Sq=newSeqQueue;

為了算法設(shè)計(jì)的方便，在此我們約定：初始化隊(duì)列時(shí)，空隊(duì)列時(shí)令front=rear=-1，當(dāng)插入新的數(shù)據(jù)元素時(shí)，尾指示器rear加1，而當(dāng)隊(duì)頭元素出隊(duì)列時(shí)，隊(duì)頭指示器front加1。另外還約定，在非空隊(duì)列中，頭指示器front總是指向隊(duì)列中實(shí)際隊(duì)頭元素的前面一個(gè)位置，而尾指示器rear總是指向隊(duì)尾元素?；静僮魉惴ǎ海?）初始化隊(duì)列

intinitQueue(sqqueue*q){/*創(chuàng)建一個(gè)空隊(duì)列由指針q指出*/q=(sqqueue*)malloc(sizeof(sqqueue))if(q==NULL)returnFALSE;

q->front=q->rear=0;returnTRUE;}（2）入隊(duì)列操作

intappend(sqqueue*q,Elemtypex){/*將元素x插入到隊(duì)列q中，作為q的新隊(duì)尾*/if(q->rear>=MAXNUM-1)returnFALSE;/*隊(duì)列滿(mǎn)*/

q->rear++;q->queue[q->rear]=x;returnTRUE;}（3）出隊(duì)列操作

Elemtypedelete(sqqueue*q){/*若隊(duì)列q不為空，則返回隊(duì)頭元素*/Elemtypex;if(q->rear==q->front)returnNULL;/*隊(duì)列空*/

x=q->queue[++q->front];returnx;}（4）取隊(duì)頭元素操作

ElemtypegetHead(sqqueue*q){/*若隊(duì)列q不為空，則返回隊(duì)頭元素*/if(q->rear==q->front)returnNULL;/*隊(duì)列空*/return(q->queue[s->front+1]);}（5）判隊(duì)列非空操作

intEmpty(sqqueue*q){//隊(duì)列q為空時(shí)，返回TRUE；

//否則返回FALSE

if(q->rear==q->front)returnTRUE;returnFALSE;}（6）求隊(duì)列長(zhǎng)度操作

intlength(sqqueue*q){/*返回隊(duì)列q的元素個(gè)數(shù)*/

return(q->rear-q->front);}隊(duì)滿(mǎn)時(shí)再進(jìn)隊(duì)—>溢出隊(duì)空時(shí)再出隊(duì)—>隊(duì)空

解決辦法：將隊(duì)列元素?cái)?shù)組首尾相接，形成循環(huán)隊(duì)列。在循環(huán)隊(duì)列中，每插入一個(gè)新元素時(shí)，就把隊(duì)尾指針沿順時(shí)針?lè)较蛞苿?dòng)一個(gè)位置。即：

q->rear=q->rear+1;if(q->rear==MAXNUM)q->rear=0;

在循環(huán)隊(duì)列中，每刪除一個(gè)元素時(shí)，就把隊(duì)頭指針沿順時(shí)針?lè)较蛞苿?dòng)一個(gè)位置。即：

q->front=q->front+1;if(q->front==MAXNUM)q->front=0;01234567front01234567front01234567frontrearAABCrearrear空隊(duì)列A進(jìn)隊(duì)B,C進(jìn)隊(duì)0123456701234567A退隊(duì)B退隊(duì)01234567D,E,F,G,H進(jìn)隊(duì)frontBCrearAfrontBCrearfrontCrearDEFGH

假設(shè)為隊(duì)列開(kāi)辟的數(shù)組單元數(shù)目為MAX_QUEUE，在C語(yǔ)言中，它的下標(biāo)在0~MAX_QUEUE-1之間，若增加隊(duì)頭或隊(duì)尾指針，可以利用取模運(yùn)算實(shí)現(xiàn)。如下：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；當(dāng)front或rear為MAX_QUEUE-1時(shí)，上述兩個(gè)公式計(jì)算的結(jié)果就為0。這樣，就使得指針自動(dòng)由后面轉(zhuǎn)到前面，形成循環(huán)的效果。隊(duì)空和隊(duì)滿(mǎn)的標(biāo)志問(wèn)題：隊(duì)列變?yōu)榭?，?duì)頭和隊(duì)尾指針相等。（1）初始化操作

StatusInitQueue(SqQueue*Q){//構(gòu)造一個(gè)空隊(duì)列Q

Q=(QElemType)malloc(MAXQSIZE*sizeof(QElemType))；

if(!Q)exit(OVERFLOW)；//存儲(chǔ)分配失敗

Q.front=Q.rear=0；

returnOK；

}（2）入隊(duì)列操作

intEnQueue(SqQueue&Q，QElemTypee){//插入元素e為Q的新的隊(duì)尾元素

if((Q.rear+1)％MAXQSIZE==Q.front)returnERROR；//隊(duì)列滿(mǎn)

Q.base[Q.rear]=e；

Q.rear=(Q.rear+1)％MAXQSIZE；

return1；

}（3）出隊(duì)列操作

StatusDeQueue(SqQueue&Q，QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，

//用e返回其值，并返回1，否則返回ERRORif(Q.Front==Q.rear)returnERROR；

e=Q.base[Q.front]；

Q.front=(Q.front+1)％MAXQSIZE；

returnOK；

}（4）求循環(huán)隊(duì)列長(zhǎng)度

IntQueueLength(SqQueueQ){//返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度

return(Q.rear–Q.front+MAXSIZE)%MAXQSIZE；

}

鏈?zhǔn)疥?duì)列：用鏈表表示的隊(duì)列。

（1）一個(gè)鏈隊(duì)列需要兩個(gè)指針，分別指示隊(duì)頭和隊(duì)尾的指針——頭指針和尾指針。

（2）給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)。空的鏈隊(duì)列的判決條件為頭指針和尾指針均指向頭結(jié)點(diǎn)。frontrear（1）初始化操作

StatusInitQueue(LinkQ