隊列及其應(yīng)用

1、隊列及其應(yīng)用數(shù) 據(jù) 結(jié) 構(gòu)數(shù)組與線性表1.1 隊列（Queue） 隊列是一種運算受限制的線性表，元素的添加在表的一端進行，而元素的刪除在表的另一端進行。允許添加元素的一端稱為隊尾（Rear）；允許刪除元素的一端稱為隊頭（Front）。向隊列添加元素稱為入隊，從隊列中刪除元素稱為出隊。 新入隊的元素只能添加在隊尾，出隊的元素只能是刪除隊頭的元素，隊列的特點是先進入隊列的元素先出隊，所以隊列也稱作先進先出表或FIFO（First-In-First-Out）表。 數(shù)組與線性表隊列的表示與堆棧類似，隊列也可以簡單的用一維數(shù)組表示。設(shè)數(shù)組名為Queue，其下標(biāo)下界為1，上界為n。一般使用一個變量r指示隊

2、尾的下標(biāo)值，叫做隊尾指針；用另一個變量f指示隊頭的下標(biāo)值，稱為隊頭指針。隊列中元素的數(shù)目等于零稱為空隊列，此時隊頭指針和隊尾指針均為零，即f=r=0。數(shù)組與線性表假定有AF 6個元素先后進入隊列，但A、B兩個元素已陸續(xù)出隊了，故隊尾指針r=6，而隊頭指針f=3。數(shù)組與線性表1. 入隊（insert） 當(dāng)給隊列插入元素時，隊尾指針r后移而隊頭指針不動，但有一個情況例外，即當(dāng)向空隊列插入第一個元素時，隊頭指針與隊尾指針同時由0變?yōu)?。 設(shè)用下標(biāo)從1到n的數(shù)組Q表示隊列，且已知待添加的元素在變量x中。 數(shù)組與線性表入隊函數(shù) void insert (Q, int n, f, r, x) if (r

3、= n) printf(“溢出!n”);/*判斷是否已到數(shù)組末端*/ else r=r+1； Qr=x;/*插入元素*/ if (f = 0) f=1; /*判斷原來是否為空隊列*/ 數(shù)組與線性表2. 出隊（Delete） 當(dāng)從隊列刪除元素時，隊頭指針f后移而隊尾指針r不動，但也有一個情況例外，即當(dāng)刪除了最后一個元素，隊列成為了空隊列時，隊頭指針與隊尾指針同時變?yōu)?。假設(shè)要求將出隊的元素值賦給變量x 。數(shù)組與線性表出隊函數(shù)void Delete (Q, int f, r, n, x) if (f=0) printf(“下溢出!n”); /*判斷是否為空隊列*/ else x=Qf; /*取隊頭

4、元素給x賦值*/ if (f=r) f=0; /*若出隊的是最后一個元素，變成空隊列*/ r=0; else f=f+1; /*隊頭指針后移*/ 數(shù)組與線性表3. 隊列存在的問題 由于隊列的入隊操作是在兩端進行的，隨著元素的不斷插入，刪除，兩端都向后移動，隊列會很快移動到數(shù)組末端造成溢出，而前面的單元無法利用。 解決辦法：1) 每次刪除一個元素后，將整個隊列向前移動一個單元，保持隊列頭總固定在數(shù)組的第一個單元 。2) 將所用的數(shù)組想象成是頭尾相接的圓環(huán)，當(dāng)隊列的尾端到達數(shù)組的末端（第n個單元）時，如果再插入元素可繼續(xù)使隊列向數(shù)組的前端（第1個單元）延長 ，此隊列稱為循環(huán)隊列。數(shù)組與線性表1.2

5、 循環(huán)隊列圖中陰影部分為隊列中元素。如何判斷一個循環(huán)隊列是滿還是空？ 數(shù)組與線性表判斷循環(huán)隊列是否滿或空 滿：隊尾經(jīng)過一個循環(huán)而到達隊首的前一個單元時，這種情況下如果再插入新的元素時，新元素就要把原隊頭的元素覆蓋，因此，當(dāng)r=f時，插入新的元素會造成隊列首尾重疊； 空：在隊列進行刪除運算時，當(dāng)f=r時表明刪除的是隊列的最后一個元素，刪除這個元素后，隊列就變成空隊列。 數(shù)組與線性表循環(huán)隊列入隊函數(shù)void insert(Q, int n, f, r, i) if (r = n) r = 1;/*到達數(shù)組末端則向前端延長*/ else r = r+1; if (r = f) printf(“溢出！

6、n”); else Qr=i;/*插入新元素*/ if (f=0) f=1; /*判定是否原來是空隊列*/ 數(shù)組與線性表循環(huán)隊列出隊函數(shù)void Delete(Q, int n, f, r, x) if (f=0) printf (“是空隊列！n”); /*是否為空*/ else x=Qf;/*取隊頭元素賦給變量x*/ if (f=r) f=0; r=0; else if (f=n) f=1; /*由數(shù)組末端移到前端*/ else f=f+1; /*隊頭指針后移*/ 數(shù)組與線性表1.3 隊列的應(yīng)用 對于各種具有“先進先出”需排隊處理的問題，都可以應(yīng)用隊列來解決。 例如，操作系統(tǒng)在管理和分配系統(tǒng)

7、資源時，大量的應(yīng)用了隊列這種數(shù)據(jù)結(jié)構(gòu)。1) 隊列在輸入/輸出管理中的應(yīng)用 2) 對CPU的分配管理 返回數(shù)組與線性表例2.1 一個雙向棧是將兩個棧用一個數(shù)組構(gòu)成，它們的棧底分別設(shè)在數(shù)組的兩端。當(dāng)一個棧中元素的數(shù)目小于n/2時，另一個棧相應(yīng)的可以大于n/2。試寫出以數(shù)組高端為底的棧的入棧和出棧的算法。 數(shù)組與線性表例2.1解答這個棧的棧頂指針top2是按相反的方向移動的，因此算法有所不同：入棧時為：top2=top2-1出棧時為：top2=top2+1 兩個棧在進棧過程中防止溢出的條件是：top2=top1+1 。出棧過程中防止下溢出及判斷空棧的條件分別為： top1=0，top2=（n+1）。

8、 數(shù)組與線性表入棧算法 void push (ST, int n, top1, top2, G) if (top2=top1+1) printf(“溢出!n”); else top2=top2-1; STtop2=G; /*插入新元素*/ 數(shù)組與線性表出棧算法void pop (ST, int n, top1, top2, x) if (top2=n+1) printf(“下溢出!n”); else x=STtop2; top2=top2+1; 數(shù)組與線性表例2.2 對于循環(huán)隊列，試寫出求隊列長度的算法 。解1：設(shè)隊列的最大元素個數(shù)為n，設(shè)一個計數(shù)器，將其初始值設(shè)為0。從隊首開始，沿著隊列順序搜索，每走過一個元素，計數(shù)器加1，直到隊尾，則