1、,第三章 棧和隊(duì)列,3.1棧及其基本運(yùn)算 3.2棧的實(shí)現(xiàn) 3.3棧的應(yīng)用 3.4隊(duì)列 3.5隊(duì)列的實(shí)現(xiàn) 3.6隊(duì)列的應(yīng)用,從結(jié)點(diǎn)間的邏輯關(guān)系看， 棧和隊(duì)列也是線(xiàn)性表，只不過(guò)是操作受限的特殊的線(xiàn)性表。 但從抽象數(shù)據(jù)類(lèi)型角度看，它們是和線(xiàn)性表不相同的兩種數(shù)據(jù)結(jié)構(gòu)。在計(jì)算機(jī)科學(xué)和程序設(shè)計(jì)中有廣范的應(yīng)用。,棧的基本概念,棧：一種特殊的線(xiàn)性表，它所有的插入和刪除都限制在表的同一端進(jìn)行。 棧頂：表中允許進(jìn)行插入、刪除操作的一端叫做棧的棧頂，棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)變化的，常用一個(gè)稱(chēng)為棧頂指針的變量來(lái)標(biāo)識(shí)。 棧底：表的另一端則叫做棧的底。 空棧：當(dāng)棧中沒(méi)有元素時(shí)，稱(chēng)之為空棧。 進(jìn)棧/出棧棧的插入運(yùn)算通常稱(chēng)為進(jìn)棧

2、或入棧，棧的刪除運(yùn)算通常稱(chēng)為退?；虺鰲?棧是限定在表的同一端進(jìn)行插入或刪除操作的線(xiàn) 性表。進(jìn)行插入或刪除操作的一端稱(chēng)為棧頂，另一 端稱(chēng)為棧底。如圖4.1。,棧的操作是按后進(jìn)先出的原則進(jìn)行的。又稱(chēng)為后進(jìn)先出（LIFO）表。,3.1棧及其基本運(yùn)算,棧的基本運(yùn)算,創(chuàng)建一個(gè)空棧； 判斷棧是否為空棧； 往棧中插入（或稱(chēng)推入）一個(gè)元素； 從棧中刪除（或稱(chēng)彈出）一個(gè)元素； 求棧頂元素的值。,棧的溢出,當(dāng)棧中已經(jīng)有MAXNUM個(gè)元素時(shí)，如果再作進(jìn)棧運(yùn)算，則會(huì)產(chǎn)生溢出，稱(chēng)為上溢（Overflow）； 而對(duì)空棧進(jìn)行出棧運(yùn)算時(shí)也會(huì)產(chǎn)生溢出，通常稱(chēng)為下溢（Underflow）。,3.2棧的實(shí)現(xiàn),4.2.1順序表示 4

3、.2.2鏈接表示,順序表示的棧的定義： #define MAXNUM 100 /* 棧中能達(dá)到的最大容量*/ typedef int DataType; /* 定義棧元素的數(shù)據(jù)類(lèi)型* / struct SeqStack /* 順序棧類(lèi)型定義 */ DataType sMAXNUM; int t; /*棧頂*/ ； typedef struct SeqStack, *pSeqStack; pSeqStack pastack; /*指向順序棧的指針變量*/,3.2.1順序表示,順序表示棧基本運(yùn)算的實(shí)現(xiàn),算法3.1 創(chuàng)建空棧PSeqStack createEmptyStack_seq( void )

