數(shù)據(jù)結(jié)構(gòu)新-第3章棧和隊(duì)列

1、第3章 棧和隊(duì)列 3.1 棧 3.2 隊(duì)列 本章小結(jié) 3.1.1 棧的定義 3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn) 3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)3.1.4 棧的應(yīng)用例子3.1 棧 棧是一種只能在一端進(jìn)行插入或刪除操作的線性表。表中允許進(jìn)行插入、刪除操作的一端稱為棧頂。 棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)的,棧頂?shù)漠?dāng)前位置由一個(gè)稱為棧頂指針的位置指示器指示。表的另一端稱為棧底。 當(dāng)棧中沒有數(shù)據(jù)元素時(shí),稱為空棧。 棧的插入操作通常稱為進(jìn)棧或入棧,棧的刪除操作通常稱為退?；虺鰲！?.1.1 棧的定義 棧頂棧底出棧進(jìn)棧棧示意圖 例3.1 設(shè)有4個(gè)元素a、b、c、d進(jìn)棧,給出它們所有可能的出棧

2、次序。 答:所有可能的出棧次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba 例3.2 設(shè)一個(gè)棧的輸入序列為A,B,C,D,則借助一個(gè)棧所得到的輸出序列不可能是 。(A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C 答:可以簡單地推算,得容易得出D,A,B,C是不可能的,因?yàn)镈先出來,說明A,B,C,D均在棧中,按照入棧順序,在棧中順序應(yīng)為D,C,B,A,出棧的順序只能是D,C,B,A。所以本題答案為D。 例3.3 已知一個(gè)棧的進(jìn)棧序列是1,2,3,n,其

3、輸出序列是p1,p2,pn,若p1=n,則pi的值 。(A) i (B) n-i (C) n-i+1 (D) 不確定 答:當(dāng)p1=n時(shí),輸出序列必是n,n-1,3,2,1,則有: p2=n-1, p3=n-2, , pn=1推斷出pi=n-i+1,所以本題答案為C。 例3.4 設(shè)n個(gè)元素進(jìn)棧序列是1,2,3,n,其輸出序列是p1,p2,pn,若p1=3,則p2的值 。(A) 一定是2(B) 一定是1(C) 不可能是1 (D) 以上都不對 答:當(dāng)p1=3時(shí),說明1,2,3先進(jìn)棧,立即出棧3,然后可能出棧,即為2,也可能4或后面的元素進(jìn)棧,再出棧。因此,p2可能是2,也可能是4,n,但一定不能是1

4、。所以本題答案為C。棧的幾種基本運(yùn)算如下: (1) 初始化棧InitStack(&s):構(gòu)造一個(gè)空棧s。 (2) 銷毀棧ClearStack(&s):釋放棧s占用的存儲(chǔ)空間。 (3) 求棧的長度StackLength(s):返回棧s中的元素個(gè)數(shù)。 (4) 判斷棧是否為空StackEmpty(s):若棧s為空,則返回真；否則返回假。 (5) 進(jìn)棧Push(&S,e):將元素e插入到棧s中作為棧頂元素。 (6) 出棧Pop(&s,&e):從棧s中退出棧頂元素,并將其值賦給e。 (7) 取棧頂元素GetTop(s,&e):返回當(dāng)前的棧頂元素,并將其值賦給e。 (8) 顯示棧中元素DispStack(

5、s):從棧頂?shù)綏５醉樞蝻@示棧中所有元素。3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn) 假設(shè)棧的元素個(gè)數(shù)最大不超過正整數(shù)MaxSize,所有的元素都具有同一數(shù)據(jù)類型ElemType,則可用下列方式來定義棧類型SqStack: typedef struct ElemType dataMaxSize； int top；/*棧指針*/ SqStack；順序棧進(jìn)棧和出棧示意圖在順序棧中實(shí)現(xiàn)棧的基本運(yùn)算算法: (1) 初始化棧initStack(&s) 建立一個(gè)新的空棧s,實(shí)際上是將棧頂指針指向-1即可。對應(yīng)算法如下: void InitStack(SqStack *&s) s=(SqStack *)ma

