程式設計概念：佇列

佇列是一種在計算中廣泛使用的先進先出 (FIFO) 抽象資料型別。佇列的用途包括任何需要按照呼叫順序執行的操作，但計算機無法跟上速度。例如

• 鍵盤緩衝區 - 您希望字母按照您按下的順序顯示在螢幕上。您可能會注意到，當您的計算機很忙時，您按下的鍵不會立即顯示在螢幕上，而要稍等片刻。當它們顯示出來時，它們會按照您按下的順序顯示。
• 印表機佇列 - 您希望列印作業按照您傳送的順序完成，即第 1 頁、第 2 頁、第 3 頁、第 4 頁等。當您共享印表機時，幾個人可能會向列印機發送列印作業，而印表機無法立即列印，因此您需要等待一段時間，但輸出的專案將按照您傳送的順序進行。

有幾種不同型別的佇列，如下所述

線性

在這種佇列形式中，元素能夠在一端加入佇列，並在另一端退出佇列。先進先出 (FIFO)。

線性 FIFO 佇列的表示

現實生活中的例子是在超市排隊結賬。第一個進入佇列的人是第一個被服務的人。如果你最後一個加入佇列，你將是最後一個被服務的人（不要插隊！）。然而，有一個區別，在超市佇列中，一旦第一個被服務，其餘的佇列就會向前移動，使之前第二個人現在成為第一個，這在計算機中是可能的，但在處理方面非常昂貴。您將看到的線性佇列會“爬”過記憶體，吞噬它遇到的所有東西。

線性佇列的最基本實現將遍歷其分配的記憶體，而不會重用記憶體。前端和後端指標只能向前移動，遲早會到達分配記憶體的末尾 - 在這一點上，無法再向佇列新增更多專案。看看這個例子以及儲存佇列前端的兩個指標（FrontPtr）和下一個空閒記憶體位置（NextFree）的值。

狀態 1	狀態 2	狀態 3	狀態 4	狀態 5	狀態 6
起始狀態	H 加入佇列	開始被服務	J 加入佇列	開始被服務	P 加入佇列
1 2 3 4 5 D G A FrontPtr = 1 NextFree = 4	1 2 3 4 5 D G A H FrontPtr = 1 NextFree = 5	1 2 3 4 5 D G A H FrontPtr = 2 NextFree = 5 Output = D 注意沒有資料被 '刪除'，但 指標已更改	1 2 3 4 5 D G A H J FrontPtr = 2 NextFree = 6	1 2 3 4 5 D G A H J FrontPtr = 3 NextFree = 6 Output = G	1 2 3 4 5 6 D G A H J P FrontPtr = 3 NextFree = 7 即使 3 之前的插槽 不再需要，但 無法新增更多資料，因為 NextFree 已超過 最後一個插槽

一個更好的實現將透過每次從前端刪除一個專案時將每個專案向左移動一個來重用記憶體。但是，如果佇列中有許多專案，這可能會變得非常慢。見下文（注意我們不再需要前端指標，因為專案 1 始終是前端）

狀態 1	狀態 2	狀態 3	狀態 4	狀態 5	狀態 6
起始狀態	H 加入佇列	開始被服務	J 加入佇列	開始被服務	P 加入佇列
1 2 3 4 5 D G A NextFree = 4	1 2 3 4 5 D G A H NextFree = 5	1 2 3 4 5 G A H NextFree = 4 Output = D D 被刪除，其他 專案被移動 到左邊	1 2 3 4 5 G A H J NextFree = 5	1 2 3 4 5 A H J NextFree = 4 Output = G	1 2 3 4 5 A H J P NextFree = 5

易於實現，程式碼簡單

然而

從佇列前端刪除專案可能會很慢

迴圈

與線性佇列不同，迴圈佇列允許重用記憶體

通常，迴圈緩衝區需要三個 指標

• 一個指向記憶體中的實際緩衝區
• 一個指向有效資料的開始
• 一個指向有效資料的結束

以下示例顯示了一個部分填充的固定長度緩衝區，以及它如何處理佇列的新增和刪除操作。特別注意指標。

