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

第3章棧和隊列教學(xué)要求相關(guān)知識點相關(guān)術(shù)語：棧、隊列物理結(jié)構(gòu)：順序棧、鏈棧、順序隊列、鏈隊列學(xué)習(xí)重點棧的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法隊列的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法目錄隊列本章小結(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棧棧的順序存儲與操作1.順序棧的定義順序棧是指利用順序存儲分配方式來實現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。通常用一維數(shù)組存儲數(shù)據(jù)元素，并預(yù)設(shè)一個最大空間。把數(shù)組中下標(biāo)為0的一端作為棧底，為了指示棧中元素的位置，定義top指示棧頂元素在順序棧中的位置。3.1棧順序棧分為靜態(tài)順序存儲和動態(tài)順序存儲，靜態(tài)順序存儲的棧一次性分配空間，在棧滿后不能追加空間進(jìn)行入棧操作，而動態(tài)順序存儲是在靜態(tài)順序存儲的基礎(chǔ)上增加了可追加空間的功能。靜態(tài)存儲是將top定義為整數(shù)，而動態(tài)存儲是將top定義為指針。top可以指向棧頂元素的下一個位置，也可以指向棧頂元素。3.1棧(1)棧的靜態(tài)分配順序存儲結(jié)構(gòu)描述#defineMaxSize100 /*定義靜態(tài)棧最大長度*/typedefstruct{SElemTypebase[MaxSize];/*定義一個存放棧數(shù)據(jù)元素的一維數(shù)組*/inttop;/*棧頂指針*，可以指向棧頂元素的下一位置或者指向棧頂元素/intStackSize;/*存儲順序棧的當(dāng)前長度*/}SeqStack;3.1棧我們使用數(shù)組來實現(xiàn)棧中元素的存儲，并設(shè)存儲棧元素的數(shù)組長度為StackSize。當(dāng)棧滿時再進(jìn)行進(jìn)棧運(yùn)算必定產(chǎn)生溢出，簡稱“上溢”；當(dāng)?？諘r再做退棧運(yùn)算也將產(chǎn)生溢出，簡稱“下溢”。上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免。下溢是正?，F(xiàn)象，常常用來作為程序控制轉(zhuǎn)移的條件。3.1棧①top為整數(shù)且指向棧頂元素的下一個位置當(dāng)top為整數(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ù)且指向棧頂元素時，初始化條件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)棧的動態(tài)分配順序存儲結(jié)構(gòu)描述棧的動態(tài)分配順序存儲結(jié)構(gòu)是通過將top定義為指針來實現(xiàn)的。#defineSTACK_INIT_SIZE10 /*存儲空間初始化分配量*/#defineSTACK_INCREMENT2 /*存儲空間分配增量*/typedefintSElemType;3.1棧typedefstructSqStack{SElemType*base;/*棧底指針，始終指向棧底的位置*/int*top; /*棧頂指針，可以指向棧頂元素的下一個位置或者指向棧頂元素*/intStackSize; /*當(dāng)前分配的?？墒褂玫囊栽貫閱挝坏淖畲蟠鎯θ萘?/}SqStack; /*順序棧*/3.1棧①top為指針且指向棧頂元素的下一個位置當(dāng)top為指針且指向棧頂元素的下一個位置時，初始化條件為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為指針且指向棧頂元素時，初始化條件為S.top=S.base-1。(a)?？誗.top==S.base-1(b)元素入棧*++S.top=e3.1棧

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

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

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

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

p=(NodePtr)malloc(LEN);

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

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

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

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

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

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

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

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

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

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

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

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

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

QueuePtrp;

p=(QueuePtr)malloc(sizeof(QNode));/*動態(tài)生成新節(jié)點*/

if(!p) exit(0);

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

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