6、lloc(sizeof(SqStack); s-top=-1; (2) 銷毀棧ClearStack(&s) 釋放棧s占用的存儲(chǔ)空間。對應(yīng)算法如下: void ClearStack(SqStack *&s) free(s); (3) 求棧的長度StackLength(s) 返回棧s中的元素個(gè)數(shù),即棧指針加1的結(jié)果。對應(yīng)算法如下: int StackLength(SqStack *s) return(s-top+1); (4) 判斷棧是否為空StackEmpty(s) 棧S為空的條件是s-top=-1。對應(yīng)算法如下: int StackEmpty(SqStack *s) return(s-top=

7、-1); (5) 進(jìn)棧Push(&s,e) 在棧不滿的條件下,先將棧指針增1,然后在該位置上插入元素e。對應(yīng)算法如下: int Push(SqStack *&s,ElemType e) if (s-top=MaxSize-1) return 0;/*棧滿的情況,即棧上溢出*/s-top+; s-datas-top=e;return 1; (6) 出棧Pop(&s,&e) 在棧不為空的條件下,先將棧頂元素賦給e,然后將棧指針減1。對應(yīng)算法如下: int Pop(SqStack *&s,ElemType &e) if (s-top=-1) return 0; /*棧為空的情況,即棧下溢出*/e=s

8、-datas-top;s-top-;return 1; (7) 取棧頂元素GetTop(s) 在棧不為空的條件下,將棧頂元素賦給e。對應(yīng)算法如下: int GetTop(SqStack *s,ElemType &e) if (s-top=-1) return 0; /*棧為空的情況,即棧下溢出*/e=s-datas-top;return 1; (8) 顯示棧中元素DispStack(s) 從棧頂?shù)綏５醉樞蝻@示棧中所有元素。對應(yīng)算法如下: void DispStack(SqStack *s) int i;for (i=s-top;i=0;i-) printf(%c ,s-datai);print

9、f(n); 約瑟夫環(huán)(順序棧): ShiliJOESPH-seqlist.CPP用棧實(shí)現(xiàn)十進(jìn)制數(shù)轉(zhuǎn)換成其他進(jìn)制數(shù) 用棧數(shù)制轉(zhuǎn)換.CPP3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 采用鏈?zhǔn)酱鎯?chǔ)的棧稱為鏈棧,這里采用單鏈表實(shí)現(xiàn)。 鏈棧的優(yōu)點(diǎn)是不存在棧滿上溢的情況。我們規(guī)定棧的所有操作都是在單鏈表的表頭進(jìn)行的,下圖是頭結(jié)點(diǎn)為*lhead的鏈棧,第一個(gè)數(shù)據(jù)結(jié)點(diǎn)是棧頂結(jié)點(diǎn),最后一個(gè)結(jié)點(diǎn)是棧底結(jié)點(diǎn)。棧中元素自棧頂?shù)綏５滓来问莂1、a2、an。鏈棧示意圖 鏈棧中數(shù)據(jù)結(jié)點(diǎn)的類型LiStack定義如下: typedef struct linknode ElemType data;/*數(shù)據(jù)域*/ struct

