隊(duì)列及其應(yīng)用

1、隊(duì)列n隊(duì)列的邏輯特征及抽象數(shù)據(jù)類型n隊(duì)列的順序表示和實(shí)現(xiàn)n隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)隊(duì)列的基本概念隊(duì)列的基本概念隊(duì)列基本操作：隊(duì)列基本操作：（1）初始化 init()（2）是否為空 empty()（3）是否滿 full() （4）入隊(duì) inqueue()（5）出隊(duì) delqueue()（6）取隊(duì)頭元素 gethead()（7）隊(duì)列長度 lenqueue()隊(duì)列的順序存儲(chǔ)方式（1）順序存儲(chǔ)：用數(shù)組表示，front和rear分別表示隊(duì)頭元素和隊(duì)尾元素； 約定：front指向隊(duì)頭元素在隊(duì)列中的前一個(gè)位置，rear指向隊(duì)尾元素在隊(duì)列中的當(dāng)前位置。const qmaxsize=.;type qelement=

2、數(shù)據(jù)類型； queue=recorddata:array1.qmaxsizeof qelement;front,rear:0.qmaxsize; end;var q:queue;frontrear11順序存儲(chǔ)隊(duì)列的基本操作(1)初始化 init() procedure init(var q:queue); beginq.front:=0;q.rear:=0; end;(2)是否為空 empty() function empty(var q:queue); beginempty:=(q.front=q.rear); end;(3)是否滿 full() function full(var q:qu

3、eue); beginfull:=(q.rear=qmaxsize); end;順序存儲(chǔ)隊(duì)列的基本操作(4)入隊(duì) inqueue(); procedure inqueue(var q:queue;x:qelement); beginif full(q) then writeln(FULL) else begin inc(q.rear);q.dataq.rear:=x; end;(5)出隊(duì) delqueue() procedure delqueue(var q:queue;x:qelement); beginif empty(q) then writeln(EMPTY)else begininc

4、(q.front);x:=q.dataq.front;end;(6)隊(duì)頭元素:m:=q.front+1;gethead:=q.datam(7)隊(duì)列長度：lenqueue:=q.rear-q.front順序隊(duì)列的順序隊(duì)列的“ 假溢出假溢出” 問題問題順序隊(duì)列的“ 假溢出” 問題采用循環(huán)隊(duì)列采用循環(huán)隊(duì)列如何解決順序隊(duì)列的假溢出問題？順序循環(huán)隊(duì)列的表示順序循環(huán)隊(duì)列的表示順序循環(huán)隊(duì)列的表示隊(duì)空和隊(duì)滿判斷問題解決方案有三：使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長度）；判隊(duì)滿：(count0) and (rear=front)判隊(duì)空：count=0加設(shè)標(biāo)志位，出隊(duì)時(shí)置,入隊(duì)時(shí)置,則可識(shí)別當(dāng)前front=

5、rear 屬于何種情況判隊(duì)滿：(tag=1) and (rear=front)判隊(duì)空：(tag=0) and (rear=front)少用一個(gè)存儲(chǔ)單元判隊(duì)滿：front= (rear+1) mod MaxQueueSize判隊(duì)空：rear=front方案三空隊(duì)列和滿隊(duì)列順序循環(huán)隊(duì)列存儲(chǔ)方式解決“假溢出”現(xiàn)象，q1接在qm之后，形成循環(huán)表，當(dāng)刪除a1之后插入am+1時(shí)，不移動(dòng)隊(duì)列中現(xiàn)有元素，直接把它加到q1位置上去。實(shí)際上就形成了一個(gè)環(huán)，這種隊(duì)列稱為循環(huán)隊(duì)列循環(huán)隊(duì)列。約定約定：損失一個(gè)元素空間。當(dāng)front=rear時(shí)定義為空；當(dāng)rear從后面追上front時(shí)，作為隊(duì)滿標(biāo)志：rear+1=fro

6、nt032415032415032415032415front=rear=0空隊(duì)列a1a2a3a4a5front=0rear=5a1.a5入隊(duì),隊(duì)滿front=3rear=5a1.a3出隊(duì)a4a5a4a5a6a7a8rear=2front=3a6.a8入隊(duì)，隊(duì)滿入隊(duì):rear:=(rear+1) mod max出隊(duì):front:=(front+1) mod max循環(huán)隊(duì)列存儲(chǔ)const maxsize=.;type qelement=數(shù)據(jù)類型; queue=recorddata=array0.maxsize-1of qelement;front，rear:0.maxsize-1; end;va

