佇列(Queue)簡介

佇列(Queue)結構是一個有序串列(Order List)，所有的加入與刪除發生在串列的不同端，加入的稱為尾端(Rear)，刪除的一端稱為前端(Front)，並具有先進先出(First In First Out，FIFO)的特色，像各位在排隊買火車票時，先到的有先買票的權利，這就是一種佇列所採取的方式。

除了一般的佇列外，為了特殊狀況會有下列兩種常用佇列的變形：

1.雙向佇列(Double-Ended Queue，Deque)為一有序串列，加入與刪除可在任何一端進行，具體說，雙向佇列就是允許兩端中的任何一端都具備有刪除或加入的功能。

2.優先佇列(Priority Queue)；不以優先順序進出，而是以每一個元素所賦予的優先權進出，例如：在大型電腦的CPU工作排程中，常會用到優先佇列，也就是像層級越高的管理者，就有較一般員工較先享有CPU的權利。

佇列的定義:

因為佇列具有先進先出(FIFO:FIRST IN,FIRST OUT)的特性，因此所有的刪除或加入的動作必須在不同的兩端進行。和堆疊相同的，我們也可以用陣列或指標來建立一個佇列。不過堆疊只需一個top，指標指向堆疊頂，而佇列就必須使用front和rear二個指標分別指向前端和尾端。一般說來有關佇列的5種基本運算的工作定義(operation definition)，可以簡單敘述如下：
(1)建立空佇列Q。
(2)將新資料加入Q的尾端，傳回新佇列。
(3)刪除佇列前端的資料，傳回新佇列。
(4)傳回佇列前端的值。
(5)若佇列為空集合，傳回真，否則傳回偽。

Que  整數陣列，存資料用。 Front  前端指標。 Rear  後端指標。 Front  指標的值較佇列前端少１。 Rear  指標指向佇列最後一個元素 起始為Front=Rear=0，表示開始無元素。

Sub InQuere (Dat,Que(),Rear,Full)       If Rear = Max Then　　　　　　　　　　'判斷佇列是否已滿            Full=1　　　　　　　　　　　　　　 '若滿則將Full設為1，表示佇列已滿        Else           Rear = Rear + 1　　　　　　　　　　   '若未滿，則將佇列後端指標加1。            Que(Rear) = Dat　　　　　　　　　　  '將要加入之元素存入佇列中            Full = 0　　　　　　　　　　　　　    '將Full設為0表佇列未滿。        End If   End Sub

Sub OutQuere (Dat,Que(),Front,Rear,Empty)       If Front = Rear Then　　　　　　　　　　'判斷佇列是否為空的            Empty = 1　　　　　　　　　　　　    '若空佇列將Empty設為1，表示佇列已滿        Else           Dat = Que(Front)　　　　　　　　　　 '若發空佇列，將前端要刪除元素存入Dat           Front = Front + 1　　　　　　　　　　  '將佇列前端指標加1           Empty = 0　　　　　　　　　　　　　'將Empty設為0表並非空佇列。       End If   End Sub

佇列的應用:


佇列結構在電腦上的應用也相當廣泛，例如：
(1)一般在CPU的工作排程，會採用佇列，也就是先到先做的方式。

(2)作為輸出入工作緩衝區；例如spooling，是先將輸入資料寫在磁碟上，再輸入電腦處理，處理後的資料先寫出磁碟上，再出印表機印出。

(3)用於電腦模擬(computer simulation)方面，在模擬中經常有時間導向(time-driven)或事件導向(event-driven)的輸入訊號，由於訊號到達的時間不一定，也是用佇列來安排。

原文出處: http://content.edu.tw/senior/computer/ks_ks/et/datastruct/qu/queue.htm