第3章 棧和隊(duì)列.ppt

《第3章 棧和隊(duì)列.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

2、設(shè)有4個元素a、b、c、d進(jìn)棧,給出它們所有可能的出棧次序。答:所有可能的出棧次序如下:abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba例3.2設(shè)一個棧的輸入序列為A,B,C,D,則借助一個棧所得到的輸出序列不可能是。(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

3、,出棧的順序只能是D,C,B,A。所以本題答案為D。例3.3已知一個棧的進(jìn)棧序列是1,2,3,…,n,其輸出序列是p1,p2,…,pn,若p1=n,則pi的值。(A)i(B)n-i(C)n-i+1(D)不確定答:當(dāng)p1=n時,輸出序列必是n,n-1,…,3,2,1,則有:p2=n-1,p3=n-2,…,pn=1推斷出pi=n-i+1,所以本題答案為C。例3.4設(shè)n個元素進(jìn)棧序列是1,2,3,…,n,其輸出序列是p1,p2,…,pn,若p1=3,則p2的值。(A)一定是2(B)一定是1(C)不可能是

4、1(D)以上都不對答:當(dāng)p1=3時,說明1,2,3先進(jìn)棧,立即出棧3,然后可能出棧,即為2,也可能4或后面的元素進(jìn)棧,再出棧。因此,p2可能是2,也可能是4,…,n,但一定不能是1。所以本題答案為C。棧的幾種基本運(yùn)算如下:(1)初始化棧InitStack(&s):構(gòu)造一個空棧s。(2)銷毀棧ClearStack(&s):釋放棧s占用的存儲空間。(3)求棧的長度StackLength(s):返回棧s中的元素個數(shù)。(4)判斷棧是否為空StackEmpty(s):若棧s為空,則返回真；否則返回假。(5)

5、進(jìn)棧Push(&S,e):將元素e插入到棧s中作為棧頂元素。(6)出棧Pop(&s,&e):從棧s中退出棧頂元素,并將其值賦給e。(7)取棧頂元素GetTop(s,&e):返回當(dāng)前的棧頂元素,并將其值賦給e。(8)顯示棧中元素DispStack(s):從棧頂?shù)綏５醉樞蝻@示棧中所有元素。3.1.2棧的順序存儲結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)假設(shè)棧的元素個數(shù)最大不超過正整數(shù)MaxSize,所有的元素都具有同一數(shù)據(jù)類型ElemType,則可用下列方式來定義棧類型SqStack:typedefstruct{ElemT

6、ypedata[MaxSize]；inttop；/*棧指針*/}SqStack；順序棧進(jìn)棧和出棧示意圖在順序棧中實(shí)現(xiàn)棧的基本運(yùn)算算法:(1)初始化棧initStack(&s)建立一個新的空棧s,實(shí)際上是將棧頂指針指向-1即可。對應(yīng)算法如下:voidInitStack(SqStack*&s){s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;}(2)銷毀棧ClearStack(&s)釋放棧s占用的存儲空間。對應(yīng)算法如下:voidClearStack(SqSt

7、ack*&s){free(s);}(3)求棧的長度StackLength(s)返回棧s中的元素個數(shù),即棧指針加1的結(jié)果。對應(yīng)算法如下:intStackLength(SqStack*s){return(s->top+1);}(4)判斷棧是否為空StackEmpty(s)棧S為空的條件是s->top==-1。對應(yīng)算法如下:intStackEmpty(SqStack*s){return(s->top==-1);}(5)進(jìn)棧Push(&s,e)在棧不滿的條件下,先將棧指針增1,然后在該位置上插入元素e。對

8、應(yīng)算法如下:intPush(SqStack*&s,ElemTypee){if(s->top==MaxSize-1)return0;/*棧滿的情況,即棧上溢出*/s->top++;s->data[s->top]=e;return1;}(6)出棧Pop(&s,&e)在棧不為空的條件下,先將棧頂元素賦給e,然后將棧指針減1。對應(yīng)算法如下:intPop(SqStack*&s,ElemType&e){if(s->top==-1)return0;/*棧為空的情況,即棧下溢出*/e=s->dat