數(shù)據(jù)結(jié)構(gòu)課件：03 第二章 堆棧和隊列

1、第二章 線性表、堆棧和隊列 2.1 線性表的定義和基本操作2.2 線性表的順序存儲結(jié)構(gòu)2.3 線性表的鏈接存儲結(jié)構(gòu)2.4 復(fù)雜性分析2.5 堆棧2.6 隊列2.5 堆 棧2.5.1 堆棧的定義和主要操作2.5.2 順序棧2.5.3 鏈?zhǔn)綏?.5.4 順序棧與鏈?zhǔn)綏５谋容^2.5.5 堆棧的應(yīng)用1、堆棧的定義棧的定義：是一種操作受限的線性表，只允許在表的同一端進(jìn)行插入和刪除操作，且這些操作是按后進(jìn)先出的原則進(jìn)行的。棧頂：進(jìn)行插入、刪除的一端；棧底：另一端；空棧：棧中無元素時。a5a3a2a1 a4進(jìn)棧出棧棧頂棧底例 線性表 (a1,a2,a5)，進(jìn)棧出棧情況a1 a2a1 a3a2a1 a3a2a

2、1 a4a5a3a2a1 a4a1 a2a1 a3a2a1 a3a2a1 a4a5a3a2a1 a4棧的后進(jìn)先出性：可以對輸入序列部分或全局求逆；凡符合后進(jìn)先出性，都可應(yīng)用棧，如十進(jìn)制數(shù)與其它數(shù)制的轉(zhuǎn)換、遞歸的實現(xiàn)、算數(shù)表達(dá)式求值等問題。棧的封閉性：除了棧頂元素外，其他元素不會被改變。因而，棧的封閉性非常好，使用起來非常安全。2、堆棧的基本操作（1）棧初始化（2）進(jìn)棧 Push（3）出棧 Pop（4）讀取棧頂元素 Peek（5）判?？?StackEmpty（6）判棧滿 StackFull（7）置空棧 2.5 堆 棧2.5.1 堆棧的定義和主要操作2.5.2 順序棧2.5.3 鏈?zhǔn)綏?.5.4

3、順序棧與鏈?zhǔn)綏５谋容^2.5.5 堆棧的應(yīng)用堆棧的順序存儲 使用數(shù)組存放棧元素，棧的規(guī)模必須小于或等于數(shù)組的規(guī)模，當(dāng)棧的規(guī)模等于數(shù)組的規(guī)模時，就不能再向棧中插入元素。 存放堆棧元素的數(shù)組： T stackArray MaxStackSize; 棧頂所在數(shù)組元素的下標(biāo)： int top; 堆?？眨?top = -1 堆棧滿： top = MaxStackSize-1top1230-1top1230ACBtop1230ABtop1230Atop1230-1棧內(nèi)變化情況順序棧AStack的類定義template class AStack private: int size ;/ 數(shù)組的規(guī)模 T * s

4、tackArray ; / 存放堆棧元素的數(shù)組 int top ; / 棧頂所在數(shù)組元素的下標(biāo)public: AStack ( int MaxStackSize ) / 構(gòu)造函數(shù) size = MaxStackSize ; stackArray = new T MaxStackSize ; top = -1 ; AStack ( ) delete stackArray ; / 析構(gòu)函數(shù)bool Push ( const T& item ) ; / 向棧頂壓入一個元素bool Pop ( T & item ) ; / 從棧頂彈出一個元素bool Peek ( T & item ) const ;

5、 / 存取棧頂元素int IsEmpty ( void ) const return top = = -1 ; / 檢測棧是否為空int IsFull ( void ) const return top size - 1 ; / 檢測棧是否為滿void clear ( void ) top -1 ; / 清空棧 ;算法 Push (A, item) / 向順序棧A中壓入一個元素itemP1. 棧滿？ IF topsize-1 THEN (PRINT“棧滿無法壓入”. RETURN.)P2. 入棧 toptop1. / 更新棧頂元素的下標(biāo) Atopitem. / 壓入新棧頂元素 top1230-

