數(shù)據(jù)結(jié)構(gòu)（C語言版）（第三版）（微課版）第3章 棧和隊(duì)列

第3章棧和隊(duì)列教學(xué)要求相關(guān)知識(shí)點(diǎn)相關(guān)術(shù)語：棧、隊(duì)列物理結(jié)構(gòu)：順序棧、鏈棧、順序隊(duì)列、鏈隊(duì)列學(xué)習(xí)重點(diǎn)棧的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相關(guān)算法隊(duì)列的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相關(guān)算法目錄隊(duì)列本章小結(jié)3棧123.1棧3.1棧棧的定義棧(Stack)是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(base)。不含任何數(shù)據(jù)元素的棧稱為空棧。假設(shè)棧S=（a0，a1，…，an-1），則稱a0為棧底元素，an-1為棧頂元素。棧中元素按a1，a2，…，an-1的順序進(jìn)棧，退棧從棧頂元素開始出棧。所以，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧又稱為后進(jìn)先出（LIFO：lastinfirstout）的線性表。3.1棧棧的順序存儲(chǔ)與操作1.順序棧的定義順序棧是指利用順序存儲(chǔ)分配方式來實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。通常用一維數(shù)組存儲(chǔ)數(shù)據(jù)元素，并預(yù)設(shè)一個(gè)最大空間。把數(shù)組中下標(biāo)為0的一端作為棧底，為了指示棧中元素的位置，定義top指示棧頂元素在順序棧中的位置。3.1棧順序棧分為靜態(tài)順序存儲(chǔ)和動(dòng)態(tài)順序存儲(chǔ)，靜態(tài)順序存儲(chǔ)的棧一次性分配空間，在棧滿后不能追加空間進(jìn)行入棧操作，而動(dòng)態(tài)順序存儲(chǔ)是在靜態(tài)順序存儲(chǔ)的基礎(chǔ)上增加了可追加空間的功能。靜態(tài)存儲(chǔ)是將top定義為整數(shù)，而動(dòng)態(tài)存儲(chǔ)是將top定義為指針。top可以指向棧頂元素的下一個(gè)位置，也可以指向棧頂元素。3.1棧(1)棧的靜態(tài)分配順序存儲(chǔ)結(jié)構(gòu)描述#defineMaxSize100 /*定義靜態(tài)棧最大長度*/typedefstruct{SElemTypebase[MaxSize];/*定義一個(gè)存放棧數(shù)據(jù)元素的一維數(shù)組*/inttop;/*棧頂指針*，可以指向棧頂元素的下一位置或者指向棧頂元素/intStackSize;/*存儲(chǔ)順序棧的當(dāng)前長度*/}SeqStack;3.1棧我們使用數(shù)組來實(shí)現(xiàn)棧中元素的存儲(chǔ)，并設(shè)存儲(chǔ)棧元素的數(shù)組長度為StackSize。當(dāng)棧滿時(shí)再進(jìn)行進(jìn)棧運(yùn)算必定產(chǎn)生溢出，簡稱“上溢”；當(dāng)?？諘r(shí)再做退棧運(yùn)算也將產(chǎn)生溢出，簡稱“下溢”。上溢是一種出錯(cuò)狀態(tài)，應(yīng)該設(shè)法避免。下溢是正?，F(xiàn)象，常常用來作為程序控制轉(zhuǎn)移的條件。3.1棧①top為整數(shù)且指向棧頂元素的下一個(gè)位置當(dāng)top為整數(shù)且指向棧頂元素的下一個(gè)位置時(shí)，初始化條件為S.top=0。(a)?？誗.top==0(b)入棧S.base[S.top++]=e3.1棧(c)棧滿S.top>=MaxSize

(d)出棧*e=S.base[--S.top]3.1棧②top為整數(shù)且指向棧頂元素當(dāng)top為整數(shù)且指向棧頂元素時(shí)，初始化條件S.top=-1(a)?？誗.top==-1(b)元素入棧S.base[++S.top]=e3.1棧

