第三章 棧和隊(duì)列

1、第三章第三章 棧和隊(duì)列棧和隊(duì)列 3.1 堆棧 3.2 隊(duì)列3.1 堆棧3.1.1 堆棧的定義和基本操作w棧（stack）是一種特殊的線性表，這種表只能在其一端（稱為棧頂top）進(jìn)行插入和刪除操作,如圖2-4-1所示。棧的概念來(lái)自存貨的堆棧，存貨時(shí)一件一件往上堆，每次取貨時(shí)都有只能從上面取。棧的存取特征是后進(jìn)先出（Last In First Out,縮寫(xiě)為L(zhǎng)IFO）。棧頂將隨著棧中元素的增減而浮動(dòng)，通過(guò)棧頂指針指明當(dāng)前棧頂元素位置。棧的固定端稱為棧底（bottom），棧底指針并不移動(dòng)。w棧的基本操作包括：創(chuàng)建一個(gè)棧進(jìn)棧 棧頂 出棧w進(jìn)棧（push），出棧（pop）w讀取棧頂元素，判?？眨瑆棧清空

2、（初始化），求當(dāng)前棧w中元素的個(gè)數(shù)，撤消一個(gè)棧等w 棧底3.1.2 順序存儲(chǔ)棧w可用順序存儲(chǔ)線性表來(lái)表示棧，為了指明當(dāng)前執(zhí)行插入和刪除運(yùn)算的棧頂位置，需要一個(gè)游標(biāo)變量top（習(xí)慣稱為棧頂指針，注意與指針變量的區(qū)別），top指出棧頂表元素在數(shù)組中的下標(biāo)。當(dāng)棧為空時(shí)，top =0;棧滿時(shí)，top=MAXN(數(shù)組元素個(gè)數(shù)),如圖2-4-1所示。順序存儲(chǔ)棧示意圖w wMAXN-1 MAXN-1 top w . .w . .w . .w 1 1wtop-0 0w ?？?棧滿 1、順序存儲(chǔ)棧的進(jìn)棧操作(1)w 順序存儲(chǔ)棧的進(jìn)棧操作(2)w函數(shù)如下：wint push(NODE stack,int maxn

3、,int top,NODE x)/*設(shè)棧點(diǎn)的數(shù)據(jù)類型為NODE，棧空間最多能存maxn個(gè)結(jié)點(diǎn)*/wif (top=maxn) return 1; /*棧滿，進(jìn)棧失敗返回*/wstack top=x; /*完成進(jìn)棧運(yùn)算*/w+top;wreturn 0; /*進(jìn)棧成功，返回0*/w2、順序存儲(chǔ)棧出棧操作(1)順序存儲(chǔ)棧出棧操作(2)w函數(shù)如下：wint pop(NODE stack,int top,NODE cp)wif(top=0) return 1; /*?？?，出棧失敗返回*/w-top; wcp=stack top; /*完成出棧運(yùn)算*/wreturn 0; /*出棧成功，返回*/w3.1

4、.3 鏈?zhǔn)酱鎯?chǔ)棧w棧也可以用鏈表實(shí)現(xiàn)，用鏈表實(shí)現(xiàn)的棧稱為鏈?zhǔn)綏?。鏈表的第一個(gè)元素是棧頂結(jié)點(diǎn)，鏈表的末尾元素是棧底結(jié)點(diǎn)，鏈表的首表指針是棧頂指針top ,top為null的空鏈表是空棧。w設(shè)棧結(jié)點(diǎn)類型為：wtypedet struct node wNODE data; /*棧元值，某種NODE類型*/wstruct node *link;wLNODE;(一) 鏈?zhǔn)酱鎯?chǔ)棧的進(jìn)棧函數(shù)w示意圖 top top=p p-link=topw w p4 X 5 2 null函數(shù)定義w函數(shù)如下：wvoid L_push(NODE x,LNODE *top) /*設(shè)棧結(jié)點(diǎn)的數(shù)據(jù)類型為NODE*/wLNODE *

