1、 2022年5月2日 2022年5月2日 3.1 棧棧3.2 棧棧的應用的應用3.3 棧與遞歸棧與遞歸3.4 隊列隊列3.5 隊列的應用隊列的應用教學內容教學內容 2022年5月2日 第第3 3章章棧和隊列棧和隊列1.1.掌握棧和隊列的掌握棧和隊列的特點特點，并能在相應的應用問，并能在相應的應用問題中正確選用題中正確選用2.2.熟練掌握棧的熟練掌握棧的兩種存儲結構兩種存儲結構的基本操作實現的基本操作實現算法，特別應注意算法，特別應注意棧滿和棧空棧滿和棧空的條件的條件3.3.熟練掌握熟練掌握循環隊列和鏈隊列循環隊列和鏈隊列的基本操作實現的基本操作實現算法，特別注意算法，特別注意隊滿和隊空隊滿和隊

2、空的的條件條件4.4.理解理解遞歸算法遞歸算法執行過程中棧的狀態變化過程執行過程中棧的狀態變化過程 教學目標教學目標 2022年5月2日 棧（棧（Stack）1. 1. 定義定義2. 2. 邏輯結構邏輯結構3. 3. 存儲結構存儲結構4. 4. 運算規則運算規則5. 5. 實現方式實現方式隊列（隊列（Queue）1. 1. 定義定義2. 2. 邏輯結構邏輯結構3. 3. 存儲結構存儲結構4. 4. 運算規則運算規則5. 5. 實現方式實現方式 2022年5月2日 3.1 3.1 棧棧1. 1. 定義定義用用順序棧順序棧或或鏈棧鏈棧存儲均可，但以順存儲均可，但以順序棧更常見序棧更常見3. 3.

3、存儲結構存儲結構與線性表相同，仍為與線性表相同，仍為一對一一對一關系關系2. 2. 邏輯結構邏輯結構只能在只能在表的一端表的一端（棧頂棧頂）進行插入）進行插入和刪除運算的和刪除運算的線性表線性表 2022年5月2日 只能在只能在棧頂棧頂運算，且訪問結點時依運算，且訪問結點時依照照后進先出后進先出（LIFOLIFO）或或先進后出先進后出（FILOFILO）的原則的原則4.4.運算規則運算規則關鍵是編寫關鍵是編寫入棧入棧和和出棧出棧函數，具函數，具體實現依順序棧或鏈棧的不同而體實現依順序棧或鏈棧的不同而不同不同基本操作有基本操作有入棧、出棧、讀棧頂入棧、出棧、讀棧頂元素值、建棧、判斷棧滿、棧空元素

4、值、建棧、判斷棧滿、棧空等等5.5.實現方式實現方式 2022年5月2日 棧是一種特殊的線性表，它只能在表的一端（棧頂）棧是一種特殊的線性表，它只能在表的一端（棧頂）進行插入和刪除運算進行插入和刪除運算棧與一般線性表的區別：僅在于棧與一般線性表的區別：僅在于運算規則運算規則不同不同“進進” 壓入壓入=PUSH=PUSH（) )“出出” 彈出彈出=POP( )=POP( )一般線性表一般線性表 邏輯結構：一對一邏輯結構：一對一 存儲結構：順序表、鏈表存儲結構：順序表、鏈表 運算規則：隨機運算規則：隨機、順序存取順序存取棧棧邏輯結構：一對一邏輯結構：一對一 存儲結構：順序存儲結構：順序棧棧、鏈、鏈

5、棧棧運算規則：運算規則：后進先出后進先出棧與一般線性表的區別棧與一般線性表的區別 2022年5月2日 “進進” 壓入壓入=PUSH=PUSH（) )“出出” 彈出彈出=POP( )=POP( ) 2022年5月2日 a a1 1 a a2 2 a an n順序棧順序棧S S a ai i表頭表頭表尾表尾棧底棧底basebase棧頂棧頂toptop低地址低地址高地址高地址寫入：寫入：vivi= = a ai i讀出：讀出： x= x= vivi 壓入：壓入：PUSH (PUSH (a an+1n+1) )彈出：彈出： POP (x)POP (x)前提：一定要預設棧頂指針前提：一定要預設棧頂指針t

6、optop！低地址低地址高地址高地址vivi a a1 1 a a2 2 a ai i a an n 順序表順序表VnVn a an+1n+1順序棧與順序表順序棧與順序表 2022年5月2日 順序棧的表示順序棧的表示空棧空棧base = topbase = top 是是棧空標志棧空標志stacksizestacksize = 4 = 4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top top 指示真正的指示真正的棧頂元素之上棧頂元素之上的下標地址的下標地址棧滿時的處理方法：棧滿時的處理方法：1 1、報錯報錯, ,返回操作系統。返回操作系統

