C語言數(shù)據(jù)結(jié)構(gòu)第04講棧.ppt

1、實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ),第3章 棧,第 3 章 棧,知 識 點(diǎn) 棧的定義和特點(diǎn) 棧的基本運(yùn)算和算法 棧的典型應(yīng)用 難 點(diǎn) 后綴表達(dá)式的算法 數(shù)制的換算 利用本章的基本知識設(shè)計(jì)相關(guān)的應(yīng)用問題,要 求 掌握棧的特點(diǎn) 掌握棧的基本運(yùn)算 熟悉棧的各種實(shí)際應(yīng)用 能設(shè)計(jì)棧的應(yīng)用的典型算法 了解棧的運(yùn)算時(shí)間復(fù)雜度分析,第3章 目錄,3-1 棧的定義與運(yùn)算 3-2 棧的存儲和實(shí)現(xiàn) 3-3 棧的應(yīng)用舉例 小 結(jié) 實(shí)驗(yàn)3 棧子系統(tǒng) 習(xí)題3,3-1 棧的定義和運(yùn)算,3-1-1 棧（Stack）的定義 1. 棧的定義 棧是限制在表尾進(jìn)行插入和刪除的線性表。,進(jìn)棧,出棧,圖3-1棧的 示意圖,2. 棧的特性 （1）棧的主要特

2、點(diǎn)是“后進(jìn)先出” （2）允許插入、刪除的這一端稱為棧頂（Top），另一端稱為棧底（Bottom）。 3. 應(yīng)用實(shí)例 （1）分幣筒； （2）鐵路調(diào)度站。,3-1-2 棧的運(yùn)算 1進(jìn)棧： Push（ / datatype可根據(jù)用需要定義類型 int top； / 定義棧頂指針 SeqStack； 再定義一個(gè)指向順序棧的指針： SeqStack *S； / 定義S為結(jié)構(gòu)體類型的指針變量,（3）棧操作的示意圖如圖3-3所示。,top=-1,top=0,top=5,top=3,top=9,(a) (b) (c) (d) (e),當(dāng)top = -1時(shí)，表示?？?，如圖3-3（a）； 當(dāng)top=0時(shí)，表示棧中

3、有一個(gè)元素，如圖3-3（b）表示棧中已輸入一個(gè)元素A； 入棧時(shí)，棧頂指針上移，指針top加1，如圖3-3（c）是6個(gè)元素入棧后的狀況； 出棧時(shí)，棧頂指針下移，指針top減1， 如圖3-3（d）是在F、E相繼出棧后的情況。此時(shí)棧中還有A、B、C、D 4個(gè)元素，top=3，指針已經(jīng)指向了新的棧頂。但是出棧的元素F、E仍然在原先的存儲單元，只是不在棧中了，因?yàn)闂Ｊ侵荒茉跅ｍ斶M(jìn)行操作的線性表。 當(dāng)top=9時(shí)，即top=MAXLEN1，表示棧滿，如圖3-3（e）。,2順序棧運(yùn)算的基本算法 （1）置空棧 首先建立?？臻g，然后初始化棧頂指針。 SeqStack *Snull（） SeqStack *s；

4、s=new (SeqStack)； / 在C語言中用s=malloc（sizeof（SeqStack）； s-top= 1； / 置?？?return s； ,（2） 進(jìn)棧 進(jìn)棧運(yùn)算是在棧頂位置插入一個(gè)新元素x，其算法步驟為： (a) 判棧是否為滿，若棧滿，作溢出處理，并返回0； (b) 若棧未滿，棧頂指針top加1； (c) 將新元素x送入棧頂，并返回1。 int Push (SeqStack *s， datatype x) if （s-top= =MAXLEN1） return 0； / 棧滿不能入棧，且返回 0 else s-top+； s-datas-top=x； / 棧不滿，則壓入元

5、素x return 1； / 進(jìn)棧成功，返回1 ,（3）出棧 出棧運(yùn)算是指取出棧頂元素，賦給某一個(gè)指定變量x，其算法步驟為： (a) 判棧是否為空，若?？眨飨乱缣幚?，并返回0； (b) 若棧非空，將棧頂元素賦給變量x； (c) 指針top減1，并返回1。 int Pop（SeqStack *s， datatype *x） if (SEmpty ( s ) ) return 0； / 若?？詹荒艹鰲?，且返回0 else *x=s-datas-top； / 棧不空則棧頂元素存入*x s-top - -； return 1； / 出棧成功，返回1 ,（4）讀棧頂元素 datatype ReadT

6、op（SeqStack *s） if (SEmpty ( s ) ) return 0； / 若?？?，則返回0 else return (s-datas-top )； / 否則，讀棧頂元素，但指針未移動 （5）判棧空 int SEmpty（SeqStack *s） if （s-top= = 1） return 1； / 若棧空，則返回1 else return 0； / 否則返回0 ,（6）判棧滿 int SFull（SeqStack *s） if （s-top= =MAXLEN1） return 1；/ 若棧滿，則返回1 else return 0； / 否則返回0 3-2-2 鏈棧 1鏈棧