(c)棧滿S.top>=MaxSize-1

(d)元素出棧*e=S.base[S.top--]3.1棧(2)棧的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)描述棧的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)是通過將top定義為指針來實(shí)現(xiàn)的。#defineSTACK_INIT_SIZE10 /*存儲(chǔ)空間初始化分配量*/#defineSTACK_INCREMENT2 /*存儲(chǔ)空間分配增量*/typedefintSElemType;3.1棧typedefstructSqStack{SElemType*base;/*棧底指針，始終指向棧底的位置*/int*top; /*棧頂指針，可以指向棧頂元素的下一個(gè)位置或者指向棧頂元素*/intStackSize; /*當(dāng)前分配的?？墒褂玫囊栽貫閱挝坏淖畲蟠鎯?chǔ)容量*/}SqStack; /*順序棧*/3.1棧①top為指針且指向棧頂元素的下一個(gè)位置當(dāng)top為指針且指向棧頂元素的下一個(gè)位置時(shí)，初始化條件為S.top=S.base。(a)?？誗.top==S.base

(b)元素入棧*S.top++=e3.1棧(c)棧滿S.top-S.base>=StackSize

(d)元素出棧*e=*--S.top3.1棧②top為指針且指向棧頂元素當(dāng)top為指針且指向棧頂元素時(shí)，初始化條件為S.top=S.base-1。(a)棧空S.top==S.base-1(b)元素入棧*++S.top=e3.1棧

(c)棧滿S.top-S.base+1>=StackSize

(d)元素出棧*e=*S.top--3.1棧2.順序棧的基本操作（top為指針且指向棧頂元素下一個(gè)位置的動(dòng)態(tài)順序棧存儲(chǔ)的基本操作）(1)構(gòu)造一個(gè)空棧SintInitStack(SqStack*S)/*成功返回1失敗返回0*/{S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S->base)return0;/*存儲(chǔ)分配失敗*/S->top=S->base;//top為指針且指向棧頂元素下一個(gè)位置S->StackSize=STACK_INIT_SIZE;return1;}3.1棧(2)銷毀棧算法3.2銷毀棧voidDestroyStack(SeqStack*S){if(S!=NULL){free(S->base);/*釋放棧*/S->top=S->base=NULL;//top為指針且指向棧頂元素下一個(gè)位置S->StackSize=0;}}3.1棧(3)清空棧voidClearStack(SqStack*S){S->top=S->base;}//top為指針且指向棧頂元素下一個(gè)位置(4)判斷一個(gè)棧是否為空intStackEmpty(SqStackS)/*若棧S為空棧，則返回1，否則返回0*/{if(S.top==S.base)return1;elsereturn0;}3.1棧(5)求棧的長度算法3.5求一個(gè)棧的長度intLengthStack(SqStackS){if((S.base)&&(S.top))