6、1top1230ABtop1230A堆棧變化情況top1230ACB算法 Pop (A. item) /* 從順序棧A中彈出棧頂元素，并存放在變量item中*/P1. ?？? IF top -1 THEN (PRINT“?？諢o法彈出”. RETURN.)P2. 出棧 itemAtop. / 保存棧頂元素值 toptop-1. / 更新棧頂元素的下標(biāo) top1230ACBtop1230ABtop1230-1top1230A堆棧變化情況算法 Peek (A. item) / 將順序棧A的棧頂元素存放在變量item中P1. ?？?？ IF top -1 THEN (PRINT“?？铡? RETURN.

7、)P2. 讀取棧頂元素 itemAtop. / 保存棧頂元素值與Pop的區(qū)別是什么？top top - 12.5 堆 棧2.5.1 堆棧的定義和主要操作2.5.2 順序棧2.5.3 鏈?zhǔn)綏?.5.4 順序棧與鏈?zhǔn)綏５谋容^2.5.5 堆棧的應(yīng)用2.5.3 堆棧的鏈?zhǔn)酱鎯τ脝捂湵韺崿F(xiàn)堆棧要為每個棧元素分配一個額外的指針空間?？紤]棧頂對應(yīng)鏈表的表頭還是表尾。因為堆棧主要操作（插入、刪除、存?。┑膶ο笫菞ｍ斣?，若棧頂對應(yīng)表尾，則每次操作的時間復(fù)雜性為O(n) ；若棧頂對應(yīng)表頭，則每個操作的時間復(fù)雜性是O(1)，顯然，棧頂對應(yīng)表頭是合理的。另外，鏈?zhǔn)綏Ｖ胁恍枰谖唤Y(jié)點。 鏈?zhǔn)綏Stack的類定義te

8、mplate class LStackprivate : SLNode * top ;/ 棧頂指針指向表頭public : LStack ( ) top = NULL ; / 構(gòu)造函數(shù) LStack ( ) clear ( ) ; / 析構(gòu)函數(shù)bool Push ( const T& item ) ; / 向棧頂壓入一個元素bool Pop ( T & item ) ; / 從棧頂彈出一個元素bool Peek ( T & item ) const ; / 讀取棧頂元素void clear ( ) ; / 清空棧int IsEmpty ( void ) const return top = =

9、 NULL ; / 檢測棧是否為空 ;算法 Push (item) / 向棧頂指針為top的鏈?zhǔn)綏Ｖ袎喝胍粋€元素item P1. 創(chuàng)建新結(jié)點 sAVAIL. /為新結(jié)點申請空間 data(s) item. next(s) top. /* 新結(jié)點的數(shù)據(jù)域存放item，指針域存放原棧頂結(jié)點的地址信息*/P2. 更新棧頂指針 tops. / 更新棧頂指針，令其指向新入棧結(jié)點算法 Pop ( .item) /* 從棧頂指針為top的鏈?zhǔn)綏Ｖ袕棾鰲ｍ斣?，并存放在變量item中*/P1. ?？?？ IF top= NULL THEN (PRINT“?？諢o法彈出”. RETURN.)P2. 出棧 itemd

10、ata(top). / 保存棧頂結(jié)點的字段值 qnext(top). / 令指針q指向次棧頂結(jié)點 AVAILtop. / 釋放棧頂結(jié)點的空間 topq./ 更新棧頂指針，令其指向q所指結(jié)點 算法 Peek (item) /* 將棧頂指針為top的鏈?zhǔn)綏５臈ｍ斣卮娣旁谧兞縤tem中*/P1. ?？?？ IF topNULL THEN (PRINT“棧空”. RETURN.)P2. 存取棧頂 itemdata(top). / 將棧頂結(jié)點的字段值保存在變量item中 算法 Clear ( ) / 將棧頂指針為top的鏈?zhǔn)綏Ｇ蹇誄1. 逐一出棧，直至?？誛HILE topNULL DO ( qnext

11、(top). / 保存次棧頂結(jié)點的地址信息 AVAILtop. / 釋放棧頂結(jié)點的存儲空間 topq. ) / 更新棧頂指針2.5 堆 棧2.5.1 堆棧的定義和主要操作2.5.2 順序棧2.5.3 鏈?zhǔn)綏?.5.4 順序棧與鏈?zhǔn)綏５谋容^2.5.5 堆棧的應(yīng)用順序棧與鏈?zhǔn)綏５谋容^在空間復(fù)雜性上，順序棧必須初始就申請固定的空間，當(dāng)棧不滿時，必然造成空間的浪費；鏈?zhǔn)綏Ｋ杩臻g是根據(jù)需要隨時申請的，其代價是為每個元素提供空間以存儲其next指針域。在時間復(fù)雜性上，對于針對棧頂?shù)幕静僮鳎▔喝?、彈出和棧頂元素存取），順序棧和鏈?zhǔn)綏５臅r間復(fù)雜性均為O(1) . 2.5 堆 棧2.5.1 堆棧的定義和主要

