數(shù)據(jù)結(jié)構第6課隊列

隊列數(shù)據(jù)結(jié)構之三1

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

隊首(front)

：允許進行刪除的一端稱為隊首。

隊尾(rear)

：允許進行插入的一端稱為隊尾。

例如：排隊購物，先進入隊列的成員總是先離開隊列。

6.1

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

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

設立一個隊首指針front，一個隊尾指針rear?！舫跏蓟篺ront=rear=0?！羧腙牐簩⑿略夭迦雛ear所指的位置，然后rear加1◆出隊：返回被刪元素，然后刪去front所指的元素，front加1。◆隊列為空：front=rear?！絷牆M：rear=MAX或front=rear。(a)空隊列Q.frontQ.rear入隊3個元素a3a2a1Q.frontQ.rear(c)出隊3個元素Q.frontQ.rear(d)入隊2個元素a5a4Q.frontQ.rear圖3-6隊列示意圖順序隊列中存在“假溢出”現(xiàn)象。因為在入隊和出隊操作中，頭、尾指針只增加不減小，致使被刪除元素的空間永遠無法重新利用。6.2隊列的順序存儲結(jié)構

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

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

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

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

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

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

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

)//將循環(huán)隊列Q的隊首元素出隊{if(q.front+1==q.rear)returnERROR;//隊空，返回錯誤標志*x=q.qa[q.front];//取隊首元素q.front=(q.front+1)%MAX;//隊首指針向前移動returnOK;}循環(huán)隊列的基本操作1隊列的鏈式存儲表示

隊列的鏈式存儲結(jié)構簡稱為鏈隊列。

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

隊列的鏈式表示和實現(xiàn)數(shù)據(jù)元素結(jié)點定義：structqnode{intdata;qnode*next;};數(shù)據(jù)元素結(jié)點data指針結(jié)點front

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

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

rear∧(b)x入隊

x∧front

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

y∧front

rear

x(d)x出隊

y∧

xfront

rear

3鏈隊列的基本操作⑴

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

⑵

鏈隊列的入隊操作

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

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

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

/*當隊列只有一個結(jié)點時應防止丟失隊尾指針*/

deletep;returnOK;}

⑷

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

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

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

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

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

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

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

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