7、的實(shí)現(xiàn) 用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的棧稱為鏈棧。因?yàn)殒湕５慕Y(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同，通常就用單鏈表來實(shí)現(xiàn)，在此用LinkStack表示，即有： typedef struct stacknode / 棧的存儲結(jié)構(gòu) datatype data; / 定義數(shù)據(jù)類型 struct stacknode *next; / 定義一個(gè)結(jié)構(gòu)體的鏈指針 stacknode;，* Linkstack； Linkstack top； / top為棧頂指針,由于棧中的操作只能在棧頂進(jìn)行的，所以用鏈表的頭部做棧頂是最合適的。鏈棧結(jié)構(gòu)如圖3-4所示。,圖3-4 鏈棧示意圖,2鏈?；静僮鳎?（1）入棧 void Push(lin

8、kstack *s,int x) stacknode *p=new stacknode; / 申請一個(gè)新結(jié)點(diǎn) p-data=x; / 數(shù)據(jù)入棧 p-next=s-top; / 修改棧頂指針 s-top=p; ,（2） 出棧 int Pop(linkstack *s) int x; / 定義一個(gè)變量x，用以存放出棧的元素 stacknode *p=s-top; / 棧頂指針指向p x=p-data; / 棧頂元素送x s-top=p-next; / 修改棧頂指針 delete p; / 回收結(jié)點(diǎn)p return x; / 返回棧頂元素 ,（3） 顯示 void ShowStack (linkst

9、ack *s) stacknode *p=s-top; if (p= =NULL) / 若?？?，作“棧空”顯示 printf (棧為空); else printf (棧元素為：); while (p!=NULL) /棧非空，則顯示棧中所有元素 printf (%6d,p-data); / 輸出一個(gè)元素 p=p-next; / 修改棧頂指針 printf (n); ,3-3. 棧的應(yīng)用舉例,3-3-1 數(shù)制轉(zhuǎn)換 數(shù)值進(jìn)位制的換算是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算和處理的基本問題。比如將十進(jìn)制數(shù)N轉(zhuǎn)換為j進(jìn)制的數(shù)，其解決的方法很多，其中一個(gè)常用的算法是除j取余法。將十進(jìn)制數(shù)每次除以j，所得的余數(shù)依次入棧，然后按“后

10、進(jìn)先出”的次序出棧便得到轉(zhuǎn)換的結(jié)果。 其算法原理是： N =（N / j）* j + N % j 其中： / 為整除，%為求余,【例3-1】將十進(jìn)制數(shù)138轉(zhuǎn)換為二進(jìn)制數(shù) N N / 2 （整除） N % 2（求余） 138 69 0 69 34 1 34 17 進(jìn) 0 出 17 8 棧 1 棧 8 4 次 0 次 4 2 序 0 序 2 1 0 1 0 1 （138）10 =（10001010）2,1算法思想如下： （1）若 N0，則將N % j 取得的余數(shù)壓入棧s中 ，執(zhí)行（2）； 若N=0，將棧s的內(nèi)容依次出棧，算法結(jié)束。 （2） 用N / j 代替 N （3） 當(dāng)N0，則重復(fù)步驟（1）

11、、（2）。,2. 算法的實(shí)現(xiàn)： void Conversion(int n) / 將十進(jìn)制數(shù)n轉(zhuǎn)換為二進(jìn)制數(shù) linkstack s; int x; s.top=NULL; do x=n%2; / 除2取余 n=n/2; stacknode *p=new stacknode; / 申請一個(gè)新結(jié)點(diǎn) p-next=s.top; / 修改棧頂指針 s.top=p; s.top-data=x; / 入棧,while(n); printf(轉(zhuǎn)換后的二進(jìn)制數(shù)值為：); while(s.top) / 余數(shù)出棧處理 printf(%d,s.top-data); / 輸出棧頂?shù)挠鄶?shù) stacknode* p=s

12、.top; / 修改棧頂指針 s.top=s.top-next; delete p; / 回收一個(gè)結(jié)點(diǎn)，C語言中用free p ,3-3-2 表達(dá)式求值 表達(dá)式是由運(yùn)算對象、運(yùn)算符、括號等組成的有意義的式子。 1中綴表達(dá)式（Infix Notation） 一般我們所用表達(dá)式是將運(yùn)算符號放在兩運(yùn)算對象的中間，比如：a+b，c/d等等，我們把這樣的式子稱為中綴表達(dá)式。 2后綴表達(dá)式（Postfix Notation） 后綴表達(dá)式規(guī)定把運(yùn)算符放在兩個(gè)運(yùn)算對象（操作數(shù)）的后面。在后綴表達(dá)式中，不存在運(yùn)算符的優(yōu)先級問題，也不存在任何括號，計(jì)算的順序完全按照運(yùn)算符出現(xiàn)的先后次次序進(jìn)行。 3中綴表達(dá)式轉(zhuǎn)換為

