第2章隊列(C版)

1、第二章 隊列 隊列是限定在一端進行插入，另一端進行刪除特殊線性表。就像排隊買東西，排在前面的人買完東西后離開隊伍（刪除），而后來的人總是排在隊伍未尾（插入）。通常把隊列的刪除和插入分別稱為出隊和入隊。允許出隊的一端稱為隊頭，允許入隊的一端稱為隊尾。所有需要進隊的數(shù)據(jù)項，只能從隊尾進入，隊列中的數(shù)據(jù)項只能從隊頭離去。由于總是先入隊的元素先出隊（先排隊的人先買完東西），這種表也稱為先進先出（FIFO）表。 隊列可以用數(shù)組Qm+1來存儲，數(shù)組的上界即是隊列所容許的最大容量。在隊列的運算中需設兩個指針： head：隊頭指針，指向實際隊頭元素的前一個位置 tail：隊尾指針，指向實際隊尾元素所在的位置

2、一般情況下，兩個指針的初值設為，這時隊列為空，沒有元素。圖1 (a)畫出了一個由個元素構成的隊列，數(shù)組定義Q11。 Qi i=3,4,5,6,7,8 頭指針head2，尾指針tail8。 隊列中擁有的元素個數(shù)為:L=tail-head現(xiàn)要讓隊頭的元素出隊，則需將頭指針加。即head=head+1這時頭指針向上移動一個位置，指向Q3，表示Q3已出隊。見圖1 (b)。 如果想讓一個新元素入隊，則需尾指針向上移動一個位置。即tail=tail+1這時Q9入隊，見圖1 (c)。 當隊尾已經(jīng)處理在最上面時，即tail=10，見圖1 (d)，如果還要執(zhí)行入隊操作，則要發(fā)生“上溢”，但實際上隊列中還有三個空

3、位置，所以這種溢出稱為“假溢出”。 克服假溢出的方法有兩種。一種是將隊列中的所有元素均向低地址區(qū)移動，顯然這種方法是很浪費時間的；另一種方法是將數(shù)組存儲區(qū)看成是一個首尾相接的環(huán)形區(qū)域。當存放到n地址后，下一個地址就翻轉為。在結構上采用這種技巧來存儲的隊列稱為循環(huán)隊列，見圖2 循環(huán)隊的入隊算法如下： 1、tail=tail+1； 2、若tail=n+1，則tail=1； 3、若head=tail尾指針與頭指針重合了，表示元素已裝滿隊列， 則作上溢出錯處理； 4、否則，Qtail=x，結束（x為新入出元素）。 隊列和棧一樣，有著非常廣泛的應用。 考慮一個分時系統(tǒng)，如果一臺計算機聯(lián)有四個終端，即允許

4、四個用戶同時使用這一臺計算機。那么，計算機系統(tǒng)必須設立一個隊列， 用以管理各終端用戶使用CPU的請求。當某個用戶要求使用CPU時，相應的終端代號就入隊（插入隊尾），而隊頭的終端用戶則是CPU當前服務的對象。我們考慮最簡單的情況， 對于當前用戶（隊頭），系統(tǒng)每次分配一個為時間片的時間間隔，在一個時間片內(nèi)，如果當前用戶的作業(yè)沒有結束，則該終端用戶的代號出隊后重新入隊，插入隊尾，等待下一次CPU服務。如果某個用戶的作業(yè)運行結束，則先退出，出隊后不再入隊，整個運行過程就是各終端代號不斷地入隊、出隊，CPU 輪流地為（）個終端用戶服務。由于計算機的運行速度極快，所以，對于每個終端用戶來說，似乎計算機是單

