棧和隊列PPT學(xué)習(xí)教案

1、會計學(xué)1 棧和隊列棧和隊列 第1頁/共75頁 第2頁/共75頁 第3頁/共75頁 每次進(jìn)棧的元素都被放在原棧頂元素之上而成為每次進(jìn)棧的元素都被放在原棧頂元素之上而成為 新的棧頂，而每次出棧的總是當(dāng)前棧中新的棧頂，而每次出棧的總是當(dāng)前棧中“最新最新”的元的元 素，即最后進(jìn)棧的元素。因此，棧又稱為素，即最后進(jìn)棧的元素。因此，棧又稱為后進(jìn)先出的后進(jìn)先出的 線性表線性表。簡稱為。簡稱為LIFOLIFO表。表。 棧的示意圖 a1 a2 an棧頂（表尾） 棧底bottom top 入棧入棧 push 出棧出棧 pop 第4頁/共75頁 棧的示意圖 S 3 bottom to p S 1 S 2 S 5 S

2、 6 S 3 S 4 S 3 S 3 S 3 S 3 S 3 PUS H PUS H PUS H POPPUS H PUS H PUS H 第5頁/共75頁 棧在計算機(jī)中主要有兩種基本的存儲棧在計算機(jī)中主要有兩種基本的存儲 結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。 l 順序存儲的棧為順序棧順序存儲的棧為順序棧 l 鏈?zhǔn)酱鎯Φ臈殒湕ｆ準(zhǔn)酱鎯Φ臈殒湕?棧的存儲方式 第6頁/共75頁 第7頁/共75頁 第8頁/共75頁 top 空棧 top top toptop top a 進(jìn)棧b 進(jìn)棧 aa b a b c d e e 進(jìn)棧 a b c d e f 進(jìn)棧溢出 a b

3、 d e e 退棧 c 第9頁/共75頁 top c 退棧b 退棧 a b a a 退?？湛諚?top a b d d 退棧 c top a b c top top 第10頁/共75頁 第11頁/共75頁 第12頁/共75頁 第13頁/共75頁 第14頁/共75頁 第15頁/共75頁 第16頁/共75頁 第17頁/共75頁 第18頁/共75頁 鏈棧鏈棧是采用是采用鏈表鏈表作為存儲結(jié)構(gòu)實(shí)現(xiàn)的棧作為存儲結(jié)構(gòu)實(shí)現(xiàn)的棧，是線性，是線性 鏈表的特例鏈表的特例。因為棧的插入和刪除操作僅限制在表頭。因為棧的插入和刪除操作僅限制在表頭 位置進(jìn)行，所以鏈表的表頭指針就作為棧頂指針。位置進(jìn)行，所以鏈表的表頭指針就

4、作為棧頂指針。 toptop為棧頂指針，始終指向當(dāng)前棧頂元素結(jié)點(diǎn)為棧頂指針，始終指向當(dāng)前棧頂元素結(jié)點(diǎn) 。若。若top=NULLtop=NULL，則代表空棧。，則代表空棧。 注意：注意：鏈棧在使用完畢時，應(yīng)該釋放其空間。鏈棧在使用完畢時，應(yīng)該釋放其空間。 注意注意: 鏈棧中指針的方向是從棧頂指向棧底方向鏈棧中指針的方向是從棧頂指向棧底方向 棧頂指針棧頂指針 top a1 an-1 an 第19頁/共75頁 第20頁/共75頁 第21頁/共75頁 第22頁/共75頁 第23頁/共75頁 第24頁/共75頁 第25頁/共75頁 將將x x入棧，修改棧頂入棧，修改棧頂 指針指針:top=p:top=p

5、 a an n出棧，修改棧頂指出棧，修改棧頂指 針針:top=top-next:top=top-next 鏈棧的入棧操作和出棧操作 第26頁/共75頁 第27頁/共75頁 第28頁/共75頁 第29頁/共75頁 隊頭 f隊尾 r 出隊出隊 入隊入隊 2.1 隊列的定義和基本運(yùn)算 第30頁/共75頁 第31頁/共75頁 隊列的進(jìn)隊和出隊 front rear空隊列front rearA進(jìn)隊 A front rearB進(jìn)隊 A B front rearC, D進(jìn)隊 A B C D front rearA退隊 B C D front rearB退隊 C D front rearE,F,G進(jìn)進(jìn)隊 C