13、后綴表達(dá)式 其轉(zhuǎn)換方法采用運(yùn)算符優(yōu)先算法。轉(zhuǎn)換過程需要兩個(gè)棧：一個(gè)運(yùn)算符號棧和一個(gè)后綴表達(dá)式輸出符號棧。,（1）讀入操作數(shù)，直接送輸出符號棧。 （2）讀入運(yùn)算符，壓入運(yùn)算符號棧。 (a)若后進(jìn)的運(yùn)算符優(yōu)先級高于先進(jìn)的，則繼續(xù)進(jìn)棧； (b)若后進(jìn)的運(yùn)算符優(yōu)先級不高于先進(jìn)的，則將運(yùn)算符號棧內(nèi)高于或等于后進(jìn)運(yùn)算符級別的運(yùn)算符依次彈出后，自己進(jìn)棧。 （3）括號處理： (a)遇到開括號“（”，進(jìn)運(yùn)算符號棧； (b)遇到閉括號“）”，則把最靠近的開括號“（”，以及其后進(jìn)棧的運(yùn)算符依次彈出到輸出符號棧（括號均不壓入輸出符號棧）。 （4）遇到結(jié)束符“#”，則把運(yùn)算符號棧內(nèi)的所有運(yùn)算符號依次彈出，并壓入輸出符號

14、棧。 （5）若輸入為+、單目運(yùn)算符，改為0與運(yùn)算對象在前，運(yùn)算符在后。 例如：A，轉(zhuǎn)換為：0A。,【例3-2】A / B C + D * EA*C,【例3-3】3 + 4 /（25（6 + 15）* 8,得到后綴表達(dá)式為：3 4 25 6 15 + / 8 * + 4后綴表達(dá)式求值 后綴表達(dá)式求值的運(yùn)算要用到一個(gè)數(shù)棧stack和一個(gè)存放后綴表達(dá)式的字符型數(shù)組exp。其實(shí)現(xiàn)過程就是從頭至尾掃描數(shù)組中的后綴表達(dá)式： （1）當(dāng)遇到運(yùn)算對象時(shí)，就把它插入到數(shù)棧stack中； （2）當(dāng)遇到運(yùn)算符時(shí)，就執(zhí)行兩次出棧的操作，對出棧的數(shù)進(jìn)行該運(yùn)算符指定的運(yùn)算，并把計(jì)算的結(jié)果壓入到數(shù)棧stack。把它插入到數(shù)棧

15、stack中； （3）重復(fù)（1）、（2），直至掃描到表達(dá)式的終止符“#”，在數(shù)棧的棧頂?shù)玫奖磉_(dá)式的值。,以例【例3-3】的結(jié)果看后綴表達(dá)式的計(jì)算過程： 3 4 25 6 15 + - / 8 * + 第1次計(jì)算結(jié)果為：21 第2次計(jì)算結(jié)果為：4 第3次計(jì)算結(jié)果為：1 第4次計(jì)算結(jié)果為：8 第5次計(jì)算結(jié)果為：11,3-3-3 子程序調(diào)用（Subroutine Call） 在計(jì)算機(jī)程序設(shè)計(jì)中，子程序的調(diào)用及返回地址就是利用堆棧來完成的。 在C(或C+)語言的主函數(shù)對無參子函數(shù)的嵌套調(diào)用過程中，在調(diào)用子程序前，先將返回地址保存到堆棧中，然后才轉(zhuǎn)去執(zhí)行子程序。當(dāng)子函數(shù)執(zhí)行到return語句（或函數(shù)結(jié)束

16、）時(shí)，便從棧中彈出返回地址，從該地址處繼續(xù)執(zhí)行程序。 例如：主函數(shù)調(diào)用子函數(shù)a()時(shí)，則在調(diào)用之前先將a函數(shù)返回地址壓入棧中；在子函數(shù)a()中調(diào)用子函數(shù)b()時(shí)，又將b函數(shù)返回地址壓人棧中；同樣，在子函數(shù)b()中調(diào)用子函數(shù)c()時(shí)，又將c函數(shù)返回地址壓人棧中。其調(diào)用返回地址進(jìn)棧示意圖如圖3-5所示。,圖3-5 無參函數(shù)嵌套調(diào)用返回地址進(jìn)棧示意圖 當(dāng)執(zhí)行完子函數(shù)c()以后，就從棧頂彈出c()函數(shù)返回地址，回到子函數(shù)b()；子函數(shù)b()執(zhí)行完畢返回時(shí)，又從棧頂彈出b函數(shù)返回地址，回到子函數(shù)a()；子函數(shù)a()返回時(shí)，再在棧頂彈出a函數(shù)返回地址，回到主函數(shù)，繼續(xù)執(zhí)行主函數(shù)程序。無參函數(shù)嵌調(diào)用返回示意

