數(shù)據(jù)結(jié)構(gòu)第6課隊(duì)列

隊(duì)列數(shù)據(jù)結(jié)構(gòu)之三1

隊(duì)列的基本概念隊(duì)列(Queue)：也是運(yùn)算受限的線性表。只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。

隊(duì)首(front)

：允許進(jìn)行刪除的一端稱為隊(duì)首。

隊(duì)尾(rear)

：允許進(jìn)行插入的一端稱為隊(duì)尾。

例如：排隊(duì)購(gòu)物，先進(jìn)入隊(duì)列的成員總是先離開隊(duì)列。

6.1

隊(duì)列基本概念先進(jìn)先出a1,a2,…,an出隊(duì)入隊(duì)隊(duì)尾隊(duì)首6.2隊(duì)列的順序表示和實(shí)現(xiàn)

利用一維數(shù)組依次存放從隊(duì)首到隊(duì)尾的各個(gè)元素，稱為順序隊(duì)列。其類型定義如下：#defineMAX100structqueue{intqueue_a[MAX];intfront;intrear;};6.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

設(shè)立一個(gè)隊(duì)首指針front，一個(gè)隊(duì)尾指針rear?！舫跏蓟篺ront=rear=0?！羧腙?duì)：將新元素插入rear所指的位置，然后rear加1◆出隊(duì)：返回被刪元素，然后刪去front所指的元素，front加1?！絷?duì)列為空：front=rear。◆隊(duì)滿：rear=MAX或front=rear。(a)空隊(duì)列Q.frontQ.rear入隊(duì)3個(gè)元素a3a2a1Q.frontQ.rear(c)出隊(duì)3個(gè)元素Q.frontQ.rear(d)入隊(duì)2個(gè)元素a5a4Q.frontQ.rear圖3-6隊(duì)列示意圖順序隊(duì)列中存在“假溢出”現(xiàn)象。因?yàn)樵谌腙?duì)和出隊(duì)操作中，頭、尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無法重新利用。6.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

設(shè)q[0,6]是一個(gè)靜態(tài)順序隊(duì)列，初始狀態(tài)為front=rear=0，請(qǐng)畫出做完下列操作后隊(duì)列的頭尾指針的狀態(tài)變化情況，若不能入隊(duì)，請(qǐng)指出其元素，并說明理由。a,b,c,d入隊(duì)a,b,c出隊(duì)i,j,k,l,m入隊(duì)d,i出隊(duì)n,o,p,q,r入隊(duì)習(xí)題一6.3循環(huán)隊(duì)列為充分利用向量空間，克服上述“假溢出”現(xiàn)象的方法是：將為隊(duì)列分配的空間看成為一個(gè)首尾相接的圓環(huán)，并稱這種隊(duì)列為循環(huán)隊(duì)列(CircularQueue)。

在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，隊(duì)首、隊(duì)尾指針仍要加1，朝前移動(dòng)。只不過當(dāng)隊(duì)首、隊(duì)尾指針指向上界(MAX-1)時(shí)，其加1操作的結(jié)果是指向下界0。這種加1操作可以描述為：if(i+1==MAX)i=0;elsei++;//其中：i代表隊(duì)首指針(front)或隊(duì)尾指針(rear)用取余運(yùn)算可簡(jiǎn)化為：i=(i+1)%MAX;例：設(shè)有循環(huán)隊(duì)列qu[0，5]，其初始狀態(tài)是front=rear=0，各種操作后隊(duì)列的頭、尾指針的狀態(tài)變化情況如下圖所示。6.3循環(huán)隊(duì)列123450(a)空隊(duì)列frontrear123450(b)d,e,b,g入隊(duì)frontdebgrear123450(c)d,e出隊(duì)bgfrontrear123450(d)i,j,k入隊(duì)bgfrontijkrear123450(e)b,g出隊(duì)ijkrearfront123450(f)r,p,s,t入隊(duì)ijkfrontrprear

循環(huán)隊(duì)列操作及指針變化情況6.3循環(huán)隊(duì)列入隊(duì)時(shí)尾指針向前追趕頭指針出隊(duì)時(shí)頭指針向前追趕尾指針故隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此，無法通過front=rear來判斷隊(duì)列“空”還是“滿”。解決的方法是：約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿。即：rear所指的單元始終為空（浪費(fèi)一個(gè)空間）。6.3循環(huán)隊(duì)列循環(huán)隊(duì)列為空：front=rear

循環(huán)隊(duì)列滿：(rear+1)%MAX