12、操作2.5.2 順序棧2.5.3 鏈?zhǔn)綏?.5.4 順序棧與鏈?zhǔn)綏５谋容^2.5.5 堆棧的應(yīng)用堆棧的應(yīng)用括號匹配 高級語言程序設(shè)計中的各種括號應(yīng)該匹配，例如：“(” 與 “)”匹配、“”與 “” 匹配、“”與 “” 匹配等。字符串a(chǎn)=(b*c+free( ) 中的括號就沒有匹配上，因為串中第一個關(guān)括號 “” 和最近的未匹配開括號 “(” 不匹配。算法思想根據(jù)匹配規(guī)則：后遇到的開括號先匹配采用棧存放開括號，當(dāng)前閉括號和棧頂開括號匹配考慮匹配失敗的情況考慮放松的匹配規(guī)則括號的匹配檢測：void main ( ) LStack bracket ; / 聲明一個鏈?zhǔn)綏ο骳har read_in =

13、cin.get() ; while (read_in != n ) if ( read_in = = | read_in = = | read_in = = ( ) /*若輸入開括號，則將其壓入棧*/bracket.push ( read_in ) ; else if ( read_in = = | read_in = = | read_in = = ) ) /* 若輸入關(guān)括號，則檢測是否匹配*/ if (bracket. IsEmpty () ) cout “Unmatched closing bracket ” read_in “is detected”endl ; return ; ch

14、ar open_bracket ; bracket.pop (open_bracket) ; if (! (open_bracket = = ( & read_in = = ) ) | ( open_bracket = = & read_in = = ) | ( open_bracket = = & read_in = = ) cout“Bad match” read_in open_bracket endl; return; read_in = cin.get() ; / 若堆棧中仍有開括號，說明匹配失敗，因為已無關(guān)括號與之匹配 if ( ! bracket. IsEmpty () ) co

15、ut “Unmatched opening bracket detected. ”endl ; return ;堆棧的應(yīng)用數(shù)制轉(zhuǎn)換例：十進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)：(66)10=(102)8 66/8=8 余 2 8/8=1 余 0 1/8=0 余 1 結(jié)果為余數(shù)的逆序:102。先求得的余數(shù)在寫出結(jié)果時最后寫出，最后求出的余數(shù)最先寫出，符合棧的后進(jìn)先出的性質(zhì)，故可用棧來實現(xiàn)數(shù)制轉(zhuǎn)換。十進(jìn)制數(shù)x轉(zhuǎn)換為r進(jìn)制數(shù)y十進(jìn)制數(shù) x 除以r，所得余數(shù)是 r 進(jìn)制數(shù) y 的最低位 y0，放入堆棧；用x除以 r 的整數(shù)商，除以 r，所得余數(shù)是 y 的次低位 y1，放入堆棧；依此類推；直到商為0，所得余數(shù)是y的最高位

16、ym，放入堆棧；此時，棧中有m+1個r進(jìn)制數(shù)，將其依次彈出，即為所得。 第二章 線性表、堆棧和隊列 2.1 線性表的定義和基本操作2.2 線性表的順序存儲結(jié)構(gòu)2.3 線性表的鏈接存儲結(jié)構(gòu)2.4 復(fù)雜性分析2.5 堆棧2.6 隊列2.6 隊 列2.6.1 隊列的定義和主要操作2.6.2 順序隊列2.6.3 鏈?zhǔn)疥犃?.6.4 順序隊列與鏈?zhǔn)疥犃械谋容^2.6.5 隊列與堆棧的擴展1、隊列的定義隊列的定義：是一個操作受限的線性表，對于它的所有插入都在表的一端進(jìn)行，所有的刪除（以至幾乎所有的存?。┒荚诒淼牧硪欢诉M(jìn)行，且這些操作又都是按著先進(jìn)先出（FIFO）的原則進(jìn)行的。 能進(jìn)行刪除的一端稱為隊頭（fr