7、。2 2、分配更大的空間分配更大的空間，作為棧的存儲空，作為棧的存儲空間間, ,將原棧的內容移入新棧。將原棧的內容移入新棧。 2022年5月2日 #define MAXSIZE 100typedef structSElemType *base;SElemType *top;int stacksize;SqStack;順序棧的表示順序棧的表示 2022年5月2日 構造一個空棧構造一個空棧 步驟：步驟：(1)(1)分配空間并檢查空間分配空間并檢查空間是否分配失敗，若失敗是否分配失敗，若失敗則返回錯誤則返回錯誤順序棧初始化順序棧初始化basestacksizetops(2)(2)設置棧底和棧頂指針設

8、置棧底和棧頂指針 S.top = S.base;(3)(3)設置棧大小設置棧大小 2022年5月2日 Status InitStack( SqStack &S )S.base =new SElemTypeMAXSIZE；if( !S.base ) return OVERFLOW;S.top = S.base;S.stackSize = MAXSIZE;return OK;順序棧初始化順序棧初始化 2022年5月2日 判斷順序棧是否為空判斷順序棧是否為空bool StackEmpty( SqStack S )if(S.top = S.base) return true; else return

9、false;basetop3120 2022年5月2日 求順序棧的長度求順序棧的長度int StackLength( SqStack S )return S.top S.base;basetopAB 2022年5月2日 Status ClearStack( SqStack S )if( S.base ) S.top = S.base;return OK;清空順序棧清空順序棧basetop3120 2022年5月2日 Status DestroyStack( SqStack &S )if( S.base )delete S.base ;S.stacksize = 0;S.base = S.top

10、 = NULL; return OK;銷毀順序棧銷毀順序棧 2022年5月2日 (1)(1)判斷是否棧滿，若滿則出錯判斷是否棧滿，若滿則出錯(2)(2)元素元素e e壓入棧頂壓入棧頂(3)(3)棧頂指針加棧頂指針加1 1順序棧進棧順序棧進棧Status Push( SqStack &S, SElemType e) if( S.top - S.base= S.stacksize ) / 棧滿棧滿 return ERROR; *S.top+=e;return OK;*S.top=e;S.top+;ABCtopbase 2022年5月2日 (1)(1)判斷是否棧空，若空則出錯判斷是否棧空，若空則出錯

11、(2)(2)獲取棧頂元素獲取棧頂元素e e(3)(3)棧頂指針減棧頂指針減1 1順序棧出棧順序棧出棧Status Pop( SqStack &S, SElemType &e) if( S.top = S.base ) / 棧空棧空 return ERROR; e *-S.top;return OK;-S.top;e=*S.top;ABCtopbase 2022年5月2日 (1)(1)判斷是否空棧，若空則返回錯誤判斷是否空棧，若空則返回錯誤(2)(2)否則通過棧頂指針獲取棧頂元素否則通過棧頂指針獲取棧頂元素取順序棧棧頂元素取順序棧棧頂元素Status GetTop( SqStack S, SEl

12、emType &e) if( S.top = S.base ) return ERROR; / 棧空棧空e = *( S.top 1 );return OK;e = *( S.top - ); ?ABCtopbase 2022年5月2日 435612435612中到了中到了1212順序不能實現；順序不能實現；135426135426可以實現。可以實現。1.1.如果一個棧的輸入序列為如果一個棧的輸入序列為123456123456，能否得到，能否得到435612435612和和135426135426的出棧序列？的出棧序列？練習練習 2022年5月2日 練習練習i n-in-i+1不確定不確定2.

13、2.若已知一個棧的入棧序列是若已知一個棧的入棧序列是1 1，2 2，3 3，n n，其輸出序列為，其輸出序列為p1p1，p2p2，p3p3，pnpn，若，若p1=np1=n，則，則pipi為為 2022年5月2日 練習練習 top不變不變 top=0 top+ top-D3.3.在一個具有在一個具有n n個單元的順序棧中，假設以地址個單元的順序棧中，假設以地址高端作為棧底，以高端作為棧底，以toptop作為棧頂指針，則當作進作為棧頂指針，則當作進棧處理時，棧處理時，toptop的變化為的變化為 2022年5月2日 考研試題考研試題b0 t0 t1 b10 m-1V雙棧共享一個棧空間雙棧共享一個