17、圖如圖3-6所示。,返回地址棧：,圖3-6 無參函數(shù)嵌套調(diào)用返回示意圖,3-3-4 遞歸調(diào)用 1遞歸 一個(gè)直接調(diào)用自己，或者通過一系列調(diào)用語句間接地調(diào)用自己的函數(shù)稱為遞歸函數(shù)。在程序設(shè)計(jì)中，有許多實(shí)際問題是遞歸定義的，使用遞歸的方法編寫程序?qū)⑹乖S多復(fù)雜的問題大大簡化。所以，遞歸是程序設(shè)計(jì)中的一個(gè)強(qiáng)有力的工具。 2典型例子 （1）2階斐波那契（Fibonacci）數(shù)列,0 n=0 1 n=1 Fib( n1 )+Fib( n2 ) 其它情況,Fib(n)=,（2）階乘函數(shù) n!的定義為：,Fac(n)=,1 n=0 / 遞歸終止條件,n*Fac (n-1) n0 / 遞歸步驟,根據(jù)定義不難寫出相

18、應(yīng)的遞歸函數(shù)： int fac ( int n ) if (n= =0) return 1 ； else return (n* fac (n1) )； ,3-3-5 中斷處理和現(xiàn)場保護(hù) 1.中斷處理（Interrupt Processing） 在C+語言中，系統(tǒng)調(diào)用是通過中斷來進(jìn)行，中斷調(diào)用示意圖如圖3-8所示。,圖3-8 中斷調(diào)用示意圖如 如果把中斷處理想象成函數(shù)調(diào)用，則中斷處理程序可以看成被調(diào)用的函數(shù)。,2. 現(xiàn)場保護(hù)和恢復(fù) 執(zhí)行中斷時(shí)，微處理機(jī)有時(shí)必須對狀態(tài)寄存器，累加器，以及相關(guān)的寄存器對進(jìn)行現(xiàn)場保護(hù)（壓棧）；中斷處理完畢，則必須按后進(jìn)先出的原則恢復(fù)現(xiàn)場（出棧）。下面，我們以匯編語言來

19、說明現(xiàn)場保護(hù)和恢復(fù)的原理： ；接受中斷處理 PUSH AX ；保護(hù)現(xiàn)場 PUSH BX PUSH CX PUSH BP PUSHF ；F狀態(tài)寄存器進(jìn)棧 ；中斷處理 POPF ；恢復(fù)現(xiàn)場，后進(jìn)棧的先出棧 POP BP POP CX POP BX POP AX,（1）棧是一種運(yùn)算受限制的線性表，它只允許在棧頂進(jìn)行插入和刪除等操作。 （2）棧的邏輯結(jié)構(gòu)和線性表相同，數(shù)據(jù)元素之間存在一對一的關(guān)系，其主要特點(diǎn)是“后進(jìn)先出”。 （3）棧的存儲結(jié)構(gòu)有順序棧和鏈棧之分，要求掌握棧的C語言描述方法。 （4）重點(diǎn)掌握在順序棧和鏈棧上實(shí)現(xiàn)：進(jìn)棧、出棧、讀棧頂元素、判?？蘸团袟M等基本操作。 （5） 熟悉棧在計(jì)算機(jī)的

20、軟件設(shè)計(jì)中的各種應(yīng)用，能靈活應(yīng)用棧的基本原理解決一些綜合性的應(yīng)用問題。,小 結(jié),實(shí)驗(yàn)3 棧子系統(tǒng),1實(shí)驗(yàn)?zāi)康?（1） 掌握棧的特點(diǎn)及其描述方法。 （2） 用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)一個(gè)棧。 （3） 掌握建棧的各種等基本操作。 （4）掌握棧的幾個(gè)典型應(yīng)用的算法。 2. 實(shí)驗(yàn)內(nèi)容 （1）設(shè)計(jì)一個(gè)字符型的鏈棧； （2）編寫進(jìn)棧、出棧、顯示棧中全部元素的程序； （3）編寫一個(gè)把十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)的應(yīng)用程序； （4）編寫一個(gè)把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式（逆波蘭式）的應(yīng)用程序； （5）設(shè)計(jì)一個(gè)選擇式菜單，以菜單方式選擇上述操作。,棧 子 系 統(tǒng) * * 1-進(jìn) 棧 * * 2-出 棧 * * 3-顯 示 *