17、ont）；能進(jìn)行插入的一端稱為隊尾（rear）；沒有元素的隊列稱為空隊列。a1a2a3a4a5隊尾隊頭入隊出隊隊列的先進(jìn)先出性：可以對輸入序列起緩沖作用；凡符合先進(jìn)先出性，都可應(yīng)用隊列，如操作系統(tǒng)中作業(yè)調(diào)度、樹的層次遍歷、圖的廣度優(yōu)先搜索等問題。隊列的封閉性：和棧類似，隊列的封閉性也非常好，使用起來非常安全。2、隊列的基本操作 (1）隊列初始化（2）入隊 (插入）（3）出隊（刪除）（4）讀取隊首元素（5）判斷隊列是否空 （6）確定隊列中元素個數(shù) （7）置空隊列 2.6 隊 列2.6.1 隊列的定義和主要操作2.6.2 順序隊列2.6.3 鏈?zhǔn)疥犃?.6.4 順序隊列與鏈?zhǔn)疥犃械谋容^2.6.5

18、隊列與堆棧的擴展隊列的順序存儲 存放隊列元素的數(shù)組： T qlistMaxQSize front 隊首元素的數(shù)組下標(biāo) rear (要入隊元素的下標(biāo)) 隊尾元素的下標(biāo)加1 a1a2a3frontrear 例 等待處理某作業(yè)進(jìn)隊、出隊情況。front=0rear=1a0012MaxQsize-1a0進(jìn)隊012MaxQsize-1front=0rear=0初始狀態(tài) 插入： rear=rear+1 front=0a0a1a2012MaxQsize-1a1 a2進(jìn)隊rear=3front=1a1a2012MaxQsize-1a0出隊rear=3 刪除隊首元素的方法1：令front=front+1fron

19、t=3012MaxQsize-1a1 a2出隊rear=3 012MaxQsize-1rear=nfront=n-3an-3an-2 無法利用的空間x 刪除隊首元素方法2 :元素向前移動，front總等于0a2012MaxQsize-1a0出隊front=0 rear=2a1front=0an-3an-2012MaxQsize-1rear=3x 012front= n-3an-3an-2MaxQsize-1rear=n-1 刪除隊首元素的方法3：循環(huán)隊列刪除時 front 順時針移動一位rear=n-1front=n-2an-2012MaxQsize-1 012front= n-3an-3an

20、-2MaxQsize-1rear=n-1 刪除隊首元素的方法3：循環(huán)隊列插入元素 x：front= n-3an-3an-2012MaxQsize-1rear=0 xrear順時針移動一位 front= n-3an-3an-2012MaxQsize-1rear=n-1 循環(huán)隊列：很好的解決了(1)(2)中存在的問題。n-3rear= n-1an-3an-20.1.front=n-3n-2插入元素 x：front=n-3an-3an-2012MaxQsize-1rear=0 xn-3an-3rear=0an-20.1n-1.front=n-3n-2xrear順時針移動一位rear = (rear+

21、1) MOD MaxQSize刪除隊首元素：front順時針移動一位front = (front+1) MOD MaxQSize;rear0front=9.1.CD刪除Crearfront=00.1.D采用環(huán)狀模型來實現(xiàn)隊列，各數(shù)據(jù)成員的意義如下： front指定隊首位置，刪除一個元素就將front順時針移動一位； rear指向元素要插入的位置，插入一個元素就將rear順時針移動一位； count存放隊列中元素的個數(shù)，當(dāng)count等于MaxQSize時，不可再向隊列中插入元素。 隊空：count=0 隊滿：count= MaxQSize順序隊列類AQueue的類聲明template class