5、p=(LNODE *)malloc(sizeof(LNODE);wp-data=x;wp-link=top;wtop=p;w（二 ）鏈接存儲(chǔ)棧的出棧函數(shù)w示意圖wTopw p4 5 2 Null 函數(shù)定義 int L_pop(NODE *cp,LNODE *top) /*設(shè)棧結(jié)點(diǎn)的數(shù)據(jù)類型為NODE*/wLNODE *p=top;wif(top=NULL) return 1;/*空棧*/w*cp=p-data;wtop=p-link;wfree(p);wreturn 0;/*出棧成功*/w3.2 3.2 隊(duì)隊(duì) 列列 w一、隊(duì)列定義、w隊(duì)列是只允許在一端進(jìn)行插入，另一端正進(jìn)行刪除的線性表，如圖3

6、-7所示。 出隊(duì) q0 q1 qi qi+1 qn-1 進(jìn)隊(duì) 隊(duì)首 隊(duì)尾w 圖3-7 隊(duì)列示意圖 w隊(duì)列中允許刪除運(yùn)算的一端稱隊(duì)首，允許插入運(yùn)算的一端稱為隊(duì)尾。習(xí)慣稱在隊(duì)列中插入結(jié)點(diǎn)操作為進(jìn)隊(duì)，隊(duì)列中刪除結(jié)點(diǎn)的操作為出隊(duì)。w若有隊(duì)Q=(q0,q1,qn-1),則q0為隊(duì)首結(jié)點(diǎn)，qn-1為隊(duì)尾結(jié)點(diǎn)。因最先進(jìn)入隊(duì)列的結(jié)點(diǎn)將最先出隊(duì)，所以隊(duì)列具有先進(jìn)先出（First In First Out簡(jiǎn)稱FIFO）的特性。w隊(duì)列的基本操作包括：創(chuàng)建一個(gè)隊(duì)列，入列，出隊(duì)，讀取隊(duì)首元素，判隊(duì)空，請(qǐng)隊(duì)列空，求當(dāng)前隊(duì)列中的元素個(gè)數(shù)，撤消一個(gè)隊(duì)列等。3.2.1 順序存儲(chǔ)隊(duì)列w可以用順序存儲(chǔ)線性表來(lái)表示隊(duì)列，為了指明當(dāng)前

7、執(zhí)行出隊(duì)運(yùn)算的隊(duì)首位置，需一個(gè)游標(biāo)變量front（習(xí)慣上稱為頭指針），為了指明當(dāng)前執(zhí)行進(jìn)隊(duì)運(yùn)算的隊(duì)尾位置，需要一個(gè)游標(biāo)變量rear（習(xí)慣上稱為尾指針）。w開(kāi)始時(shí)，讓隊(duì)列front度rear都指向數(shù)組的前端，這是一個(gè)空隊(duì)列。在隊(duì)列未滿情況下，隊(duì)列可執(zhí)行進(jìn)隊(duì)運(yùn)算。進(jìn)隊(duì)時(shí)，首先讓rear加1,變?yōu)橹赶蜿?duì)列新結(jié)點(diǎn)的存放下標(biāo)，然后將新結(jié)點(diǎn)送到由rear所指的數(shù)組元素中。隊(duì)列非空時(shí)，可執(zhí)行出隊(duì)運(yùn)算。出隊(duì)時(shí)，首先把front所指的隊(duì)列首結(jié)點(diǎn)送到接受結(jié)點(diǎn)的變量中，然后讓front加1，使front指向新的隊(duì)首結(jié)點(diǎn)。出入隊(duì)列的狀態(tài)示意圖環(huán)形隊(duì)列(1)w若用有MAXN個(gè)元素的數(shù)組表示隊(duì)列，隨著一系列進(jìn)隊(duì)和出隊(duì)運(yùn)算

8、，隊(duì)列的結(jié)點(diǎn)移向存放隊(duì)列的數(shù)組的尾端，會(huì)出現(xiàn)數(shù)組的前端空著，而隊(duì)列空間已用完的情況。一種可行的解決方法是當(dāng)發(fā)生這樣的情況時(shí)，把隊(duì)列中的結(jié)點(diǎn)移到數(shù)組的前端，并修改頭指針和尾指針。另一種更好的解決辦法是采用環(huán)形隊(duì)列。w環(huán)形隊(duì)列就是將實(shí)現(xiàn)隊(duì)列的數(shù)組q的首元q0與末元qmax-1連接起來(lái)。隊(duì)空的初態(tài)為front=rear=0；在環(huán)形隊(duì)列中，當(dāng)rear趕上front時(shí)，隊(duì)列滿。反之，當(dāng)front趕上rear時(shí)，隊(duì)列為空。這樣隊(duì)空或隊(duì)滿的條件都同為front=rear，這給程序判別隊(duì)空或隊(duì)滿帶來(lái)不便。為此采用當(dāng)隊(duì)列只剩下一個(gè)空閑結(jié)點(diǎn)的空間時(shí)，就認(rèn)為隊(duì)列已滿的簡(jiǎn)單辦法以區(qū)別隊(duì)空和隊(duì)滿。示意圖如下：w隊(duì)列出、