10、 linknode *next;/*指針域*/ LiStack;在鏈棧中,棧的基本運(yùn)算算法如下: (1) 初始化棧initStack(&s) 建立一個(gè)空棧s。實(shí)際上是創(chuàng)建鏈棧的頭結(jié)點(diǎn),并將其next域置為NULL。對應(yīng)算法如下: void InitStack(LiStack *&s) s=(LiStack *)malloc(sizeof(LiStack);s-next=NULL; s (2) 銷毀棧ClearStack(&s) 釋放棧s占用的全部存儲(chǔ)空間。對應(yīng)算法如下: void ClearStack(LiStack *&s) LiStack *p=s-next; while (p!=NULL

11、) free(s);s=p;p=p-next; (3) 求棧的長度StackLength(s) 從第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始掃描單鏈表,用i記錄訪問的數(shù)據(jù)結(jié)點(diǎn)個(gè)數(shù),最后返回i值。對應(yīng)算法如下: int StackLength(LiStack *s) int i=0;LiStack *p;p=s-next;while (p!=NULL) i+;p=p-next; return(i); (4) 判斷棧是否為空StackEmpty(s) 棧S為空的條件是s-next=NULL,即單鏈表中沒有數(shù)據(jù)結(jié)點(diǎn)。對應(yīng)算法如下: int StackEmpty(LiStack *s) return(s-next=NULL)

12、; s (5) 進(jìn)棧Push(&s,e) 將新數(shù)據(jù)結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后。對應(yīng)算法如下: void Push(LiStack *&s,ElemType e) LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p-data=e;p-next=s-next; /*插入*p結(jié)點(diǎn)作為第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/ s-next=p; (6) 出棧Pop(&s,&e) 在棧不為空的條件下,將頭結(jié)點(diǎn)后繼數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)域賦給e,然后將其刪除。對應(yīng)算法如下: int Pop(LiStack *&s,ElemType &e) LiStack *p;if (s-next=NULL)

13、return 0; /*棧空的情況*/p=s-next;/*p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/e=p-data;s-next=p-next;free(p);return 1; (7) 取棧頂元素GetTop(s) 在棧不為空的條件下,將頭結(jié)點(diǎn)后繼數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)域賦給e。對應(yīng)算法如下: int GetTop(LiStack *s,ElemType &e) if (s-next=NULL) return 0; /*棧空的情況*/e=s-next-data;return 1; (8) 顯示棧中元素DispStack(s) 從第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始掃描單鏈表,并輸出當(dāng)前訪問結(jié)點(diǎn)的數(shù)據(jù)域值。對應(yīng)算法如下: void

14、DispStack(LiStack *s) LiStack *p=s-next; while (p!=NULL) printf(%c ,p-data);p=p-next; printf(n); 用鏈棧實(shí)現(xiàn)數(shù)據(jù)反向輸出： ShiliP63-linkstack.cpp約瑟夫環(huán)(鏈棧): ShiliJOSEPHUS-linklist.C 例3.5 假設(shè)表達(dá)式中允許包含三種括號(hào):圓括號(hào)、方括號(hào)和大括號(hào)。編寫一個(gè)算法判斷表達(dá)式中的括號(hào)是否正確配對。 解: 設(shè)置一個(gè)括號(hào)棧,掃描表達(dá)式：遇到左括號(hào)(包括(、和)時(shí)進(jìn)棧,遇到右括號(hào)時(shí),若棧是相匹配的左括號(hào),則出棧,否則,返回0。 若表達(dá)式掃描結(jié)束,棧為空,返回

15、1表示括號(hào)正確匹配,否則返回0。 int correct(char exp,int n) char stMaxSize; int top=-1,i=0,tag=1; while (i-1) tag=0; /*若棧不空,則不配對*/ return(tag); 3.2 隊(duì)列 3.2.1 隊(duì)列的定義 返回 3.2.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 3.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)3.2.4 隊(duì)列的應(yīng)用例子 隊(duì)列簡稱隊(duì),它也是一種運(yùn)算受限的線性表,其限制僅允許在表的一端進(jìn)行插入,而在表的另一端進(jìn)行刪除。 我們把進(jìn)行插入的一端稱做隊(duì)尾(rear),進(jìn)行刪除的一端稱做隊(duì)首(fron

16、t)。 向隊(duì)列中插入新元素稱為進(jìn)隊(duì)或入隊(duì),新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素；從隊(duì)列中刪除元素稱為出隊(duì)或離隊(duì),元素出隊(duì)后,其后繼元素就成為隊(duì)首元素。 3.2.1 隊(duì)列的定義 隊(duì)列的入隊(duì)和出隊(duì)操作示意圖 3.2.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 假設(shè)隊(duì)列的元素個(gè)數(shù)最大不超過整數(shù)MaxSize,所有的元素都具有同一數(shù)據(jù)類型ElemType,則順序隊(duì)列類型SqQueue定義如下: typedef struct ElemType dataMaxSize； int front,rear；/*隊(duì)首和隊(duì)尾指針*/ SqQueue 從前圖中看到,圖(a)為隊(duì)列的初始狀態(tài),有front=rear成立,該條件

17、可以作為隊(duì)列空的條件。 那么能不能用rear=MaxSize-1作為隊(duì)滿的條件呢？顯然不能,在圖(d)中,隊(duì)列為空,但仍滿足該條件。這時(shí)入隊(duì)時(shí)出現(xiàn)“上溢出”,這種溢出并不是真正的溢出,在elem數(shù)組中存在可以存放元素的空位置,所以這是一種假溢出。 為了能夠充分地使用數(shù)組中的存儲(chǔ)空間,把數(shù)組的前端和后端連接起來,形成一個(gè)環(huán)形的順序表,即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán),稱為循環(huán)隊(duì)列。 循環(huán)隊(duì)列首尾相連,當(dāng)隊(duì)首front指針滿足 front=MaxSize-1后,再前進(jìn)一個(gè)位置就自動(dòng)到0,這可以利用除法取余的運(yùn)算()來實(shí)現(xiàn): 隊(duì)首指針進(jìn)1:front=(front+1)MaxSize 隊(duì)尾指針

