Queues

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

你好！今天我們要一起探索電腦組織數據最常見且實用的方法之一：隊列（Queue）。試著回想一下你上次排隊買咖啡或是等巴士的情景，那就是一個隊列！在電腦科學中，我們運用同樣的「公平」原則，確保數據能按正確的順序被處理。無論你是程式編寫的高手還是初學者，這份指南都能幫助你掌握隊列的運作原理與建構方式。

1. 基本概念：什麼是隊列？

隊列是一種線性數據結構（Linear Data Structure）。這意味著其中的元素是按照特定順序，一個接一個地排列的。關於隊列，最需要記住的就是數據進出規則的「黃金法則」。

FIFO 原則

隊列遵循 FIFO 原則。這代表 First-In, First-Out（先進先出）。
• First-In（先進）：第一個進入隊列的元素……
• First-Out（先出）：……會是第一個被移除的。

現實生活中的比喻：想像有一群人正在戲院排隊買票。排在隊伍最前面的人最先抵達，因此他們也是第一批買到票並離開的人。新來的人必須排在隊伍的最後面。如果排在最後的人先買到票，那就不公平了，對吧？

必須知道的關鍵術語

• Front (或 Head) / 前端（或隊頭）：隊列中移除元素的一端。
• Rear (或 Tail) / 後端（或隊尾）：隊列中加入新元素的一端。
• Enqueue（入隊）：將元素加入隊列後端的技術術語。
• Dequeue（出隊）：將元素從隊列前端移除的技術術語。

快速複習：
• Enqueue（入隊） = 加入到 Rear（後端）。
• Dequeue（出隊） = 從 Front（前端）移除。

重點總結：隊列是一種「公平」的結構，因為它完全按照數據抵達的順序進行處理 (FIFO)。

2. 隊列如何運作：逐步解析

如果這聽起來有點抽象，別擔心！讓我們來看看實際操作隊列時會發生什麼事。

步驟 1：Enqueue（加入數據）

想像我們有一個空的隊列，想加入數字 10。
1. 我們檢查隊列是否已滿（我們不希望它溢出！）。
2. 我們將數字 10 放置在 Rear（後端）。
3. Rear 指標向後移動一位，指向新的空位或新的最後一個元素。

步驟 2：Dequeue（移除數據）

現在我們想移除一個元素。
1. 我們檢查隊列是否為空（我們不能移除不存在的東西！）。
2. 我們取出目前位於 Front（前端）的元素。
3. Front 指標向後移動一位，指向隊列中的下一個元素。

常見錯誤：學生有時會以為執行 Dequeue 時，所有其他元素都會「向前滑動」到前端。在簡單的陣列實作中，元素通常保持原位，我們只是移動 Front 指標。對電腦來說，移動一個指標比移動 100 個數據元素要快得多！

重點總結：我們使用兩個指標（Front 和 Rear）來追蹤隊伍的起點和終點。

3. 使用陣列實作隊列

在考試中，你需要知道如何使用一維陣列來建構隊列。主要有兩種方式：線性隊列（Linear Queue）與環狀隊列（Circular Queue）。

線性隊列 (Linear Queue)

線性隊列是最簡單的版本，它的大小是固定的。
問題所在：當你不斷進行入隊與出隊操作時，指標會向陣列末端移動。即使你從前端移除了元素，"Rear" 指標最終還是會到達陣列的末端。電腦可能會認為隊列已「滿」，即使開頭其實還有空位！這種現象通常稱為空間浪費（Shuffling/Sagging）。

環狀隊列 (Circular Queue)

環狀隊列則聰明得多。當 Rear 指標到達陣列末端時，如果開頭有空位，它會「環繞」回到陣列的第一個索引位置。

比喻：想像一個環形跑道。如果你一直跑，並不會撞到盡頭的牆，而是會再次經過起跑線！

數學技巧：為了讓指標環繞，我們使用 MOD（取餘數）運算子。
若陣列大小為 5，指標移動的公式如下：
\( NewPointer = (CurrentPointer + 1) \text{ MOD } 5 \)

檢測隊列是否已滿或為空

使用陣列時，你必須能判斷隊列的狀態：
• Empty（空）：通常發生在 Front 和 Rear 指標位於相同位置（或指向一個特殊的「空」值）。
• Full（滿）：當 Rear 指標正好在 Front 指標「後面」，且已無空間可移動時。

重點總結：環狀隊列更有效率，因為它們能重複利用被出隊操作遺留下來的空位。

4. 我們何時使用隊列？

隊列在運算中無處不在！你應該能夠描述幾個使用隊列的情境：

• 印表機隊列 (Printer Queues)：當五個人同時點擊「列印」時，印表機會使用隊列來確保文件按照發送的順序逐一列印。
• 鍵盤緩衝區 (Keyboard Buffers)：當你打字非常快時，電腦會將按鍵輸入存入隊列，以便按順序逐一處理每個輸入。
• 作業系統排程 (Operating System Scheduling)：CPU 使用隊列來決定下一個要執行的程式是什麼。
• 數據緩衝區 (Data Buffers)：串流播放影片時，數據會進入隊列，即使網速波動，影片也能流暢播放。

你知道嗎？隊列對於異步（Asynchronous）數據傳輸至關重要。這只是一種專業說法，意指兩件事以不同的速度運作（例如你快速的 CPU 與緩慢的印表機）。

重點總結：每當你需要「公平地」且「按接收順序」處理數據時，就該使用隊列。

5. 總結與小撇步

記憶法：記住 F-F (Front 用於 First-Out) 以及 R-I (Rear 用於 Input)。

快速複習箱：
1. FIFO：先進先出。
2. Enqueue：加到後面 (Rear)。
3. Dequeue：從前面移除 (Front)。
4. 線性隊列：簡單但空間容易耗盡。
5. 環狀隊列：透過環繞重複利用空間。
6. Overflow（溢出）：嘗試往已滿的隊列中加入元素。
7. Underflow（下溢）：嘗試從已空的隊列中移除元素。

如果一開始覺得很複雜，別擔心！試著多想像戲院排隊的情境。只要你能理解人們是如何加入隊伍並離開的，你就已經掌握了電腦科學中 90% 的隊列原理了！