棧和隊(duì)列棧的定義和基本運(yùn)算/順序棧/鏈棧/隊(duì)列的定義和基本運(yùn)算/順序隊(duì)列/鏈?zhǔn)疥?duì)列/實(shí)訓(xùn)唐懿芳數(shù)據(jù)結(jié)構(gòu)與算法目錄CONTENTS棧的定義和基本運(yùn)算01順序棧02鏈棧03隊(duì)列的定義和基本運(yùn)算04順序隊(duì)列05鏈?zhǔn)疥?duì)列06實(shí)訓(xùn)07棧的定義和基本運(yùn)算1、棧的定義2、棧的基本運(yùn)算01數(shù)據(jù)結(jié)構(gòu)與算法第一節(jié)：棧的定義和基本運(yùn)算數(shù)據(jù)結(jié)構(gòu)與運(yùn)算生活中的棧與隊(duì)列棧和隊(duì)列是特殊的線性表?xiàng)Ｅc隊(duì)列的特征LIFO(LastInFirstOut)FIFO(FirstInFirstOut)棧的定義堆棧簡(jiǎn)稱為棧，是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。在表中，允許插入和刪除的一端稱作“棧頂”，另一端稱作“棧底”。通常將元素插入棧頂?shù)牟俜Q作為“入?！保ㄟM(jìn)棧或壓棧），稱刪除棧頂元素的操作為“出?！睏５讞ｍ斎霔３鰲D3.1堆棧a1a2an…第一節(jié)：棧的定義和基本運(yùn)算棧的基本運(yùn)算堆棧的基本運(yùn)算如下。(1) StackInit()初始化堆棧。(2) StackEmpty(s)判定棧s是否為空。(3) StackLength(s)求堆棧s的長(zhǎng)度。(4) GetTop(s)獲取棧頂元素的值。(5) Push(s,e)將元素e進(jìn)棧。(6) Pop(s)，出棧（刪除棧頂元素）。數(shù)據(jù)結(jié)構(gòu)與運(yùn)算第一節(jié)：棧的定義和基本運(yùn)算棧的存儲(chǔ)結(jié)構(gòu)兩種存儲(chǔ)結(jié)構(gòu)：(1) 順序棧——采用順序結(jié)構(gòu)存儲(chǔ)(2) 鏈?！捎面?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)與運(yùn)算順序棧1、順序棧的存儲(chǔ)結(jié)構(gòu)3、順序棧的案例2、順序棧的基本運(yùn)算02數(shù)據(jù)結(jié)構(gòu)與算法第二節(jié)：順序棧順序棧的存儲(chǔ)結(jié)構(gòu)MaxSize-1#defineMaxSize

堆?？赡苓_(dá)到的最大長(zhǎng)度typedef

struct

{ElementType

elem[MaxSize];

inttop;

/*棧頂位置*/}SeqStack;棧底棧頂a0a1an-1…備用空間棧滿和?？盏臈l件是什么？棧滿：top=Maxsize-1?？眨簍op=-1數(shù)據(jù)結(jié)構(gòu)與運(yùn)算SeqStackStackInit(){SeqStacks;s.top=-1;return(s);}順序棧的基本運(yùn)算初始化堆棧StackInit()intStackEmpty(SeqStacks){return(s.top==-1);}判定棧s是否為空StackEmpty(s)intStackLength(SeqStacks){return(s.top+1);}求堆棧s的長(zhǎng)度StackLength(s)ElementTypeGetTop(SeqStacks){if(StackEmpty(s))/*空棧*/return(nil);return(s.elem[s.top]);}獲取棧頂元素的值GetTop(s)voidPush(SeqStack*s,ElementTypee){if(s->top==MaxSize-1)/*棧滿*/printf(“Full”);else{

s->top++;s->elem[s->top]=e;}}進(jìn)棧Push(s,e)ElementTypePop(SeqStack*s){if(s->top==-1)/*棧空*/return(nil);/*返回空值*/else{e=s->elem[s->top];

s->top--;

return(e);}}出棧Pop(s)第二節(jié)：順序棧數(shù)據(jù)結(jié)構(gòu)與運(yùn)算順序棧案例1【例1】假設(shè)有兩個(gè)棧共享一個(gè)一維數(shù)組空間[0,MaxSize－1]，其中一個(gè)棧用數(shù)組的第0單元（元素）作為棧底，另一棧用數(shù)組的第MaxSize－1號(hào)單元（元素）作為棧底（即兩個(gè)堆棧從兩端向中間延伸），其對(duì)應(yīng)的類型描述如下：#defineMaxSize堆?？赡苓_(dá)到的最大長(zhǎng)度typedefstruct{ElementTypeelem[MaxSize];