18、進(jìn)1:rear=(rear+1)MaxSize 循環(huán)隊(duì)列的除頭指針和隊(duì)尾指針初始化時(shí)都置0:front=rear=0。在入隊(duì)元素和出隊(duì)元素時(shí),指針都按逆時(shí)針方向進(jìn)1。 怎樣區(qū)分這兩者之間的差別呢?在入隊(duì)時(shí)少用一個(gè)數(shù)據(jù)元素空間,以隊(duì)尾指針加1等于隊(duì)首指針判斷隊(duì)滿,即隊(duì)滿條件為: (q-rear+1) % MaxSize=q-front隊(duì)空條件仍為: q-rear=q-front循環(huán)隊(duì)的入隊(duì)和出隊(duì)操作示意圖 在循環(huán)隊(duì)列中,實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法如下: (1) 初始化隊(duì)列InitQueue(&q) 構(gòu)造一個(gè)空隊(duì)列q。將front和rear指針均設(shè)置成初始狀態(tài)即0值。對應(yīng)算法如下: void Init

19、Queue(SqQueue *&q) q=(SqQueue *)malloc (sizeof(SqQueue);q-front=q-rear=0; (2) 銷毀隊(duì)列ClearQueue(&q) 釋放隊(duì)列q占用的存儲(chǔ)空間。對應(yīng)算法如下: void ClearQueue(SqQueue *&q) free(q); (3) 判斷隊(duì)列是否為空QueueEmpty(q) 若隊(duì)列q滿足q-front=q-rear條件,則返回1；否則返回0。對應(yīng)算法如下: int QueueEmpty(SqQueue *q) return(q-front=q-rear); (4) 入隊(duì)列enQueue(q,e) 在隊(duì)列不滿

20、的條件下,先將隊(duì)尾指針rear循環(huán)增1,然后將元素添加到該位置。對應(yīng)算法如下: int enQueue(SqQueue *&q,ElemType e) if (q-rear+1)%MaxSize=q-front) /*隊(duì)滿*/return 0;q-rear=(q-rear+1)%MaxSize;q-dataq-rear=e;return 1; (5) 出隊(duì)列deQueue(q,e) 在隊(duì)列q不為空的條件下,將隊(duì)首指針front循環(huán)增1,并將該位置的元素值賦給e。對應(yīng)算法如下: int deQueue(SqQueue *&q,ElemType &e) if (q-front=q-rear) /*

21、隊(duì)空*/return 0;q-front=(q-front+1)%MaxSize;e=q-dataq-front;return 1; 例3.6 什么是隊(duì)列的上溢現(xiàn)象和假溢出現(xiàn)象？解決它們有哪些方法？ 答: 在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中,設(shè)頭指針為front,隊(duì)尾指針rear,隊(duì)的容量(存儲(chǔ)空間的大小)為MaxSize。當(dāng)有元素加入到隊(duì)列時(shí),若 rear=MaxSize(初始時(shí)rear=0)則發(fā)生隊(duì)列的上溢現(xiàn)象,該元素不能加入隊(duì)列。 特別要注意的是隊(duì)列的假溢出現(xiàn)象:隊(duì)列中還有剩余空間但元素卻不能進(jìn)入隊(duì)列,造成這種現(xiàn)象的原因是由于隊(duì)列的操作方法所致。 解決隊(duì)列上溢的方法有以下幾種: (1) 建立一個(gè)足夠

22、大的存儲(chǔ)空間,但這樣做會(huì)造成空間的使用效率降低。 (2) 當(dāng)出現(xiàn)假溢出時(shí)可采用以下幾種方法: 采用平移元素的方法:每當(dāng)隊(duì)列中加入一個(gè)元素時(shí),隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置(當(dāng)然要有空閑的空間可供移動(dòng))； 每當(dāng)刪除一個(gè)隊(duì)頭元素時(shí),則依次移動(dòng)隊(duì)中的元素,始終使front指針指向隊(duì)列中的第一個(gè)位置； 采用循環(huán)隊(duì)列方式:把隊(duì)列看成一個(gè)首尾相接的循環(huán)隊(duì)列,在循環(huán)隊(duì)列上進(jìn)行插入或刪除運(yùn)算時(shí)仍然遵循“先進(jìn)先出”的原則。 例3.7 對于順序隊(duì)列來說,如果知道隊(duì)首元素的位置和隊(duì)列中元素個(gè)數(shù),則隊(duì)尾元素所在位置顯然是可以計(jì)算的。也就是說,可以用隊(duì)列中元素個(gè)數(shù)代替隊(duì)尾指針。編寫出這種循環(huán)順序隊(duì)列的初始化、入隊(duì)、