21、 * 4-數(shù)制轉(zhuǎn)換 * * 5-逆波蘭式 * * 0-返 回 * * 請選擇菜單號： *教材p64第3行void Stack() ，在作為子系統(tǒng)上機(jī)時(shí)上機(jī)時(shí)改為：void main(),習(xí)題3,參考習(xí)題解答,返回,實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ),第4章 隊(duì)列,第4章 隊(duì)列,知 識 點(diǎn) 隊(duì)列的定義和特點(diǎn) 隊(duì)列的存儲實(shí)現(xiàn)及運(yùn)算實(shí)現(xiàn) 隊(duì)列的應(yīng)用舉例 難 點(diǎn) 循環(huán)隊(duì)列的特點(diǎn)及判斷溢出的條件 利用隊(duì)列的特點(diǎn)設(shè)計(jì)相關(guān)的應(yīng)用問題,要 求 熟練掌握以下內(nèi)容： 隊(duì)列的特點(diǎn)和基本運(yùn)算 循環(huán)隊(duì)列的特征和基本運(yùn)算 了解以下內(nèi)容： 隊(duì)列運(yùn)算的時(shí)間復(fù)雜性分析 隊(duì)列的實(shí)際應(yīng)用,第 4 章 目錄,4-1 隊(duì)列的定義和基本運(yùn)算 4-2 隊(duì)列

22、的存儲及運(yùn)算的實(shí)現(xiàn) 4-3 隊(duì)列的應(yīng)用舉例 小 結(jié) 實(shí)驗(yàn)4 隊(duì)列子系統(tǒng) 習(xí)題4,4-1 隊(duì)列的定義和基本運(yùn)算,4-1-1 隊(duì)列（Queue）的定義 1隊(duì)列的定義 設(shè)有n個(gè)元素的隊(duì)列Q=（a1，a2，a3，an），則稱a1為隊(duì)首元素，an為隊(duì)尾元素。隊(duì)列中的元素按，a1，a2，a3，an1 ，an的次序進(jìn)隊(duì)，按a 1，a2，a3，an1 ，an次序出隊(duì)，即隊(duì)列的操作是按照“先進(jìn)先出” 的原則進(jìn)行的。 2. 隊(duì)列的特性 （1）隊(duì)列的主要特性是“先進(jìn)先出”。 （2）隊(duì)列是限制在兩端進(jìn)行插入和刪除操作的線性表。 能夠插入元素的一端稱為 隊(duì)尾（Rear），允許刪除元素的一端稱為 隊(duì)首（Front）。,圖

23、4-1 隊(duì)列示意圖,a1 a2 a3 a4 a5 an,入隊(duì),出隊(duì),4. 隊(duì)列的實(shí)例 （1）如車站排隊(duì)買票或自動取款機(jī)排隊(duì)取款。 （2）在計(jì)算機(jī)處理文件打印時(shí)，為了解決高速的CPU與低速的打印機(jī)之間的矛盾，對于多個(gè)請求打印文件，操作系統(tǒng)把它們當(dāng)作可以被延遲的任務(wù)，提出打印任務(wù)的先后順序，就是它們實(shí)際打印的先后順序。即按照“先進(jìn)先出”的原則形成打印隊(duì)列。,4-1-2 隊(duì)列的基本運(yùn)算 （1）入隊(duì)操作：InQueue（q，x） 初始條件：隊(duì)q存在且未滿。 操作結(jié)果：輸入一個(gè)元素x到隊(duì)尾，長度加1。 （2）出隊(duì)操作：OutQueue（q，x） 初始條件: 隊(duì)q存在，且非空。 操作結(jié)果：刪除隊(duì)首元素，長

24、度減1。 （3）讀隊(duì)頭元素：ReadFront（q，x） 初始條件： 隊(duì)q存在且非空。 操作結(jié)果： 讀隊(duì)頭元素，隊(duì)列不變。,（4）顯示隊(duì)列中元素ShowQueue (q） 初始條件：隊(duì)列q存在，且非空。 操作結(jié)果：顯示隊(duì)列中所有元素。 （5）判隊(duì)空操作：QEmpty（q） 初始條件：隊(duì)q存在。 操作結(jié)果：若隊(duì)空則返回為0，否則返回為1。 （6）判隊(duì)滿操作：QFull（q） 初始條件：隊(duì)q存在。 操作結(jié)果：若隊(duì)滿則返回為0，否則返回為1。 （7）求隊(duì)列長度Qlen（q） 初始條件：隊(duì)列q存在。 操作結(jié)果：返回隊(duì)列的長度。,4-2 隊(duì)列的存儲實(shí)現(xiàn)及運(yùn)算實(shí)現(xiàn),4-2-1 順序隊(duì)列 1順序隊(duì)列 順序隊(duì)

25、列是用內(nèi)存中一組連續(xù)的存儲單元順序存放隊(duì)列中各元素。所以可以用一維數(shù)組QMAXLEN作為隊(duì)列的順序存儲空間，其中MAXLEN為隊(duì)列的容量，隊(duì)列元素從Q0單元開始存放，直到QMAXLEN1單元。因?yàn)殛?duì)頭和隊(duì)尾都是活動的，因此，除了隊(duì)列的數(shù)據(jù)以外，一般還設(shè)有隊(duì)首（front）和隊(duì)尾（rear）兩個(gè)指針。,順序隊(duì)可以用C+語言定義： #define MAXLEN 10 / 隊(duì)列的最大容量 typedef struct datatype QMAXLEN； / datatype 可根據(jù)用戶需要定義 int front= 1, rear= 1； / 定義隊(duì)頭、隊(duì)尾指針，并置隊(duì)列為空 Queue； Queu