inttop1,top2;

/*棧頂位置*/}ShareStack;第二節(jié)：順序棧數(shù)據(jù)結(jié)構(gòu)與運(yùn)算順序棧案例2

則棧1的棧頂表示為:s->top1，棧2的棧頂表示為:s->top2;

棧1的進(jìn)棧操作使得棧頂1右（后）移，即s->top1++，棧2進(jìn)

棧操作使得棧頂2左（前）移，即s->top1--;

棧滿時(shí)兩個(gè)棧頂相鄰，即s->top1+1＝＝s->top2。圖3.2共享堆棧棧1

棧頂2a1anb1bm棧2棧底1棧底20…MaxSize-1棧頂1第二節(jié)：順序棧數(shù)據(jù)結(jié)構(gòu)與運(yùn)算順序棧案例3進(jìn)棧

voidPush(ShareStack*s,ElementTypee,inti)/*將元素e壓入棧i(i=1,2)*/{if(s->top1+1==s->top2)/*棧滿*/ printf(“Full”);else{if(i==1){s->top1++;s->elem[s->top1]=e;}else{s->top2--;s->elem[s->top2]=e;}}}第二節(jié)：順序棧數(shù)據(jù)結(jié)構(gòu)與運(yùn)算順序棧案例4出棧ElementTypePop(ShareStack*s,inti)/*棧i(i=1,2)出棧*/{if(i==1)if(s->top1==-1)/*棧1空*/return(nil);else{e=s->elem[s->top1];s->top1--;return(e);}if(i==2) if(s->top2==MaxSize)/*棧2空*/return(nil); else{e=s->elem[s->top2];s->top2++;return(e);}}第二節(jié)：順序棧數(shù)據(jù)結(jié)構(gòu)與運(yùn)算鏈棧1、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2、鏈棧的基本運(yùn)算03數(shù)據(jù)結(jié)構(gòu)與算法第三節(jié)：鏈棧鏈棧的存儲(chǔ)結(jié)構(gòu)#defineMAX_SIZE100//設(shè)置最大元素個(gè)數(shù)typedefintElemtype;typedefstructsnode{ElementTypedata;structsnode*next;}StackNode;typedefStackNode*LinkStack;/*LinkStack為指向StackNode的指針類型*/...圖3.6鏈棧棧頂a1anan-1棧底datanextΛs數(shù)據(jù)結(jié)構(gòu)與運(yùn)算第三節(jié)：鏈棧鏈棧的基本操作1．棧初始化棧的初始化實(shí)現(xiàn)比較簡(jiǎn)單，算法如下：LinkStackStackInit(){ LinkStack s=(LinkStack)malloc(sizeof(StackNode)); s->next=0; return(s);}/*StackInit*/2．判斷棧是否為空在判斷棧是否為空時(shí)，只需將棧頂指針s->next值與null相比即可，算法實(shí)現(xiàn)如下：intStackEmpty(LinkStacks){ return(s->next==NULL);}/*StackEmpty*/數(shù)據(jù)結(jié)構(gòu)與運(yùn)算第三節(jié)：鏈棧鏈棧的基本操作3．求棧的長(zhǎng)度intStackLength(LinkStacks){ LinkStackp=s->next; intlength=0; while(p) {length++;p=p->next;} return(length);}/*StackLength*/4．進(jìn)棧操作//插入元素e為新的棧頂元素voidPush(LinkStacks,inte){ LinkStackp=(StackNode*)malloc(sizeof(StackNode)); p->data=e; p->next=s->next;//如圖②把當(dāng)前的棧頂元素賦值給新結(jié)點(diǎn)的直接后繼

s->next=p;

//如圖③將新的結(jié)點(diǎn)p賦值給棧頂指針}

/*Push*/數(shù)據(jù)結(jié)構(gòu)與運(yùn)算第三節(jié)：鏈棧鏈棧的基本操作5．出棧操作//若棧不空，則刪除棧頂元素，用e返回值intPop(LinkStacks){ if(StackEmpty(s))

/*?？?/ return(nil);

/*返回空值*/else{ LinkStackp=s->next;/*如圖①將棧頂結(jié)點(diǎn)賦值給p*/ inte=0; s->next=p->next;

/*如圖②使得棧頂指針下移1位，指向后一結(jié)點(diǎn)*/ e=p->data; free(p);

/*釋放結(jié)點(diǎn)p*/ return(e); }}

