9/150. 數組模擬環形隊列的概念 - 佇列滿了怎麼辦？環形隊列來救場！

🏗️ 第 1 週：資料結構基礎（Data Structures） 9/150

09. 數組模擬環形隊列的概念 - 佇列滿了怎麼辦？環形隊列來救場！

回想一下上一章的悲劇：當 rear 走到陣列盡頭（maxSize - 1）時，即使前面的人已經離開（front 往前移了），空出來的座位也無法再次使用。這就像一輛公車，一定要整台車的人都下光了，才能讓新的一批人上車，這顯然不合理。

解決方案： 想像把陣列的頭（Index 0）和尾（Index maxSize-1）接起來，變成一個圓環。 當 rear 走到盡頭時，下一步不是「撞牆」，而是「回到 0」。

這就是 環形佇列（Circular Queue）。

二、 數學魔法：取餘數運算 (%)

要怎麼讓電腦知道 3 的下一個是 0（假設最大長度是 4）？ 靠 if-else 判斷太笨拙了，我們用最優雅的數學運算：取模（Modulo, %）。

公式： 下一個位置 = (當前位置 + 1) % maxSize

• 假設 maxSize = 4（索引是 0, 1, 2, 3）：
• • 0 的下一個：(0 + 1) % 4 = 1
  • 1 的下一個：(1 + 1) % 4 = 2
  • 2 的下一個：(2 + 1) % 4 = 3
  • 3 的下一個：(3 + 1) % 4 = 0 (回到原點！)

這個 % 運算符就是讓隊列循環起來的引擎。

三、 規則調整：指標的新定義

為了方便計算環形狀態，我們通常會調整 front 和 rear 的初始定義（這點非常重要，請把上一章的舊定義先暫存一旁）：

1. front 變了：
2. • 指向隊列的第一個實際元素。
   • 初始值 front = 0。
2. rear 變了：
3. • 指向最後一個元素的下一個位置（也就是預留的空位）。
   • 初始值 rear = 0。

為什麼要預留一個空位？ 如果 rear 也指向最後一個實際元素，當隊列「全滿」和「全空」時，front 都會等於 rear。為了區分這兩種狀態，我們約定：隊列中必須永遠保留一個格子不放數據。這個格子就是 rear 指向的那個位置。

四、 三大核心公式（考試/面試必考）

在環形佇列中，判斷滿或空的邏輯發生了變化：

1. 判斷隊列為空（Is Empty）：
2. • front == rear
   • 解釋：追兵追上來了，或者大家都還在原點。
2. 判斷隊列已滿（Is Full）：
3. • (rear + 1) % maxSize == front
   • 解釋：rear 的下一個位置就是 front。也就是說，除了那個預留的空位，其他都滿了。
3. 計算有效數據個數（Size）：
4. • (rear + maxSize - front) % maxSize
   • 解釋：因為是環形的，rear 可能跑到 front 的前面（數值上比較小），所以要先 + maxSize 補正，再取餘數。這是計算環形距離的標準公式。

五、 狀態模擬

假設 maxSize = 4（實際上只能存 3 個數據，因為要留一個空位）：

1. 初始： front=0, rear=0 ➡️ 空
2. 加入 10： arr[0]=10, rear 變成 1 ➡️ 狀態：[10, ?, ?, ?]
3. 加入 20： arr[1]=20, rear 變成 2 ➡️ 狀態：[10, 20, ?, ?]
4. 加入 30： arr[2]=30, rear 變成 3 ➡️ 狀態：[10, 20, 30, ?]
5. • 此時判斷滿了嗎？ (3 + 1) % 4 == 0 (等於 front)，滿了！
5. 取出 10： front 變成 1 ➡️ 狀態：[?, 20, 30, ?]
6. 加入 40：
7. • 此時 rear 在 3。
   • arr[3]=40, rear 變成 (3+1)%4 = 0。
   • 狀態：[?, 20, 30, 40] (40 填補了之前的空位，成功循環！)

六、 總結

• 循環的關鍵：利用 % 運算符，讓索引值在 0 到 maxSize-1 之間無限輪迴。 • 代價：為了區分「滿」與「空」，我們犧牲了一個儲存空間（rear 指向的那個位置永遠是空的）。 • 優勢：空間真正被重複利用，再也沒有「假溢出」的問題，這是所有現代作業系統緩衝區的標準設計。