=front假設(shè)q[0,5]是一個(gè)循環(huán)隊(duì)列，初始狀態(tài)為front=rear=0，請(qǐng)畫出做完下列操作后隊(duì)列的頭尾指針的狀態(tài)變化情況，若不能入隊(duì)，請(qǐng)指出其元素，并說明理由。d,e,b,g,h入隊(duì)d,e出隊(duì)i,j,k,l,m入隊(duì)b出隊(duì)n,o,p,q,r入隊(duì)習(xí)題二循環(huán)隊(duì)列的基本操作1循環(huán)隊(duì)列的初始化queueinit_CirQueue(void){queueq;q.front=q.rear=0;return(q);}

2入隊(duì)操作intinsert_CirQueue(queueq,inte)/*將數(shù)據(jù)元素e插入到循環(huán)隊(duì)列Q的隊(duì)尾*/{if((q.rear+1)%MAX==q.front)returnERROR;/*隊(duì)滿，返回錯(cuò)誤標(biāo)志*/q.qa[q.rear]=e;//元素e入隊(duì)q.rear=(q.rear+1)%MAX;//隊(duì)尾指針向前移動(dòng)returnOK;/*入隊(duì)成功*/}循環(huán)隊(duì)列的基本操作

3出隊(duì)操作intdelete_CirQueue(queueq,int*x

)//將循環(huán)隊(duì)列Q的隊(duì)首元素出隊(duì){if(q.front+1==q.rear)returnERROR;//隊(duì)空，返回錯(cuò)誤標(biāo)志*x=q.qa[q.front];//取隊(duì)首元素q.front=(q.front+1)%MAX;//隊(duì)首指針向前移動(dòng)returnOK;}循環(huán)隊(duì)列的基本操作1隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列。

需要兩類不同的結(jié)點(diǎn)：數(shù)據(jù)元素結(jié)點(diǎn)，隊(duì)列的隊(duì)首指針和隊(duì)尾指針的結(jié)點(diǎn)。6.4

隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)數(shù)據(jù)元素結(jié)點(diǎn)定義：structqnode{intdata;qnode*next;};數(shù)據(jù)元素結(jié)點(diǎn)data指針結(jié)點(diǎn)front

rear指針結(jié)點(diǎn)類型定義：structlink_queue{qnode*front,*rear;};2鏈隊(duì)運(yùn)算及指針變化

鏈隊(duì)的操作實(shí)際上是單鏈表的操作，只不過是刪除在表頭進(jìn)行，插入在表尾進(jìn)行。鏈隊(duì)運(yùn)算及指針變化如圖3-9所示。(a)空隊(duì)列front

rear∧(b)x入隊(duì)

x∧front

rear隊(duì)列操作及指針變化(c)y再入隊(duì)

y∧front

rear

x(d)x出隊(duì)

y∧

xfront

rear

3鏈隊(duì)列的基本操作⑴

鏈隊(duì)列的初始化link_queue*init_linkqueue(void){link_queue*q;qnode*p;p=newqnode;/*開辟頭結(jié)點(diǎn)*/p->next=NULL;q=newlink_queue;/*開辟鏈隊(duì)的指針結(jié)點(diǎn)*/q.front=q.rear=p;return(q);}

⑵

鏈隊(duì)列的入隊(duì)操作

在已知隊(duì)列的隊(duì)尾插入一個(gè)元素e，即修改隊(duì)尾指針(q.rear)。intinsert_CirQueue(link_queue*q,inte)/*將數(shù)據(jù)元素e插入到鏈隊(duì)列q的隊(duì)尾*/{p=newqnode;if(!p)returnERROR;/*申請(qǐng)新結(jié)點(diǎn)失敗，返回錯(cuò)誤標(biāo)志*/p->data=e;p->next=NULL;/*形成新結(jié)點(diǎn)*/q.rear->next=p;q.rear=p;/*新結(jié)點(diǎn)插入到隊(duì)尾*/returnOK;}

⑶鏈隊(duì)列的出隊(duì)操作intdelete_queue(link_queue*q,int*x)

{qnode*p;if(q.front==q.rear)returnERROR;/*隊(duì)空*/p=q.front->next;/*取隊(duì)首結(jié)點(diǎn)*/*x=p->data;q.front->next=p->next;/*修改隊(duì)首指針*/if(p==q.rear)q.rear=q.front;

/*當(dāng)隊(duì)列只有一個(gè)結(jié)點(diǎn)時(shí)應(yīng)防止丟失隊(duì)尾指針*/

deletep;returnOK;}

⑷

鏈隊(duì)列的撤消voiddestroy_linkqueue(link_queue*q)