23、出隊(duì)和判空算法。 解: 當(dāng)已知隊(duì)首元素的位置front和隊(duì)列中元素個(gè)數(shù)count后:隊(duì)空的條件為:count=0隊(duì)滿的條件為:count=MaxSize計(jì)算隊(duì)尾位置rear: rear=(front+count)%MaxSize 對應(yīng)的算法如下: typedef struct ElemType dataMaxSize;int front;/*隊(duì)首指針*/int count;/*隊(duì)列中元素個(gè)數(shù)*/ QuType;/*隊(duì)列類型*/ void InitQu(QuType *&q) /*隊(duì)列q初始化*/ q=(QuType *)malloc(sizeof(QuType);q-front=0;q-cou

24、nt=0; int EnQu(QuType *&q,ElemType x)/*進(jìn)隊(duì)*/ int rear;if (q-count=MaxSize) return 0; /*隊(duì)滿上溢出*/else rear=(q-front+q-count+MaxSize)%MaxSize; /*求隊(duì)尾位置*/ rear=(rear+1)%MaxSize; /*隊(duì)尾位置進(jìn)1*/ q-datarear=x; q-count+; return 1; int DeQu(QuType *&q,ElemType &x)/*出隊(duì)*/if (q-count=0)/*隊(duì)空下溢出*/ return 0;else q-front=

25、(q-front+1)%MaxSize; x=q-dataq-front; q-count-; return 1;int QuEmpty(QuType *q)/*判空*/ return(q-count=0); 鏈隊(duì)組成: (1) 存儲(chǔ)隊(duì)列元素的單鏈表 (2) 指向隊(duì)頭和隊(duì)尾指針的鏈隊(duì)頭結(jié)點(diǎn) 3.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)鏈列的入隊(duì)和出隊(duì)操作示意圖單鏈表中數(shù)據(jù)結(jié)點(diǎn)類型QNode定義如下: typedef struct qnode ElemType data;/*數(shù)據(jù)元素*/struct qnode *next; QNode;鏈隊(duì)中頭結(jié)點(diǎn)類型LiQueue定義如下:typedef

26、 struct QNode *front;/*指向單鏈表隊(duì)頭結(jié)點(diǎn)*/ QNode *rear; /*指向單鏈表隊(duì)尾結(jié)點(diǎn)*/ LiQueue; 在鏈隊(duì)存儲(chǔ)中,隊(duì)列的基本運(yùn)算算法如下: (1) 初始化隊(duì)列InitQueue(q) 構(gòu)造一個(gè)空隊(duì)列,即只創(chuàng)建一個(gè)鏈隊(duì)頭結(jié)點(diǎn),其front和rear域均置為NULL,不創(chuàng)建數(shù)據(jù)元素結(jié)點(diǎn)。對應(yīng)算法如下: void InitQueue(LiQueue *&q) q=(LiQueue *)malloc(sizeof(LiQueue); q-front=q-rear=NULL; (2) 銷毀隊(duì)列ClearQueue(q) 釋放隊(duì)列占用的存儲(chǔ)空間,包括鏈隊(duì)頭結(jié)點(diǎn)和所有數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間。對應(yīng)算法如下: void ClearQueue(LiQueue *&q) QNode *p=q-front,*r;if (p!=NULL)/*釋放數(shù)據(jù)結(jié)點(diǎn)占用空間*/ r=p-next; while (r!=NULL) free(p); p=r;r=p-next; /*p和r指針同步后移*/ free(q);/*釋放鏈隊(duì)結(jié)點(diǎn)占用空間*/ (3) 判斷隊(duì)列是否為空QueueEmpty(q) 若鏈隊(duì)結(jié)點(diǎn)的rear域值為NULL,表示隊(duì)列為空,返回1；否則返回0