22、 AQueueprivate: int front ;/ 隊首所在數(shù)組元素下標(biāo) int rear ; / 新元素要插入的位置（下標(biāo)） int count ; / 隊列中元素個數(shù) T *QArray ; / 存放隊列元素的數(shù)組 int Size ;/ 存放隊列的數(shù)組規(guī)模public: AQueue ( int MaxQueueSize = 10 ) / 構(gòu)造函數(shù) AQueue ( void ) delete QArray ; / 析構(gòu)函數(shù)bool QInsert ( const T& item )/ 向隊尾插入元素itembool QDelete ( T & item ) ; / 刪除隊首元素并

23、將該元素值保存至itemvoid QClear ( void ) front = rear = count = 0 ; / 清空隊列T QFront ( void ) const ; / 存取隊首元素值bool isEmpty ( void ) const return count = = 0 ; / 檢測隊列是否為空bool isFull ( void ) const return count = = Size ; / 檢測隊列是否為滿 ;算法QInsert (A, item) / 在隊列A中將元素item插入隊尾QI1. 隊列滿？IF countsize THEN (PRINT“隊列已滿無

24、法插入”. RETURN. )QI2. 元素插入 Arear item. / 將新元素插入隊尾QI3. 更新 rearMOD(rear1, size). / 更新隊尾下標(biāo) countcount1. / 更新隊列長度 算法QDelete (A. item) / 刪除隊列A的隊首元素，并將其元素值賦給變量itemQD1. 隊列空？ IF count0 THEN (PRINT “隊列空無法刪除”. RETURN. )QD2. 出隊 item Afront. / 將隊首元素保存至itemQD3. 更新 frontMOD(front1, size). / 更新隊首元素下標(biāo) countcount -1.

25、/ 更新隊列長度 算法QFront (A. item) / 讀取隊列A的隊首元素值，并將其賦給變量itemQF1. 隊列空？IF count0 THEN (PRINT “隊列空無法讀取”. RETURN. )QF2. 存取 item Afront. / 將隊首元素保存至item 0123456a0123456FR(a) 創(chuàng)建一個隊列FR(b) 插入元素 a隊列運行示意圖abc01234560123456FR(c) 插入元素b、cFR(d) 取出元素 a、b、chidefg0123456hijdefg0123456RF(e) 插入元素d、e、f、g、h、iFR(f) 插入元素 j0123456F

26、R(g) 刪除所有元素2.6 隊 列2.6.1 隊列的定義和主要操作2.6.2 順序隊列2.6.3 鏈?zhǔn)疥犃?.6.4 順序隊列與鏈?zhǔn)疥犃械谋容^2.6.5 隊列與堆棧的擴展隊列的鏈接存儲鏈?zhǔn)疥犃械慕Y(jié)構(gòu)：（a1, a2, , an) ana1a2frontrear鏈?zhǔn)疥犃蠰Queue的類聲明template class LQueue private:SLNode * front, * rear ; / 指向隊首和隊尾的指針public:LQueue ( void ) front = rear = NULL; / 構(gòu)造函數(shù) LQueue ( void ) QClear ( ) ; / 析構(gòu)函數(shù) v

27、oid QInsert ( const T& item ) ;/ 隊尾添加元素bool QDelete ( T& item ) ;/ 刪除隊首元素bool QFront ( T& item ) const ;/ 存取隊首元素值/ 檢測隊列狀態(tài)int IsEmpty ( void ) const return front = = NULL ; void QClear ( void ) ; / 清空隊列 ;算法QInsert (item) / 將元素item插入隊尾QI1. 創(chuàng)建新結(jié)點 s AVAIL. data(s)item. next(s)NULL. / 為新結(jié)點申請空間，令其字段值為item

28、，指針域為空QI2. 隊空？ IF frontNULL THEN fronts. /若隊列為空，令隊首指針指向s ELSE next(rear)s. /若隊列非空，令表尾結(jié)點的next指針指向sQI3. 更新隊尾指針 rears. / 更新表尾指針acbfronteltNULLrearrear算法QDelete (item) / 刪除隊首結(jié)點并將其字段值存于itemQD1. 隊列空？ IF frontNULL THEN (PRINT “隊列為空”. RETURN. )QD2. 出隊 qfront. itemdata(q). / 令指針q指向隊首，并保存其字段值 frontnext(front). / 令隊首指針指向原隊首結(jié)點之后繼結(jié)點 AVAILq. / 釋放原隊首結(jié)點的存儲空間QD3. 出隊后隊列空？ IF frontNUL