/*將鏈隊(duì)列Q的隊(duì)首元素出隊(duì)*/{while(q.front!=NULL){q.rear=q.front->next;/*令尾指針指向隊(duì)列的第一個(gè)結(jié)點(diǎn)*/deleteq.front;

/*每次釋放一個(gè)結(jié)點(diǎn)*//*第一次是頭結(jié)點(diǎn)，以后是元素結(jié)點(diǎn)*/q.front=q.rear;}}在現(xiàn)實(shí)生活中Queue的應(yīng)用很廣泛。1、播放器上的播放列表2、數(shù)據(jù)流對(duì)象，異步的數(shù)據(jù)傳輸結(jié)構(gòu)(文件IO，管道通訊，套接字等)3、還有一些解決對(duì)共享資源的沖突訪問，比如打印機(jī)的打印隊(duì)列等。消息隊(duì)列等。交通狀況模擬，呼叫中心用戶等待的時(shí)間的模擬等等。可以肯定地說：任何與時(shí)間相關(guān)的操作，基本上都會(huì)牽扯到隊(duì)列。隊(duì)列的應(yīng)用舉例隊(duì)列的基本用途保存暫時(shí)不用的數(shù)據(jù)或存儲(chǔ)地址可簡(jiǎn)化程序設(shè)計(jì)例.用隊(duì)列進(jìn)行迷宮求解用隊(duì)列進(jìn)行迷宮求解的基本思想是：從迷宮的入口[1][1]出發(fā)，向四周搜索，記下所有一步能到達(dá)的坐標(biāo)點(diǎn)；然后依次從每一點(diǎn)出發(fā)，向四周搜索，記下所有從入口點(diǎn)出發(fā)，經(jīng)過兩步可以到達(dá)的坐標(biāo)點(diǎn)……依次進(jìn)行下去，一直到達(dá)迷宮的出口處[4][4]。然后從出口處沿搜索路徑回溯直到入口點(diǎn)，這樣就找到了從入口到出口的一條最短路徑。

01100000101011100110000010101010474101-11115492548354744262335332432122112序號(hào)行列前驅(qū)由于先到達(dá)的點(diǎn)要先向下搜索，故引進(jìn)一個(gè)“先進(jìn)先出”數(shù)據(jù)結(jié)構(gòu)——隊(duì)列來保存已到達(dá)的點(diǎn)的坐標(biāo)。到達(dá)迷宮的出口點(diǎn)(4,4)后，為了能夠從出口點(diǎn)沿搜索路徑回溯直至入口，對(duì)于每一點(diǎn)，在記下點(diǎn)的坐標(biāo)的同時(shí)，還要記下到達(dá)該點(diǎn)的前驅(qū)點(diǎn)?！纠科嚰佑驼?/p>

隨著城市里汽車數(shù)量的急速增長(zhǎng)，汽車加油站也漸漸多了起來。通常汽車加油站的結(jié)構(gòu)基本上是：入口和出口為單行道，加油車道可能有若干條。每輛車加油都要經(jīng)過三段路程，第一段是在入口處排隊(duì)等候進(jìn)入加油車道；第二段是在加油車道排隊(duì)等候加油；第三段是進(jìn)入出口處排隊(duì)等候離開。實(shí)際上，這三段都是隊(duì)列結(jié)構(gòu)。若用算法模擬這個(gè)過程，就需要設(shè)置加油車道數(shù)加2個(gè)隊(duì)列。隊(duì)列的應(yīng)用【例】模擬打印機(jī)緩沖區(qū)

在主機(jī)將數(shù)據(jù)輸出到打印機(jī)時(shí)，會(huì)出現(xiàn)主機(jī)速度與打印機(jī)的打印速度不匹配的問題。這時(shí)主機(jī)就要停下來等待打印機(jī)。顯然，這樣會(huì)降低主機(jī)的使用效率。為此人們?cè)O(shè)想了一種辦法：為打印機(jī)設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，當(dāng)主機(jī)需要打印數(shù)據(jù)時(shí)，先將數(shù)據(jù)依次寫入這個(gè)緩沖區(qū)，寫滿后主機(jī)轉(zhuǎn)去做其他的事情，而打印機(jī)就從緩沖區(qū)中按照先進(jìn)先出的原則依次讀取數(shù)據(jù)并打印，這樣做即保證了打印數(shù)據(jù)的正確性，又提高了主機(jī)的使用效率。由此可見，打印機(jī)緩沖區(qū)實(shí)際上就是一個(gè)隊(duì)列結(jié)構(gòu)。

【例】CPU分時(shí)系統(tǒng)

在一個(gè)帶有多個(gè)終端的計(jì)算機(jī)系統(tǒng)中，同時(shí)有多個(gè)用戶需要使用CPU運(yùn)行各自的應(yīng)用程序，它們分別通過各自的終端向操作系