return(S.top-S.base);//top為指針且指向棧頂元素下一個(gè)位置}3.1棧(6)取棧頂元素算法3.6取棧頂元素intGetTop(SqStackS,SElemType*e)/*若棧不空，則用e返回S的棧頂元素，并返回1；否則返回0*/{if(S.top>S.base)//top為指針且指向棧頂元素下一個(gè)位置{*e=*(S.top-1);return1;}elsereturn0;}3.1棧(7)入棧操作讓數(shù)據(jù)元素e進(jìn)棧，首先要判斷棧是否未滿，若是則棧頂指針右移一位，將數(shù)據(jù)元素e存入棧頂指針?biāo)肝恢谩ntPush(SqStack*S,SElemTypee)/*所插入元素e為新的棧頂元素，如果插入成功，返回1，否則返回0，top為指針且指向棧頂元素下一個(gè)位置*/{if(S->top-S->base>=S->StackSize) /*棧滿，追加存儲(chǔ)空間*/{S->base=(SElemType*)realloc(S->base,(S->StackSize+STACKINCREMENT)*sizeof(SElemType));3.1棧if(!(S->base)return0;/*存儲(chǔ)分配失敗*/S->top=S->base+S->StackSize;/*修改棧底指針*/S->StackSize+=STACKINCREMENT;}*(S->top)++=e;//將e入棧，成為新的棧頂元素return1;}3.1棧(8)出棧操作退出一個(gè)棧內(nèi)節(jié)點(diǎn)并得到棧頂數(shù)據(jù)元素的值。首先判斷棧是否為空棧，若不空則取得棧頂元素并且棧高度-1。intPop(SqStack*S,SElemType*e)/*若棧不空，則刪除S的棧頂元素，用e返回值，并返回1；否則返回0，top為指針且指向棧頂元素下一個(gè)位置*/{if(S->top==S->base)return0;/*?？?/*e=*--S->top;//棧底元素賦給e，棧頂指針下移return1;}3.1棧(9)遍歷棧算法3.9遍歷棧voidStackTraverse(SqStackS,void(*visit)(SElemType)){while(S.top>S.base)//top為指針且指向棧頂元素下一個(gè)位置printf("%2d",*S.base++);}3.1棧棧的鏈?zhǔn)酱鎯?chǔ)與操作1.鏈棧的定義棧用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)簡稱鏈棧。鏈棧中指針的方向是從棧頂指向棧底，圖3.5中的S為棧頂指針。3.1棧鏈棧的定義可以描述如下：typedefstructnode{elemtypedata;

structnode*next;}NODE,*NODEPTR#defineLENsizeof(NODE)3.1棧2.鏈棧的一些基本操作(1)建立一個(gè)空棧只要利用已經(jīng)定義的鏈表的節(jié)點(diǎn)指針類型聲明一個(gè)棧頂指針，并將其置為空即可。建立一個(gè)空棧的代碼語句如下：intInit_Stack(NodePtrtop)/*構(gòu)造空棧，返回1*/{top=NULL;return1;}3.1棧(2)進(jìn)棧操作，讓數(shù)據(jù)元素e進(jìn)入鏈棧在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下，不需要像順序存儲(chǔ)那樣需要判斷棧是否未滿，但需要建立一個(gè)新節(jié)點(diǎn)，并給新節(jié)點(diǎn)分配相應(yīng)的內(nèi)存空間。若系統(tǒng)分配空間失敗，則新節(jié)點(diǎn)e進(jìn)棧失敗，否則將數(shù)據(jù)元素存入新節(jié)點(diǎn)，并將新節(jié)點(diǎn)掛載到鏈頭，并作為新鏈頭。3.1棧intPush_Stack(NodePtrtop,elemtypee){NodePtrp;

p=(NodePtr)malloc(LEN);

if(p==NULL) {printf(“系統(tǒng)分配空間失??！”); return0;}

p->data=e; /*存入新節(jié)點(diǎn)元素值*/

p->next=top; /*新節(jié)點(diǎn)與原棧頂相連接*/

top=p; /*新節(jié)點(diǎn)作為新棧頂*/return1;}3.1棧(3)出棧操作，讓一個(gè)節(jié)點(diǎn)出棧并得到棧頂數(shù)據(jù)元素的值首先判斷棧是否為空，若不為空則獲取棧頂元素值，并將鏈頭節(jié)點(diǎn)刪除，原鏈頭的后繼節(jié)點(diǎn)作為新棧頂。3.1棧intPop_Stack(NodePtrtop,elemtype*e){NodePtrp;p=top;

if(p==NULL){printf(“棧為空，無法操作！”); return0;}*e=p->data; /*取得棧頂節(jié)點(diǎn)元素值*/

top=p->next;/*棧頂指針后移，刪除棧頂節(jié)點(diǎn)*/

free(p); /*釋放被刪除節(jié)點(diǎn)所占用的內(nèi)存空間*/return1;}3.2隊(duì)列3.2隊(duì)列隊(duì)列的定義隊(duì)列(queue)是一種運(yùn)算受限制的線性表，元素的添加在表的一端進(jìn)行，而元素的刪除在表的另一端進(jìn)行。允許插入的一端稱為隊(duì)尾（rear），允許刪除的一端稱為隊(duì)頭（front）。a0是隊(duì)頭元素an-1是隊(duì)尾元素3.2隊(duì)列隊(duì)列的順序存儲(chǔ)與操作1.順序隊(duì)列的數(shù)據(jù)類型定義#defineMaxSize10 //順序隊(duì)列的最大容量typedefstruct{ElemType*data;//定義隊(duì)列元素的存儲(chǔ)空間