5、獨在為其服務。 和線性表一樣，棧和隊可以采用鏈表存儲結構，當要實現(xiàn)多個棧共享內(nèi)存或多個隊共享內(nèi)存時，選擇鏈式分配結構則更為合適。【例1】假設在周末舞會上，男士們和女士們進入舞廳時，各自排成一隊。跳舞開始時，依次從男隊和女隊的隊頭上各出一人配成舞伴。規(guī)定每個舞曲能有一對跳舞者。若兩隊初始人數(shù)不相同，則較長的那一隊中未配對者等待下一輪舞曲?，F(xiàn)要求寫一個程序，模擬上述舞伴配對問題。輸入：第一行兩隊的人數(shù) 第二行舞曲的數(shù)目【分析】：設計兩個隊列分別存放男士和女士。每對跳舞的人一旦跳完后就回到隊尾等待下次被選。如m=4 n=3 k=6【參考程序】#include#includeusing namespa

6、ce std;int a10001,b10001,k1=1,k,i,f1=1,r1,f2=1,r2;main() int m,n; cinmn; for (i=1;i=m;i+) ai=i; for (i=1;ik; r1=m; r2=n; while (k1=k) printf(%d %dn,af1,bf2); r1+; ar1=af1; f1+; /第一次am+1=a1=1,第二次am+2=a2=2,如此循環(huán) r2+; br2=bf2; f2+; /第一次bn+1=b1=1,第二次bn+2=b2=2,如此循環(huán) k1+; return 0; 【例2】Blah數(shù)集【3.4數(shù)據(jù)結構之隊列2729

7、】 大數(shù)學家高斯小時候偶然間發(fā)現(xiàn)一種有趣的自然數(shù)集合Blah，對于以a為基的集合Ba定義如下： (1)a是集合Ba的基，且a是Ba的第一個元素； (2)如果x在集合Ba中，則2x+1和3x+1也都在集合Ba中； (3)沒有其他元素在集合Ba中了。 現(xiàn)在小高斯想知道如果將集合Ba中元素按照升序排列，第N個元素會是多少？輸入: 輸入包括很多行，每行輸入包括兩個數(shù)字，集合的基a(1=a=50)以及所求元素序號n(1=n=1000000)輸出: 對于每個輸入，輸出集合Ba的第n個元素值樣例輸入: 1 100 28 5437樣例輸出: 418 900585分析： 題目要求輸出集合中第n小的數(shù)，我們可以按

8、照從小到大的順序把序列中的前n個數(shù)計算出來，注意數(shù)集中除了第一個數(shù)a以外，其余每一個數(shù)y一定可以表示成2x+1或者3x+1的形式，其中x是數(shù)集中某一個數(shù)。因此除了第一數(shù)a以外，可以把數(shù)集q的所有數(shù)分成兩個子集，一個是用2x+1來表示的數(shù)的集合1，另一個是用3x+1來表示的數(shù)的集合2，兩個集合要保持有序非常容易，只需用兩個指針two和three來記錄，其中two表示集合1下一個要產(chǎn)生的數(shù)是由qtwo*2+1得到，three表示集合2下一個要產(chǎn)生的數(shù)是由qthree*3+1得到。接下來比較qtwo*2+1和qthree*3+1的大小關系： (1) qtwo*2+1=qthree*3+1：處理方法同

9、上。 如此循環(huán)直到產(chǎn)生出數(shù)集的第n個數(shù)?！緟⒖汲绦颉?include#includeusing namespace std;const int N=1000100;long long qN;int a,n;void work(int a,int n)int rear=2;q1=a;int two=1,three=1;while(rear=n) long long t1=qtwo*2+1,t2=qthree*3+1; int t=min(t1,t2); if (t1t2) two+; else three+; if (t=qrear-1) continue; qrear+=t;coutqnan)

10、 work(a,n);return 0;【例3】設有個人依次圍成一圈，從第個人開始報數(shù)，數(shù)到第個人出列，然后從出列的下一個人開始報數(shù)，數(shù)到第個人又出列，如此反復到所有的人全部出列為止。設個人的編號分別為1，2，n，打印出列的順序?！舅惴ǚ治觥?本題我們可以用數(shù)組建立標志位等方法求解，但如果用上數(shù)據(jù)結構中循環(huán)鏈的思想，則更貼切題意，解題效率更高。人圍成一圈，把一人看成一個結點，人之間的關系采用鏈接方式，即每一結點有一個前繼結點和一個后繼結點，每一個結點有一個指針指向下一個結點，最后一個結點指針指向第一個結點。這就是單循環(huán)鏈的數(shù)據(jù)結構。當人出列時，將結點的前繼結點指針指向結點的后繼結點指針，即把結

11、點驅出循環(huán)鏈。1、建立循環(huán)鏈表。 當用數(shù)組實現(xiàn)本題鏈式結構時，數(shù)組ai作為指針變量來使用，ai存放下一個結點的位置。設立指針j指向當前結點，則移動結點過程為j=aj，當數(shù)到m時，m結點出鏈，則aj=aaj。 當直接用鏈來實現(xiàn)時，則比較直觀，每個結點有兩個域：一個數(shù)值域，一個指針域，當數(shù)到m時，m出鏈，將m結點的前繼結點指針指向其后繼結點；2、設立指針，指向當前結點，設立計數(shù)器，計數(shù)數(shù)到多少人；3、沿鏈移動指針，每移動一個結點，計數(shù)器值加，當計數(shù)器值為時， 則結點出鏈，計數(shù)器值置為。4、重復，直到n個結點均出鏈為止。【參考程序】用數(shù)組實現(xiàn)鏈式結構#includeusing namespace s

12、td;const int n=10,m=4; /設有10個人,報到4的人出列int an+1,j=n,k=1,p=0;main() for (int i=1;in;i+) ai=i+1; /建立鏈表 an=1; /第n人指向第1人，形成一個環(huán) while (pn) /n個人均出隊為止 while(km) /報數(shù),計數(shù)器加1 j=aj; k+; printf(%d ,aj); p+; /數(shù)到m,此人出隊,計數(shù)器置1 aj=aaj; k=1; return 0;【例4】連通塊描述: 一個n * m的方格圖，一些格子被涂成了黑色，在方格圖中被標為1，白色格子標為0。問有多少個四連通的黑色格子連通塊。

13、四連通的黑色格子連通塊指的是一片由黑色格子組成的區(qū)域，其中的每個黑色格子能通過四連通的走法（上下左右），只走黑色格子，到達該聯(lián)通塊中的其它黑色格子。輸入: 第一行兩個整數(shù)n,m(1=n,m=100)，表示一個n * m的方格圖。 接下來n行，每行m個整數(shù)，分別為0或1，表示這個格子是黑色還是白色。輸出: 一行一個整數(shù)ans，表示圖中有ans個黑色格子連通塊。樣例輸入3 31 1 10 1 01 0 1樣例輸出3分析： 我們可以枚舉每個格子，若它是被涂黑的，且它不屬于已經(jīng)搜索過的聯(lián)通塊，則由它開始，擴展搜索它所在的聯(lián)通塊，并把聯(lián)通塊里的所有黑色格子標記為已搜索過。 如何擴展搜索一個聯(lián)通塊呢？我們

14、用一個搜索隊列，存儲要搜索的格子。每次取出隊首的格子，對其進行四連通擴展，若有黑格子，將其加入隊尾,擴展完就把該格子刪除。當隊列為空時，一個聯(lián)通塊就搜索完了。 如樣例所對應的方格圖如下所示： 現(xiàn)在我們以樣例為例模擬出這個方格圖的搜索順序： 將(1,1)加入隊列，(1,1)表示左上角這個格子，當前隊列為：(1,1)，聯(lián)通塊加1等于1。 取出隊首的(1,1)，標記為已搜索并對其進行四連通擴展，擴展出(1,2)，刪除(1,1)隊列變?yōu)椋?1,2)。 取出隊首的(1,2)，標記為已搜索并對其進行四連通擴展，擴展到了(1,1)，(1,3)，(2,2)，(1,1)已經(jīng)被標記搜索過，所以只將(1,3)，(2

15、,2)加入隊列，刪除隊首(1,2),隊列變?yōu)椋?1,3)，(2,2)。 取出隊首的(1,3)，沒有擴展出新格子，刪除隊首隊列變?yōu)椋?2,2) 取出隊首的(2,2)，沒有擴展出新格子，隊列變?yōu)椤Ｍ瓿梢?1,1)開始的搜索。 將(3,1)加入隊列，隊列變?yōu)椋?3,1)，聯(lián)通塊數(shù)加1變?yōu)?。 取出隊首的(3,1)，沒有擴展出新格子，刪除隊首隊列變?yōu)椤Ｍ瓿梢?3,1)開始的搜索。 將(3,3)加入隊列，隊列變?yōu)椋?3,3)，聯(lián)通塊數(shù)加1變?yōu)?。 取出隊首的(3,3)，沒有擴展出新格子，刪除隊首隊列變?yōu)?。完成?3,3)開始的搜索。無法再加入新的元素，程序結束?！緟⒖汲绦颉?include using