7、r q:queue;循環(huán)隊(duì)列基本操作(1)初始化 init()procedure init(var q:queue);beginq.front:=0; q.rear:=0;end;(2)是否為空 empty()function empty(var q:queue):boolean;begin empty:=(q.front=q.rear);end;(3)是否溢出 full()function full(var q:queue):boolean;beginfull:=(q.(rear+1) mod maxsize=q.front);end;循環(huán)隊(duì)列基本操作(4)入隊(duì) inqueue(var q:

8、queue; x:qelement);procedure inqueue(var q:queue;x:qelement);beginif full(q) then writeln(FULL)else begin q.rear:=(q.rear+1)mod maxsize; q.dataq.rear:=x;end;(5)出隊(duì) delqueue(var q:queue; x:qelement);procedure delqueue(var q:queue; x:qelement);beginif empty(q) then writeln(EMPTY)else begin q.front:=(q.

9、front+1）mod maxsize; x:=q.dataq.front;end;循環(huán)隊(duì)列基本操作(6)隊(duì)頭元素 gethead(var q:queue):qelement; m:=(q.front+1)mod maxsize; gethead:=q.datam;(7)隊(duì)列長度lenqueue(var q:queue):integer; lenqueue:=(q.rear-q.front+maxsize) mod maxsize;隊(duì)列鏈接存儲(chǔ)方式(2)鏈接存儲(chǔ)：用一個(gè)單鏈表來實(shí)現(xiàn)。為了便于表示空隊(duì)列，使用一個(gè)表頭單元，將隊(duì)頭指針指向表頭單元。type queueptr=queuenode;

10、queuenode=recorddata:elemtp; next:queueptr; end;linkedquetp=recordfront,rear:queueptr;end;q.frontq.rear.鏈接存儲(chǔ)隊(duì)列的基本操作(1)入隊(duì) inqueue(var q:linkedquetp;x:elemtp); procedure inqueue(var q:linkedquetp;x:elemtp); beginnew(q.rear.next);q.rear:=q.rear.next;q.rear.data:=x;q.rear.next:=nil; end;(2)出隊(duì) delqueue(v

11、ar q:linkedquetp;x:elemtp); procedure delqueue(var q:linkedquetp;x:elemtp); beginif empty(q) then writeln(EMPTY)else begin p:=q.front; q.front:=q.front.next; dispose(p);end鏈接存儲(chǔ)隊(duì)列的基本操作(3)置空隊(duì)列 clear(q) procedure clear(var q:linkedquetp); beginq.rear:=q.front;while q.frontnil do begin q.front:=q.front.

12、next; dispose(q.rear); q.rear:=q.front; end;new(q.front);q.front.next:=nil;q.rear:=q.front; end;隊(duì)列應(yīng)用舞伴問題 假設(shè)在周末舞會(huì)上，男士們和女士們進(jìn)入舞廳時(shí)，各自排成一隊(duì)。假設(shè)在周末舞會(huì)上，男士們和女士們進(jìn)入舞廳時(shí)，各自排成一隊(duì)。跳舞開始時(shí)，依次從男隊(duì)和女隊(duì)的隊(duì)頭上各出一人配成舞伴。若兩隊(duì)跳舞開始時(shí)，依次從男隊(duì)和女隊(duì)的隊(duì)頭上各出一人配成舞伴。若兩隊(duì)初始人數(shù)不相同，則較長的那一隊(duì)中未配對者等待下一輪舞曲?，F(xiàn)要初始人數(shù)不相同，則較長的那一隊(duì)中未配對者等待下一輪舞曲。現(xiàn)要求寫一算法模擬上述舞伴配對問題。求

13、寫一算法模擬上述舞伴配對問題。分析： 先入隊(duì)的男士或女士亦先出隊(duì)配成舞伴。因此該問題具體有典型的先進(jìn)先出特性，可用隊(duì)列作為算法的數(shù)據(jù)結(jié)構(gòu)。在算法中，假設(shè)男士和女士的記錄存放在一個(gè)數(shù)組中作為輸入，然后依次掃描該數(shù)組的各元素，并根據(jù)性別來決定是進(jìn)入男隊(duì)還是女隊(duì)。當(dāng)這兩個(gè)隊(duì)列構(gòu)造完成之后，依次將兩隊(duì)當(dāng)前的隊(duì)頭元素出隊(duì)來配成舞伴，直至某隊(duì)列變空為止。此時(shí)，若某隊(duì)仍有等待配對者，算法輸出此隊(duì)列中等待者的人數(shù)及排在隊(duì)頭的等待者的名字，他（或她）將是下一輪舞曲開始時(shí)第一個(gè)可獲得舞伴的人。具體參考程序代碼program dancers;var dancer_name:array1.100 of string;

14、 /姓名 dancer_sex:array1.100 of char; /性別，F(xiàn)表示女性，M表示男性 F_dancer:array 1.100 of integer; F_front,F_rear:integer; /女士隊(duì)列 M_dancer:array1.100 of integer; M_front,M_rear:integer; /男士隊(duì)列 num,i,count:integer;begin F_front:=0; F_rear:=0; M_front:=0; M_rear:=0; write(請輸入?yún)⒓犹璧娜藬?shù)：); readln(num); writeln(依次輸入跳舞者的性別

15、、姓名：); for i:=1 to num do begin write(i,:); readln(dancer_sexi,dancer_namei); /輸入性別，姓名 end; for i:=1 to num do /依次將跳舞者依其性別入隊(duì),只記錄跳舞者數(shù)組的下標(biāo) begin if(dancer_sexi=F) then begin inc(F_rear); F_dancerF_rear:=i; /排入女隊(duì) end else begin inc(M_rear); M_dancerM_rear:=i; /排入男隊(duì) end; end; writeln(跳舞舞伴： ); while(F_fr

16、ontF_rear) and (M_frontM_rear) do begin /依次輸出男女舞伴名 inc(F_front); /女士出隊(duì) write(dancer_nameF_dancerF_front, );/打印出隊(duì)女士名 inc(M_front); /男士出隊(duì) writeln(dancer_nameM_dancerM_front); /打印出隊(duì)男士名 end; if (F_frontF_rear) then begin /輸出女士剩余人數(shù)及隊(duì)頭女士的名字 count:=F_rear-F_front; writeln(還有,count,位女士等待下一舞曲。); writeln( dan

17、cer_nameF_dancerF_front+1,將第一個(gè)獲得舞伴); /取女隊(duì)隊(duì)頭 end else begin if (M_front M_rear) then begin /輸出男隊(duì)剩余人數(shù)及隊(duì)頭者名字 count:=M_rear-M_front; writeln(還有,count, 位男士等待下一舞曲。); writeln(dancer_nameM_dancerM_front+1,將第一個(gè)獲得舞伴。);/取男隊(duì)隊(duì)頭 end; end; end.凱撒加密(Caesar cipher)【問題描述】凱撒加密(Caesar cipher)是一種簡單的消息編碼方式：它根據(jù)字母表將消息中的每個(gè)字