/*Pop*/數(shù)據(jù)結(jié)構(gòu)與運(yùn)算第三節(jié)：鏈棧鏈棧的基本操作6．獲取棧頂元素根據(jù)棧頂指針s，可以直接獲取最后入棧的元素。應(yīng)該注意的是，在進(jìn)行讀取之前，也要進(jìn)行棧空檢查。相關(guān)的算法實(shí)現(xiàn)如下：intGetTop(LinkStacks){if(StackEmpty(s))return(nil);return(s->next->data);}/*GetTop*/數(shù)據(jù)結(jié)構(gòu)與運(yùn)算隊(duì)列1、隊(duì)列的定義3、隊(duì)列的存儲(chǔ)結(jié)構(gòu)2、隊(duì)列的基本運(yùn)算04數(shù)據(jù)結(jié)構(gòu)與算法第4節(jié)：隊(duì)列隊(duì)列的定義隊(duì)列簡(jiǎn)稱為隊(duì)，是限定只能在表的一端作插入運(yùn)算、在另一端作刪除運(yùn)算的線性表；在表中，允許插入的一端稱作“隊(duì)尾”，允許刪除的另一端稱作“隊(duì)首”（或“隊(duì)頭”）；通常將元素插入隊(duì)尾的操作稱作為入隊(duì)列（或入隊(duì)），稱刪除隊(duì)首元素的操作為出隊(duì)列（或出隊(duì)）。數(shù)據(jù)結(jié)構(gòu)與運(yùn)算出隊(duì)列入隊(duì)列隊(duì)首隊(duì)尾a1a2a3an第4節(jié)：隊(duì)列隊(duì)列的基本運(yùn)算數(shù)據(jù)結(jié)構(gòu)與運(yùn)算隊(duì)列的基本運(yùn)算如下。(1) InitQueue()初始化隊(duì)列。(2) QueueEmpty(q)判定隊(duì)列q是否為空。(3) QueueLength(q)求隊(duì)列q的長(zhǎng)度。

GetHead(q)獲取隊(duì)列q隊(duì)首元素的值。(5) AddQueue(q,e)將元素e入隊(duì)。(6) DeleteQueue(q)刪除隊(duì)首元素。第4節(jié)：隊(duì)列隊(duì)列的存儲(chǔ)結(jié)構(gòu)兩種結(jié)構(gòu)：(1) 順序隊(duì)列——采用順序結(jié)構(gòu)存儲(chǔ)(2) 鏈?zhǔn)疥?duì)列——采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)與運(yùn)算順序隊(duì)列1、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)2、順序隊(duì)列的基本運(yùn)算05數(shù)據(jù)結(jié)構(gòu)與算法第5節(jié)：順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)1#defineMaxSizen隊(duì)列可能達(dá)到的最大長(zhǎng)度ntypedefstruct{ElementTypeelem[MaxSize];

intfront,rear;

/*隊(duì)首、隊(duì)尾指示器*/}Queue;數(shù)據(jù)結(jié)構(gòu)與運(yùn)算第5節(jié)：順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)2數(shù)據(jù)結(jié)構(gòu)與運(yùn)算圖3.12隊(duì)列操作abcerear=4dfront=-1bcerear=4dfront=0front=rear=4front=rear=-1(a)空隊(duì)(b)a,b,c,d,e入隊(duì)(c)出隊(duì)1次(d)出隊(duì)4次隊(duì)滿和隊(duì)空的條件是什么？隊(duì)空：front==rear隊(duì)滿：rear==Maxsize-1?第5節(jié)：順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)3數(shù)據(jù)結(jié)構(gòu)與運(yùn)算當(dāng)rear=MaxSize-1時(shí),隊(duì)列為滿，如果再加入新元素，就會(huì)產(chǎn)生"溢出"。但是這種"溢出"并不是真正的溢出，在數(shù)組的前端還可能有空位置，所以這是一種假溢出。bcerear=4dfront=0front=rear=4解決方法：循環(huán)隊(duì)列第5節(jié)：順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)4數(shù)據(jù)結(jié)構(gòu)與運(yùn)算為了能夠充分的使用數(shù)組中的存儲(chǔ)空間，把數(shù)組的前端和后端連接起來(lái)，形成一個(gè)環(huán)形的表，即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán)，成為循環(huán)隊(duì)列（CircularQueue）。front4012340123frontrearfrontreara40123frontrearbcd40123frontrearabcd40123frontrearabc40123rear(a)空隊(duì)列(b)a入隊(duì)列(c)b,c入隊(duì)列(d)d入隊(duì)列（隊(duì)滿）(e)出隊(duì)1次(f)出隊(duì)3次（隊(duì)空）隊(duì)頭指針進(jìn)1：front=(front+1)%MaxSize；隊(duì)尾指針進(jìn)1：rear=(rear+1)%MaxSize；第5節(jié)：順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)4數(shù)據(jù)結(jié)構(gòu)與運(yùn)算以下是隊(duì)空的幾種情況：初始化時(shí)：front=rear=0循環(huán)隊(duì)列為空的條件是：front==rear40123frontrear(a)空隊(duì)列front40123rear(f)出隊(duì)3次（隊(duì)空）front=0Rear=0front=4Rear=4第5節(jié)：順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)4數(shù)據(jù)結(jié)構(gòu)與運(yùn)算循環(huán)隊(duì)列為滿的條件是：front==(rear+1)%MaxSize40123frontrearabcd以下是隊(duì)滿的幾種情況：front=0Rear=440123frontrearabcdfront=3Rear=240123frontrearbcdafront=1Rear=0第5節(jié)：順序隊(duì)列順序隊(duì)列的基本運(yùn)算11）、初始化隊(duì)列InitQueue()CirQueueInitQueue(){ CirQueueq; q.front=q.rear=0; return(q);}2）、判定隊(duì)列q是否為空QueueEmpty(q)intQueueEmpty(CirQueueq){ return(q.front==q.rear);}數(shù)據(jù)結(jié)構(gòu)與運(yùn)算第5節(jié)：順序隊(duì)列順序隊(duì)列的基本運(yùn)算23)、