9、入隊(duì)操作示例： 環(huán)形隊(duì)列(2)在下面的入列和出隊(duì)算法中，queue數(shù)組用來(lái)存放隊(duì)列元素，頭指針為front，尾指針為rear，數(shù)據(jù)結(jié)構(gòu)定義如下：#define MAX 50int queueMAX；int front=-1,rear= -1;1、順序隊(duì)列的進(jìn)隊(duì)列算法：隊(duì)滿時(shí)返回eof，否則返回0int insert_queue (int x) if (rear= =MAX-1) return(eof); queue+rear=x; return(0);環(huán)形隊(duì)列(3)2、順序隊(duì)列出隊(duì)列算法：隊(duì)空時(shí)返回eof，否則返回y值wint delete_queue()w int y ;w if (fron

10、t= =rear) return(eof);w y=queue+front;w return(y);w3、入循環(huán)隊(duì)列wint inset_q(int q, int x)w int front,rear;w if (rear+1)%MAX)= =front) return(eof);welse rear=(rear+1)%MAX;w qrear=x;w return(1);w w環(huán)形隊(duì)列（4）4、出循環(huán)隊(duì)列int delete_q(int q, int y) int front,rear; if(front= = rear) return(0); front=(front+1)%MAX; y=q

11、front; return(y);3.2.2鏈?zhǔn)酱鎯?chǔ)隊(duì)列 隊(duì)列也可以用鏈表實(shí)現(xiàn)，用鏈表實(shí)現(xiàn)的隊(duì)列稱為鏈?zhǔn)疥?duì)列。鏈表的第一個(gè)表示是隊(duì)列首結(jié)點(diǎn)，鏈表的末尾表示是隊(duì)列的隊(duì)尾結(jié)點(diǎn)，隊(duì)尾結(jié)點(diǎn)的鏈接指針值為null。隊(duì)列的頭指針hpt指向隊(duì)列的首結(jié)點(diǎn)，隊(duì)列的尾指針tpt指向隊(duì)尾結(jié)點(diǎn)。當(dāng)隊(duì)列的頭指針hpt值為null時(shí)，隊(duì)列為空。設(shè)有：wtypedef struct nodew node data;w struct node *link;w Lnode;一、鏈?zhǔn)疥?duì)列進(jìn)隊(duì)函數(shù)w示意圖 tptwhpt p A X nullB C null鏈?zhǔn)疥?duì)列進(jìn)隊(duì)函數(shù)定義wvoid Len_queue(Lnode *hpt,

12、Lnode *tpt,node x) w Lnode *p=(Lnode *)malloc(sizeof(Lnode);w p-data=x;w p-link=null;w if (hpt= =null)tpt=hpt=p;welse tpt = (= (tpt)-link=p;w 二、鏈?zhǔn)疥?duì)列出隊(duì)函數(shù)w示意圖 hpt=hpt-link tptwhpt pA B C null鏈?zhǔn)疥?duì)列出隊(duì)函數(shù)定義wint Lde_queue(Lnode *hpt,Lnode *tpt,node *cp)w Lnode *p= hpt;w if(hpt= =null) return 1; /* 隊(duì)空*/w*cp=

13、 (hpt)-data;whpt=(hpt)-link;wif(hpt= = null) tpt=null;wfree (p);wreturn 0;w 舉例(1)wP33 二w1向一個(gè)棧頂指針為Top的鏈棧中插入一個(gè)S所指的結(jié)點(diǎn)時(shí)，其進(jìn)行的操作是（ ）。w2從棧頂指針為Top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將結(jié)點(diǎn)保存在X中，進(jìn)行的操作是（ ）。w3在具有N個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有（ ）個(gè)元素。w4假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)輸入序列a,b,c,d,e進(jìn)行一系列操作SSXSXSSXXX之后，得到的輸出序列為（ ）。w5設(shè)有數(shù)組A0.m作為循環(huán)隊(duì)列的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則元素x執(zhí)行入隊(duì)操作的語(yǔ)句是（