18、母移動(dòng)常量位k。舉個(gè)例子如果k等于3，則在編碼后的消息中，每個(gè)字母都會(huì)向后移動(dòng)3位：a會(huì)被替換為d；b會(huì)被替換成e；依此類推。字母表末尾將回卷到字母表開頭。于是，w會(huì)被替換為z，x會(huì)被替換為a。在解碼消息的時(shí)候，每個(gè)字母會(huì)反方向移動(dòng)同樣的位數(shù)。因此，如果k等于3，下面這條編碼后的消息：vlpsolflwb iroorzv frpsohalwb會(huì)被解碼成：simplicity follows complexity朱麗葉斯.凱撒在他的一些機(jī)密政府通信中真正用到了這種加密。遺憾的是，凱撒加密相當(dāng)容易被破解。字母的移動(dòng)只有26種可能；要破解密碼，只需嘗試各種密鑰值，直到有一種可行即可。隊(duì)列應(yīng)用使用重復(fù)

19、密鑰(repeating key)可以對這種編碼技術(shù)做出改進(jìn)，這時(shí)不再將每個(gè)字母移動(dòng)常位數(shù)，而是利用一列密鑰值將各個(gè)字母移動(dòng)不同的位數(shù)。如果消息長于這列密鑰值，可以從頭再次使用這列密鑰。例如，假設(shè)密鑰值為：3 1 7 4 2 5則第1個(gè)字母會(huì)移動(dòng)3位，第2個(gè)字母會(huì)移動(dòng)1位，依此類推，將第6個(gè)字母移動(dòng)5位之后，我們會(huì)從頭再次使用這列密鑰。于是第7個(gè)字母會(huì)移動(dòng)3位，第8個(gè)字母會(huì)移動(dòng)1位。反之解碼的過程類似。注意：加密與解密都是針對字母（大小寫均可）進(jìn)行。樣例：明文：this is a test! 密鑰：2112 密文：viju kt b vgtu【算法分析】【算法分析】我們都知道隊(duì)列的特點(diǎn)是我們都

20、知道隊(duì)列的特點(diǎn)是FIFO(先進(jìn)先出先進(jìn)先出)，將密鑰存儲(chǔ)在隊(duì)列中，將密鑰存儲(chǔ)在隊(duì)列中，使用了一個(gè)密鑰后，將這個(gè)密鑰添加到隊(duì)尾，這樣較長的信息可以重復(fù)使用了一個(gè)密鑰后，將這個(gè)密鑰添加到隊(duì)尾，這樣較長的信息可以重復(fù)使用該密鑰。使用該密鑰。隊(duì)列應(yīng)用用隊(duì)列實(shí)現(xiàn)圖的寬度優(yōu)先搜索算法 我們要對圖進(jìn)行分層次遍歷,遍歷的序列為1，2，7，寬度有先搜索算法遍歷序列圖寬度有先搜索算法遍歷序列圖分析 n 要對圖進(jìn)行按層次遍歷，我們可采用逐層標(biāo)號(hào)法要對圖進(jìn)行按層次遍歷，我們可采用逐層標(biāo)號(hào)法進(jìn)行。方法如下：進(jìn)行。方法如下：n 第一步：將初始點(diǎn)放入隊(duì)列，并將該點(diǎn)設(shè)置為已第一步：將初始點(diǎn)放入隊(duì)列，并將該點(diǎn)設(shè)置為已標(biāo)號(hào)的點(diǎn)。標(biāo)號(hào)的點(diǎn)。n 第二步：從隊(duì)列中