14、棧空間優點：互相調劑，靈活性強，減少溢出機會優點：互相調劑，靈活性強，減少溢出機會 2022年5月2日 將編號為將編號為0 0和和1 1的兩個棧存放于一個數組空間的兩個棧存放于一個數組空間VmVm 中，棧底分別處于數組的兩端。當第中，棧底分別處于數組的兩端。當第0 0號棧號棧的棧頂指針的棧頂指針top0top0等于等于-1-1時該棧為空，當第時該棧為空，當第1 1號號棧的棧頂指針棧的棧頂指針top1top1等于等于m m時該棧為空。兩個棧時該棧為空。兩個棧均從兩端向中間增長（如下圖所示）均從兩端向中間增長（如下圖所示） 。考研試題考研試題bot0 top0 top1 bot10 m-1V 20

15、22年5月2日 typedef structint top2, bot2; /棧頂和棧底指針棧頂和棧底指針SElemTypeSElemType * *V; V; /棧數組棧數組 intint m; m; /棧最大可容納元素個數棧最大可容納元素個數 DblStackDblStack; ;數據結構定義如下數據結構定義如下考研試題考研試題 2022年5月2日 void Dblpush(DblStack &s,SElemType x,int i) ；/把把x插入到棧插入到棧i的棧的棧int Dblpop(DblStack &s,int i,SElemType &x) ； /退掉位于棧退掉位于棧i棧頂的