求隊(duì)列q的長(zhǎng)度QueueLength(q)intQueueLength(CirQueueq){return((q.rear+MaxSize-q.front)%MaxSize);}數(shù)據(jù)結(jié)構(gòu)與運(yùn)算40123frontrearabcfront=0Rear=340123frontrearabcdfront=3Rear=2第5節(jié)：順序隊(duì)列順序隊(duì)列的基本運(yùn)算34)、獲取隊(duì)列q隊(duì)首元素的值GetHead(q)ElementTypeGetHead(CirQueueq){ if(QueueEmpty(q)) return(-1); return(q.elem[(q.front+1)%MaxSize]);}數(shù)據(jù)結(jié)構(gòu)與運(yùn)算40123frontrear40123frontrearabcfront=0Rear=340123frontrearabdfront=4Rear=2第5節(jié)：順序隊(duì)列順序隊(duì)列的基本運(yùn)算45)、AddQueue(q,e)將元素e入隊(duì)voidAddQueue(CirQueue*q,ElementTypee){if(q->front==(q->rear+1)%MaxSize) printf("\nfull"); else{q->rear=(q->rear+1)%MaxSize;q->elem[q->rear]=e; }}數(shù)據(jù)結(jié)構(gòu)與運(yùn)算6)、DeleteQueue(q)刪除隊(duì)首元素ElementTypeDeleteQueue(CirQueue*q){ ElementTypee; if(q->front==q->rear) return(-1); else {e=q->elem[(q->front+1)%MaxSize];q->front=(q->front+1)%MaxSize; return(e); }}鏈?zhǔn)疥?duì)列1、鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu)2、鏈?zhǔn)疥?duì)列的基本運(yùn)算06數(shù)據(jù)結(jié)構(gòu)與算法第6節(jié)：鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與運(yùn)算3.6.1隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)首指針front圖3.16鏈隊(duì)列…隊(duì)尾指針rearΛa2a1anΛΛ頭結(jié)點(diǎn)隊(duì)首指針front隊(duì)尾指針rear(b)非空鏈隊(duì)列(a)空鏈隊(duì)列第6節(jié)：鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與運(yùn)算typedefstructQnode{ElementTypedata;//結(jié)點(diǎn)數(shù)據(jù)域

structQnode*next;//結(jié)點(diǎn)指針域}QueueNode;

typedefstruct{QueueNode*front,*rear;//隊(duì)首和隊(duì)尾指針}LinkQueue;第6節(jié)：鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列的基本操作數(shù)據(jù)結(jié)構(gòu)與運(yùn)算1．隊(duì)列初始化。隊(duì)列的初始化實(shí)現(xiàn)比較簡(jiǎn)單，算法如下：LinkQueueInitQueue(){ QueueNode*p; LinkQueueq; p=(QueueNode*)malloc(sizeof(QueueNode)); p->next=NULL;q.front=q.rear=p; return(q);}2.判斷隊(duì)列是否為空intQueueEmpty(LinkQueueq){ return(q.front==q.rear);}第6節(jié)：鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列的基本操作數(shù)據(jù)結(jié)構(gòu)與運(yùn)算3．獲取隊(duì)首元素ElementTypeGet