16、namespace std; const int N = 110; const int flag42 = 0, 1, 0, -1, 1, 0, -1, 0; int aNN,queueN * N2; int n, m, ans; bool pNN; void bfs(int x,int y) int front =0, rear =2; queue10 = x,queue11 = y; while (front rear-1) + front; x = queuefront0; y = queuefront1; for (int i = 0;i 4;+ i) int x1 = x + flag

17、i0; int y1 = y + flagi1; if (x1 1 | y1 n | y1 m | !ax1y1 | px1y1) continue; px1y1 = true; queuerear0 = x1; queuerear+1 = y1; int main() cin n m; for (int i = 1; i = n; + i) for (int j = 1; j aij; for (int i = 1; i = n; + i) for (int j = 1; j = m; + j) if (aij & !pij) + ans; bfs(i,j); cout ans endl;

18、return 0; 【樣例輸入】area.in0 0 0 0 0 0 0 0 0 00 0 0 0 1 1 1 0 0 00 0 0 0 1 0 0 1 0 00 0 0 0 0 1 0 0 1 00 0 1 0 0 0 1 0 1 00 1 0 1 0 1 0 0 1 00 1 0 0 1 1 0 1 1 00 0 1 0 0 0 0 1 0 00 0 0 1 1 1 1 1 0 00 0 0 0 0 0 0 0 0 0【樣例輸出】area.out151、編程計算由“*”號圍成的下列圖形的面積。面積計算方法是統(tǒng)計*號所圍成的閉合曲線中水平線和垂直線交點的數(shù)目。如下圖所示，在10*10的二維數(shù)

19、組中，有“*”圍住了15個點，因此面積為15?！旧蠙C練習】2、奇怪的電梯(lift.cpp)【問題描述】大樓的每一層樓都可以停電梯，而且第i層樓（1=i=N）上有一個數(shù)字Ki（0=Ki=N）。電梯只有四個按鈕：開，關，上，下。上下的層數(shù)等于當前樓層上的那個數(shù)字。當然，如果不能滿足要求，相應的按鈕就會失靈。例如：3 3 1 2 5代表了Ki（K1=3,K2=3,），從一樓開始。在一樓，按“上”可以到4樓，按“下”是不起作用的，因為沒有-2樓。那么，從A樓到B樓至少要按幾次按鈕呢？【輸入格式】lift.in輸入文件共有二行，第一行為三個用空格隔開的正整數(shù)，表示N,A,B(1N200, 1A,BN)，第二行為N個用空格隔開的正整數(shù)，表示Ki?！据敵龈袷健縧ift.out輸出文件僅一行，即最少按鍵次數(shù)