Queues

歡迎來到佇列（Queue）的世界！

在這一章中，我們要探討計算機科學中最貼近生活的資料結構之一：佇列 (Queue)。如果你曾經在排隊買咖啡，或是等候印表機列印你的作業，那麼你已經完全理解佇列是如何運作的了！我們將一起看看電腦如何處理這些資料「隊伍」，讓一切保持井然有序且公平。

1. 什麼是佇列？

佇列是一種抽象資料型別 (Abstract Data Type, ADT)，它遵循先進先出 (First-In, First-Out, FIFO) 的原則。這意味著最先進入佇列的資料，也會最先被移出。想像它就像電影院的排隊隊伍：最早到的人，就是第一個買到票的人。

核心術語：

• 前端 (Front 或 Head)：佇列中移除項目的位置。
• 後端 (Rear 或 Tail)：佇列中加入新項目的位置。

現實生活例子：「列印佇列」。當五個人同時發送文件到印表機時，印表機會先處理第一份收到的文件，然後才處理第二份。這既公平又合乎邏輯！

重點筆記：佇列就是 FIFO。先進者，先出！

2. 靜態與動態佇列

在深入了解不同類型的佇列之前，我們需要先了解它們是如何在電腦記憶體中建立的。別擔心這些名詞聽起來很深奧；它們的區別其實非常簡單！

靜態資料結構 (Static Data Structures)

靜態佇列的大小是固定的，在程式編寫時就已經決定。它通常使用陣列 (Array) 來實作。
• 優點：記憶體是預先分配好的，所以程式在執行時不需要花時間「尋找」額外的記憶體空間。
• 缺點：如果空間用完了，你就不能再加入新項目（這稱為溢位，Overflow）。此外，如果佇列大部分是空的，記憶體空間就會被浪費。

動態資料結構 (Dynamic Data Structures)

動態佇列可以在程式執行時根據需求擴展或縮減大小。它通常使用指標 (Pointers) 來實作。
• 優點：它只使用真正需要的記憶體量。
• 缺點：編寫程式會較為複雜，而且如果整台電腦的 RAM 用盡，可能會導致系統崩潰（堆積溢位，Heap overflow）。

記憶小撇步：Static (靜態) 保持 Same (相同) 大小。Dynamic (動態) 則會 Develop (變化) 大小。

3. 線性佇列 (Linear Queues)

線性佇列是最簡單的版本。它就像一條排成直線的隊伍。當有新項目加入時，後端 (Rear) 指標向後移動；當項目移除時，前端 (Front) 指標向後移動。

問題所在：想像一個由 5 個空間組成的陣列建立的線性佇列。你加入了 5 個項目，然後移除了 3 個。即使前端現在有 3 個空位，後端 (Rear) 指標依然停在陣列末端！電腦會誤以為佇列已滿。這造成了嚴重的空間浪費。

快速回顧：線性佇列很容易理解，但如果我們不將數據向前移動（這很慢）或使用更好的結構，它會變得非常「佔空間」。

4. 環狀佇列 (Circular Queues)

為了解決線性佇列的「浪費空間」問題，我們可以使用環狀佇列。想像陣列的末端被「黏」回開頭，形成一個圓圈。

當 後端 (Rear) 指標到達陣列的最後一個索引時，下一個加入的項目如果發現第一個索引（索引 0）是空的，就會繞回到開頭。

運算原理：

我們使用模數 (Modulo) 運算子 \( \% \) 來計算下一個位置。如果陣列大小為 \( 5 \)，計算下一個位置的公式為：
新位置 = (目前位置 + 1) MOD 5

你知道嗎？環狀佇列被廣泛用於「緩衝區 (Buffers)」，例如 YouTube 影片載入（緩衝）時。它會不斷重複使用同一塊記憶體！

重點筆記：環狀佇列比線性佇列更節省空間，因為它們可以「繞圈」使用空間。

5. 優先佇列 (Priority Queues)

有時候，「先到先得」並不是最好的方式。在優先佇列中，項目是根據其重要性而非到達先後順序來排列的。

類比：醫院的急診室 (A&E)。如果一個人因為輕微擦傷走進來，但隨後有人因腿部骨折送醫，腿部骨折的人會優先得到診治。他們擁有更高的優先權。

• 較高優先權的項目會被移到前端。
• 如果兩個項目優先權相同，則遵循標準的 FIFO 原則。

6. 基本佇列操作

在考試中，你可能會被要求描述如何對佇列執行這四項基本操作。別被名稱嚇到了；它們只是「加入」、「移除」、「檢查是否為空？」和「檢查是否已滿？」的專業術語。

1. Enqueue（加入項目）

步驟 1：檢查佇列是否已滿（避免溢位，Overflow）。
步驟 2：如果沒滿，將 後端 (Rear) 指標移動到下一個空位。
步驟 3：在 後端 (Rear) 位置插入資料。

2. Dequeue（移除項目）

步驟 1：檢查佇列是否為空（避免下溢，Underflow）。
步驟 2：複製 前端 (Front) 位置的資料。
步驟 3：將 前端 (Front) 指標移動到下一個項目。

3. 檢查佇列是否為空

在許多實作中，如果 前端 (Front) 和 後端 (Rear) 指標處於相同位置（或者獨立的計數變數為 0），則佇列為空。

4. 檢查佇列是否已滿

如果 後端 (Rear) 指標位於最後一個可用位置（在環狀佇列中，則需判斷它後面的空間是否已被 前端 (Front) 佔用），則佇列已滿。

常見錯誤：當你執行 Dequeue（移除項目）時，資料其實還留在記憶體插槽中！我們只是移動了 前端 (Front) 指標，讓電腦「忽略」該資料。只有當新的資料寫入並覆蓋它時，該資料才算真正被「刪除」。

總結檢查清單

• 你能定義 FIFO 嗎？（先進先出）
• 你知道靜態與動態之間的區別嗎？
• 你能解釋為什麼環狀佇列比線性佇列更好嗎？
• 你記得優先佇列是基於重要性來排序的嗎？
• 你能列出 Enqueue 和 Dequeue 的步驟嗎？

如果一開始覺得有點難也不要擔心！只要在腦海中保持「超市排隊」的類比，邏輯自然就會通了。