26、e *p； / 定義一個(gè)指向隊(duì)的指針變量 p=new Queue； / 申請一個(gè)順序隊(duì)的存儲空間 / 在C中用p = malloc（sizeof（Queue） 設(shè)： 隊(duì)頭指針：p-front 指向隊(duì)頭元素前面一個(gè)位置 隊(duì)尾指針：p-rear 指向隊(duì)尾元素。,（1）判隊(duì)空 當(dāng)p-front = p-rear= 1時(shí)表示隊(duì)空。如圖4-2（a） （2）入隊(duì) 在無溢出的情況下，隊(duì)尾指針加1，新元素即可入隊(duì)： p-rear+； / 先將隊(duì)尾指針加1 p-Qp-rear=x； / 入隊(duì) （3）出隊(duì)。 在隊(duì)列非空的情況下允許出隊(duì)，出隊(duì)時(shí)隊(duì)頭指針加1， 隊(duì)頭元素即可輸出： p-front+； x=p-Qp-f

27、ront； / 隊(duì)頭元素送x （4）隊(duì)列的長度： m= (p-rear)(p-front)； （5）判隊(duì)滿： m= MAXLEN； 判隊(duì)空： m=0 。,Rear=-1 front=-1 (a),rear=4,rear=7,rear=9,front=-1,front=4,front=4,(b) (c) (d),圖4-2,從示意圖中可以看到，隨著入隊(duì)、出隊(duì)操作的進(jìn)行，整個(gè)隊(duì)列會整體向后移動，這樣就出現(xiàn)了圖4-2（d）中的現(xiàn)象：隊(duì)尾指針雖然已經(jīng)移到了最后，而隊(duì)列卻未真滿的“假溢出”現(xiàn)象，使得隊(duì)列的空間沒有得到有效的利用。 2循環(huán)隊(duì)列 為了解決上述隊(duì)列的“假溢出”現(xiàn)象，要做移動操作，當(dāng)移動數(shù)據(jù)較多時(shí)

28、將會影響隊(duì)列的操作速度。一個(gè)更有效的方法是將隊(duì)列的數(shù)據(jù)區(qū)Q0 .MAXLEN-1看成是首尾相連的環(huán)，即將表示隊(duì)首的元素Q0與表示隊(duì)尾的元素QMAXLEN1連接起來，形成一個(gè)環(huán)形表，這就成了循環(huán)隊(duì)列，如圖4-3所示。,圖4-3 循環(huán)隊(duì)列示意圖,MAXLEN-1,圖4-4是假設(shè)長度為10的循環(huán)隊(duì)列操作示意圖。 因?yàn)槭穷^尾相接的循環(huán)結(jié)構(gòu)，所以將入隊(duì)時(shí)的隊(duì)尾指針加1操作修改為： p-rear= (p-rear+1) % MAXLEN； 將出隊(duì)時(shí)的隊(duì)頭指針加1操作修改為： p-front= (p-front+1) % MAXLEN； 在圖4-4（a）中，此時(shí)front=4，rear=8，隊(duì)列中具有: a

29、6 、a7 、a8、a9四個(gè)元素； 隨著a10a15相繼入隊(duì)，此時(shí) front=4，rear=4，隊(duì)列已滿，如（b）所示，可見在隊(duì)滿情況下有： front= =rear。,若在（a）的情況下，a6a9相繼出隊(duì)，此時(shí)隊(duì)空， front=8，rear=8，如（c）所示，也有：front= =rear，也就是說，僅根據(jù)等式front= =rear 無法有效判別是“隊(duì)滿”還是“隊(duì)空”。 兩種常用的方法： （1）規(guī)定：當(dāng)front= =rear，表示循環(huán)隊(duì)列為空； 當(dāng)front= =（rear+1）% MAXLEN，表示循環(huán)隊(duì)列為滿。 （2）在定義結(jié)構(gòu)體時(shí)，附設(shè)一個(gè)存儲循環(huán)隊(duì)列中元素個(gè)數(shù)的變量n，當(dāng)n=