intfront,rear; /*定義隊(duì)頭和隊(duì)尾指針*/}SqQueue定義指向隊(duì)列的指針變量：SqQueue*sq;申請(qǐng)順序隊(duì)列的存儲(chǔ)空間：sq->base=(ElemType*)malloc(MaxSize*sizeof(ElemType));3.2隊(duì)列2.順序隊(duì)列的操作(1)front為隊(duì)頭元素當(dāng)前位置，rear為隊(duì)尾元素下一個(gè)位置①置空隊(duì)列sq->front=sq->rear=0;②入隊(duì)操作sq->data[sq->rear]=a; /*將新元素a入隊(duì)*/sq->rear++;3.2隊(duì)列③出隊(duì)操作*e=sq->data[sq->front];//將隊(duì)頭元素a出隊(duì)sq->front++;④計(jì)算隊(duì)列中元素個(gè)數(shù)n=(sq->rear)-(sq->front)當(dāng)隊(duì)列真滿時(shí)，n=MaxSize當(dāng)隊(duì)列空時(shí)，n=03.2隊(duì)列(2)front為隊(duì)頭元素前一個(gè)位置，rear為隊(duì)尾元素當(dāng)前位置①置空隊(duì)列sq->front=sq->rear=-1;②元素入隊(duì)sq->rear++;sq->data[sq->rear]=a; /*將新元素a入隊(duì)*/3.2隊(duì)列③出隊(duì)操作sq->front++;*e=sq->data[sq->front];//將隊(duì)頭元素a出隊(duì)④隊(duì)列中元素個(gè)數(shù)n=(sq->rear)-(sq->front)當(dāng)隊(duì)列真滿時(shí)，n=MaxSize當(dāng)隊(duì)列空時(shí)，n=03.2隊(duì)列3.順序隊(duì)列存在的假溢出現(xiàn)象圖3.8是順序隊(duì)列的各種操作示意圖，從圖中可以看到不管是入隊(duì)操作還是出隊(duì)操作，整個(gè)隊(duì)列都會(huì)隨著操作的進(jìn)展向數(shù)組中下標(biāo)較大的位置方向移動(dòng)，因?yàn)閺纳鲜鱿嚓P(guān)操作可以看到，都會(huì)執(zhí)行“++”這一步，于是就出現(xiàn)了圖3.8(d)的情況，此時(shí)隊(duì)尾指針rear已經(jīng)移到了所分配空間的最后一個(gè)位置，但是此時(shí)隊(duì)列中并沒有滿載，可以看出所分配的存儲(chǔ)空間的下半部分幾乎完全空閑，并沒有元素存儲(chǔ)進(jìn)來。這種現(xiàn)象我們稱為“假溢出”。出現(xiàn)假溢出現(xiàn)象的主要原因是隊(duì)列本身“隊(duì)尾進(jìn)入，隊(duì)頭出”的特性所導(dǎo)致的。3.2隊(duì)列問題由于隊(duì)列的進(jìn)隊(duì)操作是在兩端進(jìn)行的，隨著元素的不斷插入，刪除，兩端都向后移動(dòng)，隊(duì)列會(huì)很快移動(dòng)到數(shù)組末端造成溢出，而前面的單元無法利用。解決辦法：每次刪除一個(gè)元素后，將整個(gè)隊(duì)列向前移動(dòng)一個(gè)單元，保持隊(duì)列頭總固定在數(shù)組的第一個(gè)單元。將所用的數(shù)組想象成是頭尾相接的圓環(huán)，當(dāng)隊(duì)列的尾端到達(dá)數(shù)組的末端（第n個(gè)單元）時(shí)，如果再插入元素可繼續(xù)使隊(duì)列向數(shù)組的前端（第1個(gè)單元）延長，此隊(duì)列稱為循環(huán)隊(duì)列。3.2隊(duì)列4.循環(huán)隊(duì)列解決假溢出，讓第MaxSize個(gè)元素進(jìn)入到第0個(gè)空間中(利用取余數(shù)運(yùn)算%)。使隊(duì)列數(shù)據(jù)區(qū)形成一個(gè)循環(huán)，頭尾指針front、rear的指示不變，這種結(jié)構(gòu)稱為循環(huán)隊(duì)列。3.2隊(duì)列入隊(duì)時(shí)，將隊(duì)尾的自加1操作修改為：sq->rear=(sq->rear+1)%MaxSize;出隊(duì)時(shí)，將隊(duì)頭指針的自加1操作修改為：sq->front=(sq->front+1)%MaxSize;判斷一個(gè)循環(huán)隊(duì)列是否隊(duì)滿為：（Q.rear+1）%MaxSize==Q.front判斷一個(gè)隊(duì)列是否為空可用表達(dá)式：Q.rear==Q.front計(jì)算隊(duì)中元素長度應(yīng)為：(Q.rear-Q.front+MaxSize)%MaxSize3.2隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)與操作1.鏈隊(duì)列的數(shù)據(jù)類型定義typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;/*隊(duì)頭指針*/QueuePtrrear;/*隊(duì)尾指針*/}LinkQueue;3.2隊(duì)列2.鏈隊(duì)列的操作(1)建立一個(gè)空隊(duì)列利用已經(jīng)定義的鏈表的節(jié)點(diǎn)指針類型聲明一個(gè)隊(duì)頭和隊(duì)尾指針，并將指針置為空即可，這里不再像順序存儲(chǔ)的章節(jié)中那樣需要一個(gè)隊(duì)列長度，因?yàn)樵阪滉?duì)列中不需要做隊(duì)滿判斷，只要內(nèi)存空間還存在可用的位置，就可以不停地完成入隊(duì)操作；而在進(jìn)行隊(duì)空判定時(shí)也只需要查驗(yàn)隊(duì)頭指針是否為空即可，也不再需要借助隊(duì)列中元素的個(gè)數(shù)判斷。3.2隊(duì)列建立一個(gè)空鏈隊(duì)列的算法如下：voidInitQueue(LinkQueue*Q){/*初始化一個(gè)隊(duì)列*/

Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q->front)exit(0);/*生成頭節(jié)點(diǎn)失敗*/