6、D E F GC D E F G front rearH進(jìn)進(jìn)隊,溢出 第32頁/共75頁 隊列的進(jìn)隊和出隊原則 n 進(jìn)隊時隊尾指針先進(jìn)一進(jìn)隊時隊尾指針先進(jìn)一 rear = rear + 1， 再將新元素按再將新元素按 rear 指示位置加入。指示位置加入。 n 出隊時隊頭指針先進(jìn)一出隊時隊頭指針先進(jìn)一 front = front + 1， 再將下標(biāo)為再將下標(biāo)為 front 的元素取出的元素取出。 n 隊滿時再進(jìn)隊將隊滿時再進(jìn)隊將溢出出錯溢出出錯； n 隊空時再出隊將隊空時再出隊將隊空處理隊空處理。 n 解決辦法之一：將隊列元素存放數(shù)組首尾解決辦法之一：將隊列元素存放數(shù)組首尾 相接，形成相接，形

7、成循環(huán)循環(huán)(環(huán)形環(huán)形)隊列隊列。 第33頁/共75頁 隊列在計算機(jī)中主要有兩種基本的存儲結(jié) 構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。 l順序存儲的隊列為順序隊列 l鏈?zhǔn)酱鎯Φ年犃袨殒滉犃?隊列的存儲方式 第34頁/共75頁 第35頁/共75頁 frontrear a b c a b c d d d e d e f f rear front rear 第36頁/共75頁 第37頁/共75頁 第38頁/共75頁 當(dāng)Q-front= Q-rear 時,隊列空。 當(dāng)Q-rear+1MaxSize 時,隊列滿(即上溢出),但此 時頭指針指示的元素之前可能還有空單元,此現(xiàn)象稱為 假溢出;若把這樣的順序結(jié)構(gòu)設(shè)想為一

8、個循環(huán)表, 插入 時就可以利用這些空單元, 這樣就構(gòu)成循環(huán)隊列。 假上溢 第39頁/共75頁 第40頁/共75頁 0 1 2 3 4 5 ENQUEUE1 ENQUEUE 2 ENQUEUE3 DEQUEUE1 ENQUEUE 4 DEQUEUE2 ENQUEUE5 ENQUEUE 6 ENQUEUE7 ENQUEUE8 q 1 q 2 q 3 q 4 q 5 q 6 q 7 q 8 循環(huán)隊列 （circular queue） 滿滿 空空 ? F R F R F R R R R R R R 第41頁/共75頁 入隊操作時的尾指針運(yùn)算入隊操作時的尾指針運(yùn)算: rear=(rear+1)%Maxs

9、ize 出隊操作時的頭指針運(yùn)算出隊操作時的頭指針運(yùn)算: front=(front+1)%Maxaize 問題：問題：在循環(huán)隊列中，由于隊空時有在循環(huán)隊列中，由于隊空時有front=rear；隊滿時也有隊滿時也有front=rear；因因 此我們無法通過此我們無法通過front=rear來判斷隊列是來判斷隊列是“空空”還是還是“滿滿”。 循環(huán)隊列示意圖 循環(huán)隊列的幾種狀態(tài)循環(huán)隊列的幾種狀態(tài) 第42頁/共75頁 frontrea r 循環(huán)隊列循環(huán)隊列隊滿和隊空隊滿和隊空的描述方法的描述方法 frontrear 隊空隊空: 隊滿隊滿: front frontrearrear rear=front（?

10、） rear=front 第43頁/共75頁 第44頁/共75頁 第45頁/共75頁 第46頁/共75頁 第47頁/共75頁 第48頁/共75頁 第49頁/共75頁 第50頁/共75頁 第51頁/共75頁 第52頁/共75頁 第53頁/共75頁 隊頭在鏈頭，隊尾在鏈尾。隊頭在鏈頭，隊尾在鏈尾。 a1an q.front q.rear q.front q.rear 空隊列空隊列 第54頁/共75頁 鏈隊列的幾種狀態(tài)示意圖 此時，front=rear 修改rear指針 修改頭結(jié)點(diǎn)的指針域 鏈隊列為空的特征：鏈隊列為空的特征：front=rearfront=rear 鏈隊列會滿嗎鏈隊列會滿嗎 ？ 一