30、 =0時(shí)表示隊(duì)空； 當(dāng)n= =MAXLEN時(shí)為隊(duì)滿。,循環(huán)隊(duì)列的結(jié)構(gòu)體類型定義如下： typedef struct datatype dataMAXLEN； / 定義數(shù)據(jù)的類型及數(shù)據(jù)的存儲區(qū) int front，rear； / 定義隊(duì)頭、隊(duì)尾指針 int n； / 用以記錄循環(huán)隊(duì)列中元素的個(gè)數(shù) csequeue； / 循環(huán)隊(duì)列變量名 3.循環(huán)隊(duì)列的基本運(yùn)算 （1）置空隊(duì) csequeue* IniQueue ( ) q=new csequeue ; / 在c語言中用malloc (sizeof (csequeue) ) q-front=q-rear=MAXLEN1； q-n=0； return

31、 q； ,（2）入隊(duì) int InQueue ( csequeue *q ,datatype x) if (n= =MAXLEN) printf (隊(duì)滿)； return 0； / 隊(duì)滿不能入隊(duì)，返回0 else q-rear=(q-rear+1) % MAXLEN； q-dataq-rear=x； q-n+； return 1； / 入隊(duì)完成，返回1 ,（3）出隊(duì) int Outsequeue (csequeue *q ,datatype *x) if (n= =0) printf (隊(duì)空)； return 0； / 隊(duì)空不能出隊(duì)，返回0 else q-front=(q-front+1) %

32、 MAXLEN； *x=q-dataq-front； / 讀出隊(duì)頭元素 q-n ； return 1； / 出隊(duì)完成，返回1 ,（4）判隊(duì)空 int Empsequeue (csequeue *q) if (q-n = = 0) return 1； else return 0； 4-2-2 鏈隊(duì)列 1鏈隊(duì)列的結(jié)構(gòu) 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊(duì)列（或鏈隊(duì)），實(shí)際上它是一個(gè)帶有頭指針（front）和尾指針（rear）的單鏈表。為了處理方便，也可以給鏈隊(duì)列附加一個(gè)頭結(jié)點(diǎn)。鏈隊(duì)列為空的條件是front=rear，即隊(duì)列的頭指針和尾指針均指向表頭結(jié)點(diǎn)，如圖4-5（a）所示。,圖4-5 鏈隊(duì)列的入隊(duì)、出隊(duì),

33、圖4-5中頭指針front和尾指針rear是兩個(gè)獨(dú)立的指針變量，從結(jié)構(gòu)性上考慮，有時(shí)也兩個(gè)指針封裝在一個(gè)結(jié)構(gòu)中。 2鏈隊(duì)的描述： typedef struct queuenode datatype data; / datatype為特定的類型，根據(jù)具體情況可以是char或int等 struct queuenode *next; queuenode; / 鏈隊(duì)結(jié)點(diǎn)的類型datatype typedef struct queuenode *front,*rear; linkqueue; / 將頭指針、尾指針封裝在一起的鏈隊(duì),3頭指針和尾指針封裝在一個(gè)結(jié)構(gòu)中的鏈隊(duì)列 如圖4-6所示為頭指針和尾指針封

34、裝在一個(gè)結(jié)構(gòu)中的鏈隊(duì)列。,圖4-6 鏈隊(duì)列示意圖,4鏈隊(duì)的基本運(yùn)算： （1）入隊(duì)（進(jìn)隊(duì)） void InQueue (linkqueue *q) / 進(jìn)隊(duì)函數(shù) int x; / 定義入隊(duì)元素類型 queuenode *p=new queuenode; / 申請一個(gè)新結(jié)點(diǎn) p-data=x; / 輸入元素 p-next=NULL; / 修改指針 if (q-front= =NULL) q-front=p; else q-rear-next=p; q-rear=p; ,（2） 出隊(duì) int OutQueue(linkqueue *q,int *v) / 出隊(duì)函數(shù) queuenode *p; if

35、(q-front= =NULL) / 判隊(duì)空 return 0; else p=q-front; / 若隊(duì)不空，則作出隊(duì)處理 *v=p-data; q-front=p-next; if(q-front=NULL) q-rear=NULL; delete p; / 回收結(jié)點(diǎn) return 1; / 返回1 ,（3）讀隊(duì)頭元素 void ReadFront (linkqueue *q) / 讀隊(duì)首元素函數(shù) if (q=NULL|q-front= =NULL) / 判隊(duì)空 printf(隊(duì)空!); else printf (q-front-data); / 若隊(duì)不空，則讀隊(duì)頭元素 ,（4）顯示隊(duì)列中