Q->front->next=NULL;}3.2隊(duì)列(2)判斷一個(gè)隊(duì)列是否為空，算法如下：StatusQueueEmpty(LinkQueueQ){/*判斷隊(duì)列是否為空*/

if(Q.front->next==NULL) return1;

elsereturn0;}3.2隊(duì)列(3)入隊(duì)操作讓數(shù)據(jù)元素e進(jìn)入隊(duì)列，首先要建立一個(gè)新節(jié)點(diǎn)e，然后判斷隊(duì)列是否為空，若是空隊(duì)列，則此e進(jìn)入隊(duì)列后既是隊(duì)頭又是隊(duì)尾，否則就將節(jié)點(diǎn)e直接鏈接到隊(duì)尾，并將隊(duì)尾指針后移一個(gè)節(jié)點(diǎn)即可。3.2隊(duì)列voidEnQueue(LinkQueue*Q,QElemTypee){/*所插入的元素e為隊(duì)列Q的新隊(duì)尾元素*/

QueuePtrp;

p=(QueuePtr)malloc(sizeof(QNode));/*動(dòng)態(tài)生成新節(jié)點(diǎn)*/

if(!p) exit(0);

p->data=e;/*將e的值賦給新節(jié)點(diǎn)*/

p->next=NULL;/*新節(jié)點(diǎn)的指針為空*/