資源描述：
《數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第三章棧和隊(duì)列【課前思考】1.什么是線性結(jié)構(gòu)？2.你見過餐館中一疊一疊的盤子嗎？如果它們是按1,2,…,n的次序往上疊的，那么使用時(shí)候的次序應(yīng)是什么樣的？3.在日常生活中，為了維持正常的社會秩序而出現(xiàn)的常見現(xiàn)象是什么？第三章棧和隊(duì)列棧和隊(duì)列與線性表相比，是限定性的線性表結(jié)構(gòu)。棧的特點(diǎn)：棧必須按“后進(jìn)先出”的規(guī)則進(jìn)行操作隊(duì)列特點(diǎn)：必須按“先進(jìn)先出”的規(guī)則進(jìn)行操作。插入刪除線性表：Insert(L,i,x)Delete(L,i)(1≤i≤n+1)(1≤i≤n)棧：Insert(L,n+1,x)Delete(L,n)隊(duì)列：Insert(L,n+1,x)Del
2、ete(L,1)1.從“數(shù)據(jù)結(jié)構(gòu)”的角度看，它們都是線性結(jié)構(gòu)即數(shù)據(jù)元素之間的關(guān)系相同。2.它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對插入和刪除操作的“限定”。如：線性表允許在表內(nèi)任一位置進(jìn)行插入和刪除； 棧只允許在表尾一端進(jìn)行插入和刪除； 隊(duì)列只允許在表尾一端插入，在表頭一端刪除。棧和隊(duì)列與線性表對比：第三章棧和隊(duì)列3.1棧3.1.1棧的類型定義棧（Stack）是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱作“棧頂(top)”不允許插入和刪除的另一端稱作"棧底(bottom)"通常稱往棧頂插入元素的操
3、作為“入?！?，稱刪除棧頂元素的操作為“出棧”。棧被稱為是一種“后進(jìn)先出”的結(jié)構(gòu)，又稱LIFO（LastInFirstOut的縮寫）表。如下圖所示的鐵路調(diào)度站棧的類型定義如下：ADTStack{數(shù)據(jù)對象：D＝{ai
4、ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{
5、ai-1,ai∈D,i=2,...,n}約定an端為棧頂，a1端為棧底?；静僮鳎篒nitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。 操作結(jié)果：棧S被銷毀。ClearStack(&S)初始條
6、件：棧S已存在。 操作結(jié)果：將S清為空棧。StackEmpty(S)初始條件：棧S已存在。 操作結(jié)果：若棧S為空棧，則返回TRUE，否則返回FALSE。StackLength(S)初始條件：棧S已存在。 操作結(jié)果：返回棧S中元素個(gè)數(shù)，即棧的長度GetTop(S,&e)初始條件：棧S已存在且非空。 操作結(jié)果：用e返回S的棧頂元素。Push(&S,e)初始條件：棧S已存在。 操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&e)初始條件：棧S已存在且非空。 操作結(jié)果：刪除S的棧頂元素，并用e返回其值。StackTrav
7、erse(S,visit())初始條件：棧S已存在且非空，visit()為元素的訪問函數(shù)。 操作結(jié)果：從棧底到棧頂依次對S的每個(gè)元素調(diào)用函數(shù)visit()，一旦visit()失敗，則操作失敗。}ADTStack3.1棧3.1.2棧的存儲表示和操作的實(shí)現(xiàn)棧也有兩種存儲表示：順序存儲和鏈?zhǔn)酱鎯樞虼鎯Y(jié)構(gòu)簡稱為順序棧鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈棧"棧頂指針"意為指示棧頂元素在棧中的位置，但它的值實(shí)際是棧中元素的個(gè)數(shù)，和順序表中的length值的意義相同。一、順序棧類型的定義//結(jié)構(gòu)定義：typedefstruct{elemType*base;//存儲空間基址
8、inttop;//棧頂指針intstacksize;//允許的最大存儲空間以元素為單位}Stack;3.1棧3.1.2棧的存儲表示和操作的實(shí)現(xiàn)//基本操作接口(函數(shù)聲明)：voidInitStack(Stack&S，intmaxsize);//構(gòu)造一個(gè)最大存儲容量為maxsize的空棧S。voidDestroyStack(Stack&S);//銷毀棧S，S不再存在。voidClearStack(Stack&S);//將S置為空棧。boolStackEmpty(StackS);//若棧S為空棧，則返回TRUE，否則返回FALSEintStackLengt
9、h(StackS);//返回S的元素個(gè)數(shù)，即棧的長度。boolGetTop(StackS,ElemType&e);//若棧不空，則用e返回S的棧頂元素，并返回TRUE；//否則返回FALSE。boolPush(Stack&S,ElemTypee);//若棧的存儲空間不滿，則插入元素e為新的棧頂//元素，并返回TRUE； 否則返回FALSE。boolPop(Stack&S,ElemType&e);//若棧不空，則刪除S的棧頂元素，用e返回其值，//并返回TRUE；否則返回FALSE。voidStackTraverse(StackS,void(*visi
10、t(ElemType))//依次對S的每個(gè)元素調(diào)用函數(shù)visit()，//一旦visit()失
