資源描述：
《數(shù)據(jù)結(jié)構(gòu)第3棧和隊列ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第三章棧和隊列本章要點棧和隊列的定義、特點棧和隊列基本操作算法的實現(xiàn)棧和隊列的應(yīng)用3.1棧3.1.1棧的定義及基本運算棧是限制在表的一端進行插入和刪除操作的線性表。允許插入、刪除的這一端稱為棧頂，另一個固定端稱為棧底。當表中沒有元素時稱為空棧。常做的基本運算有：（1）棧初始化：Init_SeqStack(s)初始條件：棧s不存在操作結(jié)果：構(gòu)造了一個空棧。（2）判?？眨篍mpty_SeqStack(s)初始條件：棧s已存在操作結(jié)果：若s為空棧返回為1，否則返回為0。（3）入棧：Push_SeqStack(s，x
2、)初始條件：棧s已存在操作結(jié)果：在棧s的頂部插入一個新元素x，x成為新的棧頂元素。棧發(fā)生變化。常做的基本運算有：（4）出棧：Pop_SeqStack(s)初始條件：棧s存在且非空操作結(jié)果：棧s的頂部元素從棧中刪除，棧中少了一個元素。（5）取棧頂元素：Get_SeqStack(s)初始條件：棧s存在且非空操作結(jié)果：棧頂元素作為結(jié)果返回，棧不變化。3.1.2棧的存儲實現(xiàn)和運算實現(xiàn)1．順序棧利用順序存儲方式實現(xiàn)的棧稱為順序棧。順序棧的類型描述如下：#defineMaxSize50typedefstruct{Data
3、typedata[MaxSize];inttop;}SeqStack定義一個指向順序棧的指針：SeqStack*s;通常0下標端設(shè)為棧底，這樣空棧時棧頂指針top=-1;入棧:棧頂指針+１，即s->top++;出棧:棧頂指針-１，即s->top--。如圖3-2所示。圖(a)空棧，圖(c)是A、B、C、D、E5個元素依次入棧，圖(d)是E、D出棧后3個元素，理解棧頂指針的作用。（1）初始化空棧初始條件：棧不存在。操作結(jié)果：構(gòu)造一個空棧。操作步驟：創(chuàng)建一個SeqStack類型的結(jié)構(gòu)體指針s，并返回指針s。算法3.
4、1如下：voidInit_SeqStack(SeqStack*s)//算法3.1{s->top=-1;}（2）判斷空棧初始條件：棧存在。操作結(jié)果：判斷棧是否為空。操作步驟：判斷棧s是否為空，如果為空返回1，否則返回0。算法3.2如下：intEmpty_SeqStack(SeqStack*s){if(s->top==-1)return1;elsereturn0;}top-1進棧操作AB（3）入棧初始條件：棧s存在。操作結(jié)果：在棧s的頂部插入一個新元素x，x成為新的棧頂元素。intPush_SeqStack(Se
5、qStack*s,Datatypex){if(s->top==MaxSize-1){printf("溢出");return0;}else{s->top++;s->data[s->top]=x;return1;}}CD（4）出棧初始條件：棧s存在。操作結(jié)果：棧s的頂部元素從棧中刪除。DatatypePop_SeqStack(SeqStack*s){Datatypex;if(Empty_SeqStack(s)){printf("棧空");x='