16、元素棧頂的元素int IsEmpty(DblStack s,int i) ；/判棧判棧i空否空否, 空返回空返回1, 否則返回否則返回0int IsFull(DblStack s) ；/判棧滿否判棧滿否, 滿返回滿返回1, 否則返回否則返回0試編寫判斷棧空、棧滿、進棧和出棧四試編寫判斷棧空、棧滿、進棧和出棧四個算法的函數個算法的函數(函數定義方式如下）函數定義方式如下）考研試題考研試題 2022年5月2日 b0 t0 t1 b10 m-1V棧空：棧空：topitopi = = botiboti i i表示棧的編號表示棧的編號 棧滿：棧滿：top0+1=top1 top0+1=top1 或或to

17、p1-1=top0top1-1=top0提示提示 2022年5月2日 鏈棧的表示鏈棧的表示運算是受限的單鏈表，只能在鏈表頭部進行操作，故運算是受限的單鏈表，只能在鏈表頭部進行操作，故沒有必要附加頭結點。棧頂指針就是鏈表的頭指針沒有必要附加頭結點。棧頂指針就是鏈表的頭指針 typedef struct StackNode SElemType data; struct StackNode *next; StackNode, *LinkStack;LinkStack S; data next 棧頂棧頂棧底棧底S 2022年5月2日 鏈棧的初始化鏈棧的初始化void InitStack(LinkSta

18、ck &S )S=NULL;S 2022年5月2日 判斷鏈棧是否為空判斷鏈棧是否為空Status StackEmpty(LinkStack S) if (S=NULL) return TRUE; else return FALSE; 2022年5月2日 鏈棧進棧鏈棧進棧Status Push(LinkStack &S , SElemType e) p=new StackNode; /生成新結點生成新結點p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; pS 2022年5月2日 鏈棧進棧鏈棧進棧pSeStatus Push

19、(LinkStack &S , SElemType e) p=new StackNode; /生成新結點生成新結點p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 2022年5月2日 鏈棧進棧鏈棧進棧pSeStatus Push(LinkStack &S , SElemType e) p=new StackNode; /生成新結點生成新結點p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 2022年5月2日 鏈棧進棧鏈棧進棧pSeSStatus P

20、ush(LinkStack &S , SElemType e) p=new StackNode; /生成新結點生成新結點p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; 2022年5月2日 鏈棧出棧鏈棧出棧SAe = AStatus Pop (LinkStack &S,SElemType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 2022年5月2日 鏈棧出棧鏈棧出棧SAe = ApStatus Po

21、p (LinkStack &S,SElemType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 2022年5月2日 鏈棧出棧鏈棧出棧SAe = ApSStatus Pop (LinkStack &S,SElemType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; 2022年5月2日 鏈棧出棧鏈棧出棧Status Pop (LinkStack &S,SEl

22、emType &e)if (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; e = AS 2022年5月2日 取鏈棧棧頂元素取鏈棧棧頂元素SElemType GetTop(LinkStack S) if (S=NULL) exit(1)； else return Sdata; 2022年5月2日 3.2 3.2 棧的應用棧的應用例例1 1：數制轉換（十轉：數制轉換（十轉N N）用棧暫存低位值用棧暫存低位值例例2 2：括號匹配的檢驗括號匹配的檢驗用棧暫存左括號用棧暫存左括號例例3 3：表達式求

23、值表達式求值用棧暫存運算符用棧暫存運算符例例4 4：迷宮求解：迷宮求解 用棧實現遞歸調用用棧實現遞歸調用簡化了程序設計的問題簡化了程序設計的問題 2022年5月2日 迷宮求解迷宮求解 2022年5月2日 從入口出發，按某一方向向未走過的前方探索從入口出發，按某一方向向未走過的前方探索若能走通，則到達新點，否則試探下一方向若能走通，則到達新點，否則試探下一方向 ; ; 若所有的方向均沒有通路，則沿原路返回前一點，若所有的方向均沒有通路，則沿原路返回前一點，換下一個方向再繼續試探換下一個方向再繼續試探直到所有可能的通路都探索到，或找到一條通路，直到所有可能的通路都探索到，或找到一條通路，或無路可走

24、又返回到入口點。或無路可走又返回到入口點。求解思想：求解思想：回溯法回溯法迷宮求解迷宮求解 2022年5月2日 需要解決的問題：需要解決的問題：1、表示迷宮的數據結構、表示迷宮的數據結構2、試探方向、試探方向3、棧的設計、棧的設計4、防止重復到達某點，避免發生死循環、防止重復到達某點，避免發生死循環迷宮求解迷宮求解 2022年5月2日 1、表示迷宮的數據結構、表示迷宮的數據結構表示一個表示一個m行行n列迷宮：列迷宮：用用mazemn表示，表示，0im,0jx=xx表表3.13.1算符間的優先關系算符間的優先關系 2022年5月2日 【算法思想算法思想】（1）初始化）初始化OPTR棧和棧和OPN

25、D棧，將棧，將 “#”壓入壓入OPTR（2）依次讀入字符）依次讀入字符ch，循環執行（，循環執行（3）至（）至（5） （3）取出）取出OPTR的棧頂元素，當的棧頂元素，當OPTR的棧頂元素和的棧頂元素和ch均為均為“#”時，表達式求值完畢，時，表達式求值完畢，OPND棧頂元素為表達式的值棧頂元素為表達式的值設定兩棧設定兩棧 ：OPND-OPND-操作數或運算結果操作數或運算結果OPTR-OPTR-運算符運算符（4） if (ch是操作數是操作數) 則則ch進進OPND，讀入下一字符，讀入下一字符ch（5） else 比較比較OPTR棧頂元素和棧頂元素和ch的優先級的優先級case : 運算符運

26、算符ch 進進OPTR，讀入下一字符，讀入下一字符chcase=: 脫括號（彈出左括號），讀入下一字符脫括號（彈出左括號），讀入下一字符chcase : 棧頂運算符退棧、計算，結果進棧頂運算符退棧、計算，結果進OPND 2022年5月2日 OperandType EvaluateExpression( ) InitStack (OPND); ch = getchar( ); while (ch!= # | GetTop(OPTR)! = #) if (! In(ch,OP)Push(OPND,ch); ch = getchar(); / ch不是運算符則進棧不是運算符則進棧 else swit

27、ch (Precede(GetTop(OPTR),ch) /比較優先權比較優先權 case : /彈出彈出OPTR棧頂的運算符運算，并將運算結果入棧棧頂的運算符運算，并將運算結果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; case = : /脫括號并接收下一字符脫括號并接收下一字符 Pop(OPTR,x); ch = getchar(); break; / switch / while return GetTop(OPND); / EvaluateExpress

28、ion 2022年5月2日 OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd) 2022年5月2日 3.3 3.3 棧與遞歸棧與遞歸n遞歸的定義遞歸的定義 若一個對象部分地包含它若

29、一個對象部分地包含它自己自己, , 或用它自己給自己定義或用它自己給自己定義, , 則稱這個對則稱這個對象是遞歸的；若一個過程象是遞歸的；若一個過程直接地或間接地調用直接地或間接地調用自己自己, , 則稱這個過程是遞歸的過程。則稱這個過程是遞歸的過程。 2022年5月2日 當多個函數構成嵌套調用時當多個函數構成嵌套調用時, , 遵循遵循后調用先返回后調用先返回棧棧 2022年5月2日 n以下三種情況常常用到遞歸方法以下三種情況常常用到遞歸方法遞歸定義的數學函數遞歸定義的數學函數具有遞歸特性的數據結構具有遞歸特性的數據結構可遞歸求解的問題可遞歸求解的問題 2022年5月2日 1. 遞歸定義的數學

30、函數遞歸定義的數學函數: 階乘函數階乘函數: 0n ) 1(0n 1)(若若nFactnnFact 2階階Fibonaci數列數列: )2() 1(1n 10n 0)(其它若若nFibnFibnFib 2022年5月2日 樹樹 2. 2. 具有遞歸特性的數據結構具有遞歸特性的數據結構: :RootRootLchildLchildRchildRchild 廣義表廣義表 A=(A=(a,Aa,A) )3. 3. 可遞歸求解的問題可遞歸求解的問題: : 迷宮問題迷宮問題HanoiHanoi塔問題塔問題 2022年5月2日 分治法：分治法：對于一個較為復雜的問題，能夠分解成幾對于一個較為復雜的問題，能

31、夠分解成幾個相對簡單的且解法相同或類似的子問題來求解個相對簡單的且解法相同或類似的子問題來求解1 1、能將一個問題轉變成一個新問題，而新問題與、能將一個問題轉變成一個新問題，而新問題與原問題的解法相同或類同，不同的僅是處理的對象，原問題的解法相同或類同，不同的僅是處理的對象，且這些處理對象是變化有規律的且這些處理對象是變化有規律的2 2、可以通過上述轉化而使問題簡化、可以通過上述轉化而使問題簡化3 3、必須有一個明確的遞歸出口，或稱遞歸的邊界、必須有一個明確的遞歸出口，或稱遞歸的邊界用分治法求解遞歸問題用分治法求解遞歸問題必備的三個條件必備的三個條件 2022年5月2日 分治法求解遞歸問題算法

32、的一般形式：分治法求解遞歸問題算法的一般形式： void p (參數表參數表) if （遞歸結束條件）可直接求解步驟；（遞歸結束條件）可直接求解步驟；-基本項基本項 else p（較小的參數）；（較小的參數）；-歸納項歸納項 long Fact ( long n ) if ( n = 0) return 1;/基本項基本項 else return n * Fact (n-1); /歸納項歸納項 2022年5月2日 返回返回 2參數參數 2 計算計算 2*Fact(1)返回返回 1參數參數 1 計算計算 1*Fact(0)返回返回 1參數參數 0 直接定值直接定值 = 1if ( n = 0 )

33、 return 1;else return n * Fact (n-1); 求解階乘求解階乘 n! n! 的過程的過程 main : Fact(4)返回返回 24 參數參數 4 計算計算 4*Fact(3)返回返回 6參數參數 3 計算計算 3*Fact(2) 2022年5月2日 設有一個遞歸算法如下設有一個遞歸算法如下:int X(int n) if(n=3) return 1; else return X(n-2)+X(n-4)+1則計算則計算X(X(8)時需要計算時需要計算X函數函數 次次.D練習練習A. 8 B.9 C.16 D.18 2022年5月2日 2022年5月2日 規則規則:

34、 :(1) (1) 每次只能移動一個圓盤每次只能移動一個圓盤(2) (2) 圓盤可以插在圓盤可以插在A,BA,B和和C C中的任一塔座上中的任一塔座上(3) (3) 任何時刻不可將較大任何時刻不可將較大圓盤壓在較小圓盤之上圓盤壓在較小圓盤之上Hanoi塔問題塔問題ABC 2022年5月2日 Hanoi塔問題塔問題 n = 1n = 1，則直接從，則直接從 A A 移到移到 C C。否則。否則 (1)用用 C 柱做過渡，將柱做過渡，將 A 的的(n-1)個移到個移到 B(2)將將 A 最后一個直接最后一個直接移到移到 C (3)用用 A 做過渡，將做過渡，將 B 的的 (n-1) 個移到個移到

35、C 2022年5月2日 #includeint c=0;void move(char x,int n,char z)cout+c,n,x,zc 2022年5月2日 調用前調用前, , 系統完成系統完成: :(1)(1)將將實參實參, ,返回地址返回地址等傳遞給被調用函數等傳遞給被調用函數(2)(2)為被調用函數的為被調用函數的局部變量局部變量分配存儲區分配存儲區(3)(3)將控制轉移到被調用函數的將控制轉移到被調用函數的入口入口調用后調用后, , 系統完成系統完成: :(1)(1)保存被調用函數的計算保存被調用函數的計算結果結果(2)(2)釋放被調用函數的釋放被調用函數的數據區數據區(3)(3

36、)依照被調用函數保存的依照被調用函數保存的返回地址返回地址將控制轉移到將控制轉移到調用函數調用函數 2022年5月2日 “層次層次”主函數主函數第第1 1次調用次調用第第 i i 次調用次調用0 0層層1 1層層i i 層層“遞歸工作棧遞歸工作棧”“工作記錄工作記錄”實在參數實在參數, ,局部變量局部變量, ,返回地址返回地址遞歸函數調用的實現遞歸函數調用的實現 2022年5月2日 程序的具體執行過程參見：程序的具體執行過程參見：“HanoiHanoi塔執行過程塔執行過程. .pptppt” 2022年5月2日 空間效率空間效率時間效率時間效率O(2n)與遞歸樹的結點數成正比與遞歸樹的結點數成

37、正比與遞歸樹的深度成正比與遞歸樹的深度成正比O(n)遞歸算法的效率分析遞歸算法的效率分析 2022年5月2日 1 2 3 4f(1)=1 f(1)+1+f(1)=3 f(2)+1+f(2)=7 f(3)+1+f(3)=15f(n) = 2f(n-1)+1f(n-1) = 2f(n-2)+1f(n-2) = 2f(n-3)+1.f(3) = 2f(2)+1f(2) = 2f(1)+120f(n) = 21f(n-1)+2021f(n-1) = 22f(n-2)+2122f(n-2) = 23f(n-3)+22.2n-3f(3) = 2n-2f(2)+ 2n-32n-2f(2) = 2n-1f(1

38、)+ 2n-2f(n) = 20+21+2n-2+ 2n-1f(1) = 2n-1遞歸算法的效率分析遞歸算法的效率分析 2022年5月2日 6464片金片移動次數：片金片移動次數：假如每秒鐘一次，共需多長時間呢？假如每秒鐘一次，共需多長時間呢？一年大約有一年大約有31536926秒，移完這些金片需要秒，移完這些金片需要多億年多億年世界、梵塔、廟宇和眾生都已經灰飛煙滅世界、梵塔、廟宇和眾生都已經灰飛煙滅 ! 2022年5月2日 優點：結構清晰，程序易讀優點：結構清晰，程序易讀缺點：每次調用要生成工作記錄，保存狀缺點：每次調用要生成工作記錄，保存狀態信息，入棧；返回時要出棧，恢復狀態信息，入棧；返

39、回時要出棧，恢復狀態信息。時間開銷大。態信息。時間開銷大。遞歸的優缺點遞歸的優缺點遞歸遞歸非遞歸非遞歸 2022年5月2日 3.4 3.4 隊列隊列隊列是一種先進先出隊列是一種先進先出(FIFO) 的線性表的線性表. 它只允許在它只允許在表的一端進行插入表的一端進行插入,而在另一端刪除元素而在另一端刪除元素),(21naaaqa a1 1a a2 2a a3 3a an n.入隊列入隊列隊頭隊頭隊尾隊尾 2022年5月2日 ),(21naaaqa a1 1a a2 2a a3 3a an n.隊頭隊頭隊尾隊尾出隊列出隊列 2022年5月2日 ),(21naaaqa a1 1a a2 2a a3

40、 3a an n.隊頭隊頭隊尾隊尾出隊列出隊列 2022年5月2日 ),(21naaaqa a1 1a a2 2a a3 3a an n.隊頭隊頭隊尾隊尾出隊列出隊列 2022年5月2日 設棧設棧S S和隊列和隊列Q Q的初始狀態為空，元素的初始狀態為空，元素e1e1、e2e2、e3e3、e4e4、e5e5和和e6e6依次通過依次通過S S，一個元素出棧后即，一個元素出棧后即進入進入Q Q，若，若6 6個元素出隊的序列是個元素出隊的序列是e2e2、e4e4、e3e3、e6e6、e5e5和和e1e1，則棧，則棧S S的容量至少應該是（）。的容量至少應該是（）。 （A）2 （B）3 （C）4 （D

41、）6練習練習B 2022年5月2日 0n , 2 , 1,|niElemSetaaDii數據對象數據對象:數據關系數據關系:端為隊列尾端為隊列頭約定n1111a ,a , 2 , 1,| ,niDaaaaRiiii基本操作基本操作: (1) InitQueue (&Q) /構造空隊列構造空隊列 (2) DestroyQueue (&Q) /銷毀隊列銷毀隊列 (3) ClearQueue (&S) /清空隊列清空隊列 (4) QueueEmpty(S) /判空判空. 空空-TRUE,ADT Queue 隊列的抽象數據類型隊列的抽象數據類型 2022年5月2日 (5) QueueLength(Q)

42、 /取隊列長度取隊列長度 (6) GetHead (Q,&e) /取隊頭元素取隊頭元素, (7) EnQueue (&Q,e) /入隊列入隊列 (8) DeQueue (&Q,&e) /出隊列出隊列 (9) QueueTraverse(Q,visit() /遍歷遍歷ADT Queue隊列的抽象數據類型隊列的抽象數據類型 2022年5月2日 #define M 100 /最大隊列長度最大隊列長度Typedef struct QElemType *base; /初始化的動態分配存儲空間初始化的動態分配存儲空間 int front; /頭指針頭指針 int rear; /尾指針尾指針SqQueue;

43、 隊列的順序表示用一維數組隊列的順序表示用一維數組baseM 2022年5月2日 隊列的順序表示用一維數組隊列的順序表示用一維數組baseMQ.frontQ.front0 01 12 23 34 45 5Q.rearQ.rearQ.frontQ.frontQ.rearQ.rearJ J1 1J J2 2J J3 3Q.frontQ.frontQ.rearQ.rearJ J3 3Q.frontQ.frontQ.rearQ.rearJ J5 5J J6 6front=rear=0空隊標志：空隊標志：front= =rear入隊：入隊：baserear+=x;出隊：出隊：x=basefront+;

44、2022年5月2日 Q.frontQ.frontQ.rearQ.rearJ5J5J6J6Q.frontQ.front0 01 12 23 34 45 5Q.rearQ.rearJ5J5J6J6J1J1J2J2J3J3J4J4存在的問題存在的問題設數組大小為設數組大小為Mfront=0rear=M時時再入隊再入隊真溢出真溢出front 0rear=M時時再入隊再入隊假溢出假溢出 2022年5月2日 解決的方法循環隊列解決的方法循環隊列1 10 0Q.rearQ.rearQ.frontQ.front.base0接在接在baseM-1之之后后若若rear+1=M則令則令rear=0;實現：利用實現：

45、利用“模模”運算運算入隊：入隊： baserear=x; rear=(rear+1)%M;出隊：出隊： x=basefront; front=(front+1)%M; 2022年5月2日 J4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfrontJ9J9J8J8J7J7J7,J8,J9J7,J8,J9入隊入隊隊空：隊空：front=rearfront=rear隊滿：隊滿：front=rearfront=rear解決方案：解決方案：1.1.另外另外設一個標志設一個標志以區別隊空、隊滿以區別隊空、隊滿2 2. .少用一個元素空間少用一個元素空間： 隊空：隊空：

46、front=rearfront=rear 隊滿：隊滿：( (rear+1)%M=frontrear+1)%M=frontJ4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfront0 01 12 23 34 45 5frontfrontJ4,J5,J6J4,J5,J6出隊出隊rearrear 2022年5月2日 循環隊列循環隊列#define MAXQSIZE 100 /最大隊列長度最大隊列長度Typedef struct QElemType *base; /初始化的動態分配存儲空間初始化的動態分配存儲空間 int front; /頭指針頭指針 int re

47、ar; /尾指針尾指針SqQueue; 2022年5月2日 Status InitQueue (SqQueue &Q) Q.base =new QElemTypeMAXQSIZE if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK;循環隊列初始化循環隊列初始化 2022年5月2日 求循環隊列的長度求循環隊列的長度int QueueLength (SqQueue Q) return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; 2022年5月2日 Status EnQueue(SqQueue &Q,QElemT

48、ype e) if(Q.rear+1)%MAXQSIZE=Q.front) return ERROR; Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK;循環隊列入隊循環隊列入隊 2022年5月2日 Status DeQueue (LinkQueue &Q,QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK;循環隊列出隊循環隊列出隊 2022年5月2日 naaa,21. . . .d

49、atadatanextnext隊頭隊頭隊尾隊尾Q.frontQ.frontQ.rearQ.rear鏈隊列鏈隊列 2022年5月2日 typedef struct QNode QElemType data; struct Qnode *next;Qnode, *QueuePtr;typedef struct QueuePtr front; /隊隊頭指針頭指針 QueuePtr rear; /隊尾指針隊尾指針LinkQueue; 鏈隊列鏈隊列 2022年5月2日 Q.frontQ.rearxQ.frontQ.rearxyQ.frontQ.rearxy(a) 空隊列空隊列(b) 元素元素x入入隊列隊

50、列(d) 元素元素x出出隊列隊列Q.frontQ.rear(c) 元素元素y入入隊列隊列鏈隊列鏈隊列 2022年5月2日 Status InitQueue (LinkQueue &Q) Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode); if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK;鏈隊列初始化鏈隊列初始化 2022年5月2日 Status DestroyQueue (LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; free(Q.

51、front); Q.front=Q.rear; return OK;銷毀鏈隊列銷毀鏈隊列 2022年5月2日 Status QueueEmpty (LinkQueue Q) return (Q.front=Q.rear); 判斷鏈隊列是否為空判斷鏈隊列是否為空 2022年5月2日 Status GetHead (LinkQueue Q, QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.front-next-data; return OK;求鏈隊列的隊頭元素求鏈隊列的隊頭元素 2022年5月2日 Status EnQueue(LinkQueu

52、e &Q,QElemType e) p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;鏈隊列入隊鏈隊列入隊Q.frontQ.rearxyp 2022年5月2日 Status DeQueue (LinkQueue &Q,QElemType &e) if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.re

53、ar=p) Q.rear=Q.front; free(p); return OK;鏈隊列出隊鏈隊列出隊Q.frontQ.rearxyp 2022年5月2日 【例例】汽車加油站汽車加油站隨著城市里汽車數量的急速增長，汽車加油隨著城市里汽車數量的急速增長，汽車加油站也漸漸多了起來。通常汽車加油站的結構站也漸漸多了起來。通常汽車加油站的結構基本上是：入口和出口為單行道，加油車道基本上是：入口和出口為單行道，加油車道可能有若干條。每輛車加油都要經過三段路可能有若干條。每輛車加油都要經過三段路程，第一段是在入口處排隊等候進入加油車程，第一段是在入口處排隊等候進入加油車道；第二段是在加油車道排隊等候加油；

54、第道；第二段是在加油車道排隊等候加油；第三段是進入出口處排隊等候離開。實際上，三段是進入出口處排隊等候離開。實際上，這三段都是隊列結構。若用算法模擬這個過這三段都是隊列結構。若用算法模擬這個過程，就需要設置加油車道數加程，就需要設置加油車道數加2 2個隊列。個隊列。3.5 3.5 隊列的應用隊列的應用 2022年5月2日 【例例】模擬打印機緩沖區模擬打印機緩沖區在主機將數據輸出到打印機時，會出現主機速度與在主機將數據輸出到打印機時，會出現主機速度與打印機的打印速度不匹配的問題。這時主機就要停打印機的打印速度不匹配的問題。這時主機就要停下來等待打印機。顯然，這樣會降低主機的使用效下來等待打印機。

55、顯然，這樣會降低主機的使用效率。為此人們設想了一種辦法：為打印機設置一個率。為此人們設想了一種辦法：為打印機設置一個打印數據緩沖區，當主機需要打印數據時，先將數打印數據緩沖區，當主機需要打印數據時，先將數據依次寫入這個緩沖區，寫滿后主機轉去做其他的據依次寫入這個緩沖區，寫滿后主機轉去做其他的事情，而打印機就從緩沖區中按照先進先出的原則事情，而打印機就從緩沖區中按照先進先出的原則依次讀取數據并打印，這樣做即保證了打印數據的依次讀取數據并打印，這樣做即保證了打印數據的正確性，又提高了主機的使用效率。由此可見，打正確性，又提高了主機的使用效率。由此可見，打印機緩沖區實際上就是一個隊列結構。印機緩沖區

56、實際上就是一個隊列結構。 2022年5月2日 【例例】CPUCPU分時系統分時系統在一個帶有多個終端的計算機系統中，同時有多個在一個帶有多個終端的計算機系統中，同時有多個用戶需要使用用戶需要使用CPUCPU運行各自的應用程序，它們分別通運行各自的應用程序，它們分別通過各自的終端向操作系統提出使用過各自的終端向操作系統提出使用CPUCPU的請求，操作的請求，操作系統通常按照每個請求在時間上的先后順序，將它系統通常按照每個請求在時間上的先后順序，將它們排成一個隊列，每次把們排成一個隊列，每次把CPUCPU分配給當前隊首的請求分配給當前隊首的請求用戶，即將該用戶的應用程序投入運行，當該程序用戶，即將該用戶的應用程序投入運行，當該程序運行完畢或用完規定的時間片后，操作系統再將運行完畢或用完規定的時間片后，操作系統再將CPUCPU分配給新的隊首請求用戶，這樣即可以滿足每個用分配給新的隊首請求用戶，這樣即可以滿足每個用戶的請求，又可以使戶的請求，又可以使CPUCPU正常工作。正常工作。 2022年5月2日 【例例】打印楊輝三角形打印楊輝三角形 1 1 i = 1 1 2 1 2 1 3 3 1 3 1 4 6 4 1 4 1 5 0 0 5 1 5 1