36、元素 void ShowQueue(linkqueue *q) / 顯示隊(duì)列 queuenode *p=q-front; if (p= =NULL) / 判隊(duì)空 printf(隊(duì)列為空!); else while(p!=NULL) / 若隊(duì)不空，則輸出隊(duì)中元素 printf (p-data); p=p-next; / 修改指針 printf(n); ,隊(duì)列是一種應(yīng)用廣泛的數(shù)據(jù)結(jié)構(gòu)，凡具有“先進(jìn)先出”需要排隊(duì)處理的問題，都可以使用隊(duì)列來解決。 1. 隊(duì)列在輸入、輸出管理中的應(yīng)用 在計(jì)算機(jī)進(jìn)行數(shù)據(jù)輸入、輸出處理時(shí)，由于外部設(shè)備的速度遠(yuǎn)遠(yuǎn)低于CPU數(shù)據(jù)處理的速度，此時(shí)可以設(shè)定一個(gè)“隊(duì)列緩沖區(qū)”進(jìn)行緩

37、沖。當(dāng)計(jì)算機(jī)要輸出數(shù)據(jù)時(shí)，將計(jì)算機(jī)的數(shù)據(jù)按塊（例如每塊512B）逐個(gè)添加到“隊(duì)列緩沖區(qū)”的尾端，而外部設(shè)備則按照其輸出速度從隊(duì)首逐個(gè)取出數(shù)據(jù)塊輸出。這樣，雖然輸出數(shù)據(jù)速度較慢，但卻能保證與計(jì)算機(jī)輸出的數(shù)據(jù)有完全相同的次序，而不致發(fā)生輸出次序的混亂或數(shù)據(jù)的丟失。,4-3 隊(duì)列應(yīng)用舉例,2.對CPU的分配管理 一般的計(jì)算機(jī)系統(tǒng)只有一個(gè)CPU，如果在系統(tǒng)中有多個(gè)進(jìn)程都滿足運(yùn)行條件，這就可以用一個(gè)就緒隊(duì)列來進(jìn)行管理。當(dāng)某個(gè)進(jìn)程需要運(yùn)行時(shí)，它的進(jìn)程名就被插入到就緒隊(duì)列的尾端。如果此隊(duì)列是空的，CPU就立即執(zhí)行該進(jìn)程；如果此隊(duì)列非空，則該進(jìn)程就需要排在隊(duì)列的尾端進(jìn)行等待。CPU總是首先執(zhí)行排在隊(duì)首的進(jìn)程，

38、一個(gè)進(jìn)程分配的一段時(shí)間執(zhí)行完了，又將它插入到隊(duì)尾等待，CPU轉(zhuǎn)而為下一個(gè)出現(xiàn)在隊(duì)首的進(jìn)程服務(wù)。如此，按“先進(jìn)先出”的原則一直進(jìn)行下去，直到執(zhí)行完的進(jìn)程從隊(duì)列中逐個(gè)刪除掉。,3優(yōu)先隊(duì)列（Priority Queue） 在實(shí)際應(yīng)用中，有時(shí)往往需要根據(jù)任務(wù)的優(yōu)先級別來決定先做那些最重要的事情，此時(shí)必須對這種“先進(jìn)先出”的規(guī)則進(jìn)行適當(dāng)?shù)男薷摹?假設(shè)每個(gè)元素都有一個(gè)相當(dāng)于權(quán)的數(shù)據(jù)項(xiàng)，那么我們就可以根據(jù)權(quán)值的大小來決定元素出隊(duì)的順序。也就是說，在隊(duì)列中哪一個(gè)優(yōu)先級最高，那一個(gè)就優(yōu)先出隊(duì)。這種按優(yōu)先級高低來決定出隊(duì)順序的隊(duì)列，稱為優(yōu)先隊(duì)列。 優(yōu)先隊(duì)列的一個(gè)典型的應(yīng)用就是批處理操作系統(tǒng)中的作業(yè)處理。每個(gè)作業(yè)都有一個(gè)優(yōu)先級，系統(tǒng)在處理文件的時(shí)候，并不是根據(jù)一般隊(duì)列的“先進(jìn)先出”原則，而是根據(jù)文件優(yōu)先級的高低來選擇處理對象。,在優(yōu)先隊(duì)列中的每一個(gè)元素都有一個(gè)被稱為權(quán)的數(shù)據(jù)項(xiàng)，權(quán)的大小決定了元素的優(yōu)先級。實(shí)現(xiàn)優(yōu)先隊(duì)列有兩種方法： （1）按權(quán)的大小進(jìn)行插入，使整個(gè)隊(duì)列始終保持按優(yōu)先級次序排列的狀態(tài)，而刪除操作則和普通隊(duì)列一樣，只刪除隊(duì)首元素。 （2）插入操作和普通隊(duì)列一樣，只在隊(duì)尾進(jìn)行插入，而刪除操作則是根據(jù)元素的優(yōu)先級來進(jìn)行的，即只能刪除優(yōu)先級最高的元素。 限于篇幅，有關(guān)優(yōu)先隊(duì)列具體算法的實(shí)現(xiàn)，在此不作介紹了。,4雙隊(duì)列（D