Queues

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

你好！這一章我們要探討的是隊列（Queue），它是計算機科學中最基礎且最有用的數據結構之一。如果你有排隊搭巴士或買咖啡的經驗，那麼你已經掌握了隊列的核心概念了！

隊列之所以重要，是因為它能以高度受控且有序的方式來管理處理流程和數據流。我們將探討它的運作原理、遵循的特定規則，以及如何在程式碼中高效地實作它，並解決一些常見的實作難題。

3.2.3 理解隊列數據結構

核心原則：FIFO（先進先出）

隊列最重要的規則就是它的原則：FIFO，即 First-In, First-Out（先進先出）。

比喻： 想像一下超級市場的結帳隊列。最先排進隊伍的人，也是第一個獲得服務並離開隊伍的人。新的項目（人）總是從隊尾加入，而項目總是從隊頭移除。

這種嚴格的排序機制正是隊列的定義，也讓它與堆疊（Stack，後進先出 LIFO）等其他結構區分開來。

重點總結：FIFO 規則

數據進入隊列的順序，就是它離開隊列的順序。

基本的隊列操作

隊列需要特定的方法（操作）來管理其內容。在處理隊列時，我們會使用專門的術語來表示數據的加入和移除。

1. Enqueue（加入隊列）

Enqueue 是用來將項目加入隊列的操作。

• 項目去哪了？它總是會被加入到隊列的 Rear（或 Back，即隊尾）。
• 在實作層面，這通常涉及更新一個指針或索引（通常稱為 Rear 指針），使其指向新的最後一個元素。

2. Dequeue（移出隊列）

Dequeue 是用來將項目從隊列中移除的操作。

• 項目從哪裡被移除？它總是從隊列的 Front（即隊頭）被移除。
• Dequeue 操作會回傳被移除項目的值。
• 在實作層面，這涉及更新 Front 指針，使其指向隊列中的下一個首位元素。

常見錯誤提醒： 學生經常搞混這些術語。請記住：「E」代表 Enqueue（Enter，從隊尾進入），「D」代表 Dequeue（Depart，從隊頭離開）。

描述隊列的適用場景

每當資源需要公平且按順序處理，以確保沒有請求被忽略或無限期延遲時，我們就會用到隊列。

你需要在以下情況使用隊列數據結構：

• 任務排程： 作業系統（OS）管理多個等待 CPU 的任務或行程。隊列確保第一個請求 CPU 時間的任務，也會是下一個獲得資源的任務。
• 輸入/輸出緩衝（Buffering）： 當數據傳輸時（例如串流影片或將檔案傳送到印表機），數據會儲存在緩衝區（隊列）中，以處理處理速度的差異。數據必須嚴格按照到達的順序進行處理。
• 模擬： 模擬現實世界的系統，如交通流量、客戶服務櫃檯排隊或製造業生產線。

你知道嗎？

「列印隊列（Print Queue）」的概念是隊列數據結構在軟體應用中最完美的範例。第一個發送到印表機的文件，就是第一個被列印出來的文件。

使用一維陣列實作隊列

雖然某些程式語言提供了內建的隊列函式庫（你應該要有使用它們的經驗！），但了解如何從零開始建構隊列至關重要，我們通常會使用一維陣列來實現。

我們使用兩個主要的指針（或索引）來管理陣列中的隊列：

• Front： 指向第一個項目（下一次 Dequeue 將會發生的位置）。
• Rear： 指向最後一個項目（下一次 Enqueue 將會發生的位置）。

線性隊列（Linear Queue）的實作

在簡單的線性隊列中，當你進行 Enqueue 時，Rear 指針加 1；當你進行 Dequeue 時，Front 指針加 1。

線性隊列的問題：

想像一個大小為 5 的陣列。如果我們加入 5 個項目（填滿陣列）然後移出 4 個項目，此時 Front 指針位於索引 4，而 Rear 指針位於索引 5。儘管前四個空位（索引 0 到 3）現在是空的，我們卻無法加入新項目，因為 Rear 指針已經到達陣列末端。這很不高效，因為導致了陣列前端的空間浪費。

解決方案：環狀隊列（Circular Queue）

環狀隊列解決了線性隊列的問題，它允許指針（Front 和 Rear）在到達陣列末端時「繞回」到陣列開頭。

比喻： 想像陣列是一個甜甜圈或圓環。當 Rear 指針到達最後一塊時，下一塊就會回到第一塊（如果它是空的）。

環狀隊列如何運作（繞回機制）

為了實現指針繞回，我們通常使用 MOD（模數/取餘） 運算子。

如果陣列大小為 \(N\)，那麼在更新指針（我們稱之為 P）時：

新 \(P\) = (\(P\) + 1) MOD \(N\)

如果 \(N\) = 10，而 Rear 在索引 9，(9 + 1) MOD 10 = 0。指針會繞回到索引 0。這最大化了固定陣列空間的使用率。

測試隊列狀態：空還是滿？

使用陣列實作（無論是線性還是環狀）時，在執行操作前必須先檢查隊列的狀態，以避免錯誤（例如嘗試從空隊列中移出資料）。

1. 測試隊列是否為空

如果 Front 和 Rear 指針指向同一個位置，代表它們之間沒有儲存任何元素，此時隊列為空。

• 判斷為空規則： 當 Front = Rear 時，隊列為空。
• 注意： 有時在初始化隊列時，Front 和 Rear 會被設定為 sentinel 值（例如 -1 或 0），但在使用後，判斷為空的主要依據是它們是否再次重合。

2. 測試隊列是否已滿（環狀陣列的關鍵）

判斷環狀隊列是否已滿較具挑戰性，因為 Front = Rear 同時也是「空」的條件。為了區分「滿」和「空」，陣列實作通常會保留一個永遠不使用的空位。

當 Rear 指針的下一個位置就是 Front 指針時，我們認為隊列已滿。

• 判斷已滿規則： 當 (Rear + 1) MOD N = Front 時（其中 N 為陣列大小），隊列已滿。

這個規則確保了 Front 和 Rear 之間始終至少有一個空格，讓演算法能夠正確識別隊列究竟是空的，還是已經完全填滿。

如果環狀隊列的數學計算起初看起來很棘手，不用擔心。請嘗試用一個小型陣列範例（大小為 5 或 6）來追蹤指針位置，特別注意當你到達最大索引值時發生了什麼，你很快就會理解 MOD 運算子的妙用了！

記住： 你也應該具備使用標準程式語言函式庫所提供的內建隊列數據結構的經驗，因為這些函式庫已經幫你處理了環狀分配和指針管理的複雜細節！