4、 算法3.2 判斷棧是否為空棧 int isEmptyStack_seq( PSeqStack pastack ) 算法3.3 進(jìn)棧void push_seq( PSeqStack pastack, DataType x ) 算法3.4 出棧void pop_seq( PSeqStack pastack ) 算法3.5 取棧頂元素DataType top_seq( PSeqStack pastack ),創(chuàng)建一個(gè)空棧,為棧結(jié)構(gòu)申請(qǐng)空間，并將棧頂變量賦值為-1 pSeqStack CreateEmptyStack_seq( void ) pSeqStack pastack; pastack= (

5、pSeqStack)malloc(sizeof(struct SeqStack); if (pastack=NULL) printf(Out of space! n); elsepastack-t=-1; /棧頂指針總是指向頂部元素 return (pastack); ,判斷棧是否為空,當(dāng)pastack所指的棧為空棧時(shí)，則返回1，否則返回0 int isEmptyStack_seq( PSeqStack pastack) return ( pastack-t = -1); ,進(jìn)棧操作,往pastack所指的棧中插入（推入）一個(gè)值為的元素。當(dāng)棧不滿(mǎn)時(shí)， 棧頂指針先加1，然后把元素x放入棧頂變量所

6、指的位置中。 void push_seq(PSeqStack pastack,DataTypex ) if(pastack-t = MAXNUM -1 ) printf( Overflow! n ); else pastack-t =pastack-t + 1; pastack-spastack-t = x; ,出棧操作,出棧運(yùn)算，表示從pastack所指的棧中刪除（或稱(chēng)彈出）一個(gè)元素。 void pop_seq( pSeqStack pastack) / 刪除棧頂元素 if (pastack-t = = -1) printf( Underflow!n ); else pastack-t =

7、pastack-t -1; ,取棧頂元素,取棧頂元素運(yùn)算，當(dāng)pastack所指的棧不為空棧時(shí)，將棧頂元素取出，而棧本身未發(fā)生任何變化。 DataType top_seq( PSeqStack pastack) /* 當(dāng)pastack所指的棧不為空棧時(shí)，求棧頂元素的值*/ return (pastack-spastack-t); ,3.2.2 鏈接表示,鏈接表示的棧的定義： typedef int DataType; struct Node; typedef struct Node *pNode; struct Node /* 單鏈表結(jié)點(diǎn)結(jié)構(gòu) */ DataType info; pNode li

8、nk; ; struct LinkStack/* 鏈接棧類(lèi)型定義 */ pNode top;/* 指向棧頂結(jié)點(diǎn) */ ; typedef struct LinkStack *PLinkStack;,pLinkstack plstack; /*變量聲明*/,plstack,top,info,link,圖4.3 棧的鏈接表示,鏈接表示?；具\(yùn)算的實(shí)現(xiàn),算法4.6 創(chuàng)建空棧PLinkStack createEmptyStack_link(void) 算法4.7 判斷棧是否為空棧 int isEmptyStack_link( PLinkStack plstack ) 算法4.8 進(jìn)棧void push

9、_link( PLinkStack plstack, DataType x ) 算法4.9 出棧void pop_link( PLinkStack plstack ) 算法4.10 取棧頂元素DataType top_link( PLinkStack plstack ),創(chuàng)建空鏈接棧,申請(qǐng)鏈棧結(jié)構(gòu)空間，創(chuàng)建一空鏈接棧，返回指向空鏈接棧的指針。 PLinkStack createEmptyStack_link(void) PLinkStack plstack; plstack= (PLinkStack)malloc(sizeof(struct LinkStack); if (plstack!=

10、NULL) plstack-top = NULL; else printf(Out of space! n); return (plstack); ,判斷鏈接棧是否為空棧,判斷plstack所指的棧是否為空棧，當(dāng)plstack所指的棧為空棧時(shí)，則返回1，否則返回0。 int isEmptyStack_link( PLinkStack plstack) return (plstack-top = NULL); ,鏈接棧的進(jìn)棧操作,往plstack所指的棧中插入（或稱(chēng)推入）一個(gè)值為x的元素。首先申請(qǐng)結(jié)點(diǎn)空間，然后通過(guò)指針修改，將結(jié)點(diǎn)插在棧頂指針后。 void push_link(PLinkStac

11、k plstack,DataTypex ) PNode p; p = (PNode)malloc(sizeof(structNode ) ); if ( p = NULL ) printf(Out of space!n); else p-info = x; p-link =plstack-top; plstack-top = p; ,鏈接棧的出棧操作,出棧運(yùn)算，表示從plstack所指的棧中刪除（或稱(chēng)彈出）一個(gè)元素。當(dāng)棧不空時(shí)，直接修改棧頂指針，刪除結(jié)點(diǎn)。 void pop_link( PLinkStack plstack) PNode p; if( isEmptyStack_link( pl

12、stack) ) printf( Empty stack pop.n ); else p = plstack-top; plstack-top = plstack-top-link; free(p); ,鏈接棧取棧頂元素,當(dāng)plstack所指的棧不空時(shí)，取棧頂元素的值，棧保持不變 DataType top_link( PLinkStack plstack) /* 對(duì)非空棧求棧頂元素*/ return (plstack-top-info); ,3.3棧的應(yīng)用,3.3.1棧與遞歸 遞歸 遞歸函數(shù)到非遞歸函數(shù)的轉(zhuǎn)換 3.3.3表達(dá)式計(jì)算 后綴表達(dá)式的求值 中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換,如果一個(gè)結(jié)構(gòu)定

13、義中有的部分是由與自己同樣的結(jié)構(gòu)組成，則稱(chēng)為遞歸的定義。 一個(gè)遞歸定義必須一步比一步簡(jiǎn)單，最后是有終結(jié)的（稱(chēng)為遞歸定義的出口），決不能無(wú)限循環(huán)下去。,3.3.1 棧與遞歸,一. 遞歸的定義,例1 簡(jiǎn)單算術(shù)表達(dá)式 （a）常數(shù)，變量，函數(shù)引用是表達(dá)式； （b) 若e1,e2是表達(dá)式, op為運(yùn)算符，則 e1 op e2, op e1, (e1) 也是表達(dá)式。,遞歸舉例：,算法3.11 階乘的遞歸計(jì)算 int fact (int n) if (n = = 0) return 1; else return(n*fact(n-1); ; r2 main( ) int n; scanf(“%dn”, r1

14、,3,r1,2,r2,1,r2,0,r2,1,1,2,6,調(diào)用前： （1）為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)； （活動(dòng)記錄， 數(shù)據(jù)區(qū)） （2）將所有的實(shí)參、返回地址傳遞給被調(diào)用函數(shù)； 實(shí)參和形參的結(jié)合，傳值。 （3）將控制轉(zhuǎn)移到被調(diào)用函數(shù)入口。 調(diào)用后返回： （1）保存被調(diào)用函數(shù)的計(jì)算結(jié)果； （2）釋放被調(diào)用函數(shù)的存儲(chǔ)區(qū)； （3）依照被調(diào)用函數(shù)保存的返回地址將控制轉(zhuǎn) 移到調(diào)用函數(shù)。,二. 遞歸函數(shù)到非遞歸函數(shù)的轉(zhuǎn)換,函數(shù)嵌套調(diào)用時(shí)，按照“后調(diào)用先返回”的原則進(jìn)行。,int main() int m,n; . first(m,n); 1: ,int first(int s, int t) int

15、i; second(i); 2: ,int second(int d) intx,y; 3: ,聲明部分；,int i, j; 函數(shù)1；,int i, j; 函數(shù)2；,算法3.12 階乘的非遞歸計(jì)算 程序員自己管理一個(gè)棧，并模擬函數(shù)調(diào)用的執(zhí)行過(guò)程。 int nfact(int n); int res; pSeqStack st; st=createEmptyStack-seq(); while (n0) while (!isEmptyStack-seq(st) push-seq(st,n); res=res*top-seq(st); n=n-1; pop-seq(st); res=1; fre

16、e(st); return(st); ,3.3.3 表達(dá)式求值,(1) 假定所有運(yùn)算分量都是整數(shù)； (2) 所有運(yùn)算符都是整數(shù)的二元操作，且都用一個(gè)字符表示。,3*（7+3*6/2-5） 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式： 3 7 3 6* 2 / + 5 - * 基本方法是：利用一個(gè)運(yùn)算符棧,(1)棧初始化。 (2)從左到右掃描向量IFX，重復(fù)下述兩步操作，直到表達(dá)尾。 從IFX中取出下個(gè)TOKEN(數(shù)字、運(yùn)算符、左括號(hào)、右括號(hào))； CASE TOKEN OF (：將TOKEN壓入棧S; 操作數(shù)：將操作數(shù)直接送入PFX; 操作符：如?？栈騎OKEN比棧頂元素優(yōu)先級(jí)高，將TOKEN進(jìn)棧；否則，退棧并

17、將退棧元素送入PFX，然后再將TOKEN與新棧頂元素比較之; ）：退棧并將退棧元素送PFX，直到碰到左括號(hào)，左括號(hào)退棧不送PFX。 (3)當(dāng)遇到中綴表達(dá)式結(jié)束符號(hào)，連續(xù)退棧并送退棧元素到PFX，直至棧空。,計(jì)算后綴表達(dá)式： 3 7 3 6* 2 / + 5 - * 方法：利用一個(gè)運(yùn)算對(duì)象棧,(1)棧初始化。 (2)從左到右掃描向量PFX，重復(fù)下述兩步操作，直到表達(dá)式尾。 從PFX中取出下個(gè)TOKEN(操作數(shù)、運(yùn)算符) CASE TOKEN OF 操作數(shù)：將操作數(shù)直接送入棧S1; 操作符：出棧兩個(gè)操作數(shù)，對(duì)其進(jìn)行TOKEN操作，結(jié)果壓人棧S1 (3)當(dāng)遇到后綴表達(dá)式結(jié)束符號(hào)，棧頂?shù)闹稻褪墙Y(jié)果(應(yīng)

18、是棧中唯一元素)。,3.4 隊(duì)列,隊(duì)列也是一種特殊的線(xiàn)性表，對(duì)于它所有的插入都在表的一端進(jìn)行，所有的刪除都在表的另一端進(jìn)行。進(jìn)行刪除的這一端叫隊(duì)列的頭，進(jìn)行插入的這一 端叫隊(duì)列的尾。當(dāng)隊(duì)列中沒(méi)有任何元素時(shí)，稱(chēng)為空隊(duì)列。隊(duì)列也稱(chēng)作先進(jìn)先出表。,k1 k2 k3 . kn-1,隊(duì)頭,隊(duì)尾,進(jìn)隊(duì),出隊(duì),隊(duì)列的基本運(yùn)算： 創(chuàng)建一個(gè)空隊(duì)列 Queue createEmptyQueue ( void ) 判隊(duì)列是否為空隊(duì)列 int isEmptyQueue ( Queue qu ) 往隊(duì)列中插入一個(gè)元素 void enQueue ( Queue qu, DataType x ) 從隊(duì)列中刪除一個(gè)元素 vo

19、id deQueue ( Queue qu ) 求隊(duì)列頭部元素的值 DataType frontQueue ( Queue qu ),3.5隊(duì)列的實(shí)現(xiàn),3.5.1順序表示 3.5.2鏈接表示,3.5.1 隊(duì)列的順序表示,#define MAXNUM /* 隊(duì)列中最大元素個(gè)數(shù) */ struct SeqQueue/* 順序隊(duì)列類(lèi)型定義 */ DataType qMAXNUM; int f,r；/f 指向隊(duì)列頭，r 指向隊(duì)列尾 ; /* 順序隊(duì)列類(lèi)型的指針類(lèi)型 */ typedef struct SeqQueue *PSeqQueue;,約定,設(shè)paqu是PSeqQueue類(lèi)型的變量，則頭變量pa

20、qu-f存放即將要被刪除的元素的下標(biāo)，尾變量paqu-r存放即將要被插入的元素（當(dāng)前還不是隊(duì)列中的元素）的下標(biāo)。 初始時(shí)paqu-f = paqu-r = 0。 隊(duì)列中元素的個(gè)數(shù)可以用paqu-r -paqu-f計(jì)算得到，當(dāng)paqu-r = paqu-f時(shí)，元素的個(gè)數(shù)為0，即為空隊(duì)列。,隊(duì)列的溢出,當(dāng)隊(duì)列滿(mǎn)時(shí)，再作進(jìn)隊(duì)操作，這種現(xiàn)象稱(chēng)為上溢； 當(dāng)隊(duì)空時(shí)，作刪除操作，這種現(xiàn)象稱(chēng)為下溢。溢出現(xiàn)象在運(yùn)算中應(yīng)該加以考慮。 當(dāng)paqu-r = MAXNUM時(shí)，再作插入運(yùn)算就會(huì)產(chǎn)生溢出，如果這時(shí)隊(duì)列的前端還有許多空的（可用的）位置，這種現(xiàn)象稱(chēng)為假溢出。,解決假溢出通常采用的方法是： 把數(shù)組paqu-qMA

21、XNUM從邏輯上看成一個(gè)環(huán)，即規(guī)定paqu-q0是paqu-qMAXNUM -1的下一個(gè)元素。當(dāng)paqu-qMAXNUM -1已經(jīng)插入元素以后，就把paqu-r置成0，再有元素要插入時(shí)，就插到paqu-q0的位置上，這種隊(duì)列也稱(chēng)為環(huán)形隊(duì)列 如何區(qū)別循環(huán)隊(duì)列的空與滿(mǎn)？ 犧牲隊(duì)列中的一個(gè)結(jié)點(diǎn)，當(dāng)隊(duì)列中已有MAXNUM -1個(gè)結(jié)點(diǎn)時(shí)就稱(chēng)滿(mǎn)，再要插入就發(fā)生溢出,7,6,5,4,3,2,1,0,Q.front Q.rear,k1,k2,k3,k6,k5,隊(duì)列空,隊(duì)列數(shù)組越界,（）普通情況,圖(a)空隊(duì)列,圖(b)隊(duì)列滿(mǎn)，判斷 (Q.rear+1) = = Q.front,（）循環(huán)隊(duì)列,圖3.9 循環(huán)隊(duì)列

22、,算法3.16 創(chuàng)建一個(gè)空隊(duì)列 PSeqQueue createEmptyQueue_seq( void ) 算法3.17 判斷隊(duì)列是否為空隊(duì)列 int isEmptyQueue_seq( PSeqQueue paqu ) 算法3.18 進(jìn)隊(duì)列運(yùn)算 void enQueue_seq( PSeqQueue paqu, DataType x ） 算法3.19 出隊(duì)列運(yùn)算 void deQueue_seq( PSeqQueue paqu ) 算法3.20 取隊(duì)列頭部元素的值 DataType frontQueue_seq( PSeqQueue paqu ),環(huán)形隊(duì)列中實(shí)現(xiàn)隊(duì)列基本運(yùn)算的算法,PSeq

23、Queue createEmptyQueue_seq( void ) PSeqQueue paqu; paqu= (PSeqQueue)malloc(sizeof(struct SeqQueue); if (paqu=NULL) printf(Out of space! n); else paqu-f = 0; paqu-r = 0; return (paqu); ,void enQueue_seq( PSeqQueue paqu, DataTypex ) 當(dāng)隊(duì)列不滿(mǎn)時(shí)，將元素x插入paqu所指的隊(duì)列中。 void enQueue_seq( PSeqQueue paqu, DataTypex

24、) if( (paqu-r + 1) %MAXNUM = paqu-f ) printf( Full queue.n ); else paqu-qpaqu-r = x; paqu-r = (paqu-r + 1) % MAXNUM; ,void deQueue_seq( PSeqQueue paqu) 出隊(duì)列運(yùn)算，當(dāng)隊(duì)列不空時(shí)，從paqu所指的隊(duì)列中刪除一個(gè)元素 void deQueue_seq( PSeqQueue paqu if( paqu-f = paqu-r ) printf( Empty Queue.n ); else paqu-f = (paqu-f + 1) % MAXNUM;

25、,DataType frontQueue_seq( PSeqQueue paqu) 當(dāng)paqu所指的隊(duì)列不空時(shí)，取隊(duì)列頭部元素，隊(duì)列本身保持不變。 DataType frontQueue_seq( PSeqQueue paqu） return (paqu-qpaqu-f); ,struct Node; typedef struct Node *pNode; struct Node DataType info; pNodelink; ; struct LinkQueue PNodef; PNoder; ; typedef struct LinkQueue, *PLinkQueue;,3.5.2

26、隊(duì)列的鏈接表示,k0,k1,k2,kn-1,.,圖3.10 隊(duì)列的鏈接表示,plqu,f,r,算法3.21 創(chuàng)建一個(gè)空隊(duì)列 PLinkQueue createEmptyQueue_link( ) 算法3.22 判斷隊(duì)列是否為空隊(duì)列 int isEmptyQueue_link( PLinkQueue plqu ) 算法3.23 進(jìn)隊(duì)列運(yùn)算 void enQueue_link( PLinkQueue plqu, DataType x ) 算法3.24 出隊(duì)列運(yùn)算 void deQueue_link( PLinkQueue plqu ) 算法3.25 取隊(duì)列頭部元素的值 DataType frontQueue_link( PLinkQueue plqu ),鏈接隊(duì)列中實(shí)現(xiàn)隊(duì)列基本運(yùn)算的算法,PLinkQueue createEmptyQueue_link( ) 申請(qǐng)隊(duì)列結(jié)構(gòu)空間，創(chuàng)建一個(gè)空隊(duì)列。 PLinkQueue createEmptyQueue_link( ) PLinkQueue plqu; plqu= (PLinkQueue)malloc(sizeof(struct LinkQueue); if (plqu!=NULL) plqu-f = NULL; pl