圖表	StartPtr	EndPtr
	3	5
資料被指定為位於 StartPtr 和 EndPtr 之間
	3	6
向佇列新增另一個元素會將 EndPtr 向上移動一個
	4	6
從佇列前端刪除一個元素是透過將 StartPtr 增加一個來實現的
	4	7
向佇列新增另一個元素會將 EndPtr 向上移動一個，它現在位於緩衝區的末尾
	4	1
向佇列新增另一個元素會導致 EndPtr 迴圈回到緩衝區開頭的空閒空間
	4	2
向佇列新增另一個元素會將 EndPtr 向上移動一個，它現在正接近 StartPtr
	4	3
向佇列新增另一個元素會將 EndPtr 向上移動一個，它現在正接近 StartPtr。 如果我們嘗試向迴圈佇列新增另一個元素，我們無法在不首先從佇列前端刪除內容的情況下進行新增

迴圈佇列在計算機科學中非常常見，它們被用於儲存內容，它們具有以下優點

它們重用記憶體空間，這意味著它們不會覆蓋資料或耗盡記憶體（在一定範圍內）

以及缺點

除了資料之外，還包括儲存指標，比線性佇列佔用更多空間

受緩衝區（陣列）中可用資料量的限制

優先順序

它基於佇列中元素的優先順序順序。換句話說，這種型別的佇列的每個元素都附加了不同的優先順序級別；例如，高優先順序或低優先順序。

急診室是優先順序佇列的一個例子

現實世界中的例子是急診室的候診室，摔倒的人可能比頭部割傷的人優先順序低，因此即使頭部受傷的病人後來進來，他們也可能插隊。

狀態 1	狀態 2	狀態 3
1. 胳膊骨折 2. 膝蓋擦傷	1. 心臟病發作 2. 胳膊骨折 3. 膝蓋擦傷	1. 心臟病發作 2. 重度腦震盪 3. 胳膊骨折 4. 膝蓋擦傷
初始佇列	心臟病發作最優先插隊	重度腦震盪不如心臟病發作重要，所以移到第二位

在計算機中，我們使用優先順序佇列來處理程序的執行。每個程序將具有一個與其關聯的優先順序，當更重要的程序需要處理器時，它們會跳過不太重要的程序以獲得處理器的關注。例如

流程	優先順序
網頁瀏覽器	正常
媒體播放器	低於正常
作業系統安全	高
計劃的病毒掃描程式	低
印表機佇列	低
文字處理器	正常

擴充套件排程演算法 有幾種方法可以用來處理處理器排程，每種方法都有自己的優缺點 排程演算法 CPU 利用率 吞吐量 週轉時間 響應時間 先進先出 低 低 高 低 最短作業優先 中等 高 中等 中等 基於優先順序的排程 中等 低 高 高 迴圈排程 高 中等 中等 高 多級佇列排程 高 高 中等 中等

練習：佇列 為什麼你會選擇迴圈佇列而不是線性佇列？ 答案 迴圈佇列使用固定數量的記憶體，並在遍歷佇列時重用記憶體。線性佇列不會重用記憶體，可能會浪費記憶體。 說出實現迴圈佇列中使用的三個指標 答案 一個指向記憶體中的實際緩衝區 一個指向有效資料的開始（StartPtr） 一個指向有效資料的結束（EndPtr） 當一個更高優先順序的任務需要處理器的關注時，優先順序佇列中會發生什麼？ 答案 低優先順序任務被排隊，高優先順序任務被賦予處理器的關注 當 Monkey 和 Snake 被新增，第一個專案被刪除，然後 Bear 被新增到以下佇列中時，指標的值將是什麼 1 2 3 4 5 獾 雪貂 黃鼠狼 如果它是迴圈佇列？ 答案 1 2 3 4 5 熊 雪貂 黃鼠狼 猴子 蛇 StartPtr = 2 EndPtr = 1 如果它是線性佇列？ 答案 這將失敗，因為佇列中沒有更多空間了！ 描述佇列的功能 答案 先進先出資料型別 說出在計算機中使用佇列的兩個用途。 答案 鍵盤緩衝區 印表機佇列