11、般不會，因為刪除時有一般不會，因為刪除時有freefree動作，除非內(nèi)存不足動作，除非內(nèi)存不足 ！ 修改rear指針 第55頁/共75頁 和鏈棧類似，無須考慮判隊滿的運(yùn)算及上溢 。 在出隊算法中，一般只需修改隊頭指針。 但當(dāng)原隊中只有一個結(jié)點(diǎn)時，該結(jié)點(diǎn)既是隊 頭也是隊尾，故刪去此結(jié)點(diǎn)時亦需修改尾指 針，且刪去此結(jié)點(diǎn)后隊列變空。 以上討論的是無頭結(jié)點(diǎn)鏈隊列的基本運(yùn)算 。和單鏈表類似，為了簡化邊界條件的處理 ，在隊頭結(jié)點(diǎn)前也可附加一個頭結(jié)點(diǎn)，增加 頭結(jié)點(diǎn)的鏈隊列的基本運(yùn)算 第56頁/共75頁 第57頁/共75頁 第58頁/共75頁 int InitQueue( LinkQueue int Init

12、Queue( LinkQueue * *Q )Q ) /構(gòu)造一個空隊列構(gòu)造一個空隊列 * *Q Q Q-front = (LQnode Q-front = (LQnode * *)malloc(sizeof(LQnode); )malloc(sizeof(LQnode); if( Q-front = NULL ) if( Q-front = NULL ) return FALSE; return FALSE; /申請內(nèi)存失敗返回申請內(nèi)存失敗返回 Q-rear = Q-front;Q-rear = Q-front; Q-front Q-front- next = NULL;next = NULL

13、; return TRUE; return TRUE; /申請內(nèi)存成功返回申請內(nèi)存成功返回 第59頁/共75頁 第60頁/共75頁 第61頁/共75頁 第62頁/共75頁 第63頁/共75頁 第64頁/共75頁 數(shù)據(jù)結(jié)構(gòu)-第3章 棧和隊列66 第65頁/共75頁 數(shù)據(jù)結(jié)構(gòu)-第3章 棧和隊列67 int Factorial(int n) if (n=0) return(1); return n*Factorial(n-1); /Factorial 第66頁/共75頁 數(shù)據(jù)結(jié)構(gòu)-第3章 棧和隊列68 12 3 s 1 2 3 - 利用棧，棧中每個元素稱為工作記錄，分成三個部分： 返回地址 實(shí)際參數(shù)

14、表(變參和值參) 局部變量 - 發(fā)生調(diào)用時，保護(hù)現(xiàn)場，即當(dāng)前的工作記錄入棧，然后 轉(zhuǎn)入被調(diào)用的過程 - 一個調(diào)用結(jié)束時，恢復(fù)現(xiàn)場，即若棧不空，則退棧，從 退出的返回地址處繼續(xù)執(zhí)行下去 第67頁/共75頁 69 L0 3 / / L3 3 / L3 2 / L3 1 / 1 1 2 6 第68頁/共75頁 數(shù)據(jù)結(jié)構(gòu)-第3章 棧和隊列70 第69頁/共75頁 數(shù)據(jù)結(jié)構(gòu)-第3章 棧和隊列71 第70頁/共75頁 數(shù)據(jù)結(jié)構(gòu)-第3章 棧和隊列72 使用跳轉(zhuǎn)語句： void linklist_output1(LNode *p) 1: if ( p ) printf(p-data); p=p-next; goto 1 /linklist_output1 使用循環(huán)語句： void linklist_output2(LNode *p) while ( p ) printf(p-data); p=p-next; /linklist_output2 p ana 2a 1 第71頁/共75頁 數(shù)據(jù)結(jié)構(gòu)-