🏗️ 第 1 週：資料結構基礎（Data Structures） 7/150
07. 數組模擬隊列的思路分析 - 怎麼用數組來模擬排隊系統？
一、 核心變數：我們需要哪些裝備？
要用一個陣列來模擬排隊，我們不能只有一個陣列，還需要幾個「指揮官」來記錄隊伍的狀態。
1. maxSize（最大容量）：
2. array（陣列本身）：
o 用來存放數據的容器，例如
int[] arr = new int[maxSize]。
3. front（隊頭指標）：
o 負責記錄「輪到誰出去了」。
o 初始值設定技巧： 通常設為 -1，指向隊列頭部的前一個位置（這樣數據處理起來會比較方便，稍後解釋）。
4. rear（隊尾指標）：
o 負責記錄「最後一個人排在哪」。
o 初始值設定技巧： 也設為 -1，指向隊列尾部的具體位置（即最後一個數據的索引）。
二、 動作分解：進場與出場
有了這兩個指標，我們就可以控制人流了。想像這兩個指標在陣列上賽跑：
1. 加入隊列 (AddQueue / Enqueue)
當有新數據要進來時，我們只看 rear（隊尾）。
· 判斷滿了沒： 先檢查 rear 是否等於
maxSize - 1。如果是，代表已經排到懸崖邊了，不能加了。
· 動作：
1. rear 往後移一格 (rear++)。
2. 將數據填入新的 rear 位置 (arr[rear] = data)。
2. 取出數據 (GetQueue / Dequeue)
當要處理數據時，我們只看 front（隊頭）。
· 判斷空了沒： 檢查 front 是否等於 rear。如果兩個指標重疊，代表隊尾已經追上隊頭（或者大家都還沒動），隊列是空的。
· 動作：
1. front 往後移一格 (front++)。
2. 取出該位置的數據 (
return arr[front])。
三、 狀態模擬：腦海中的動畫
讓我們模擬一個大小為 3 的隊列：
1. 初始狀態： front = -1,
rear = -1(空)。
2. 加入 A： rear 變 0，arr[0] = A。
3. 加入 B： rear 變 1，arr[1] = B。
4. 取出 A： front 變 0，回傳 arr[0]。
o 注意：此時 A 其實還在陣列記憶體裡，只是我們的 front 指標移開了，邏輯上視為它已經離開。
5. 加入 C： rear 變 2，arr[2] = C。
此時狀態：front = 0, rear = 2。隊列中有 B 和 C。
四、 致命缺陷：一次性使用的悲劇
仔細看上面的模擬，你會發現一個嚴重的問題。
假設我們的 maxSize 是 3。 當我們依序加入了 A, B, C，此時 rear = 2 (也就是
maxSize - 1)。隊列滿了。
接著，我們把 A, B, C 全部取出處理掉。 此時 front 也變成了 2。
· 隊列空了嗎？是的 (front == rear)。
· 我們可以再加入新數據嗎？不行！
因為我們的判斷條件是 if (rear == maxSize - 1) 就算滿。雖然陣列的前面索引 0, 1, 2 的位置邏輯上都空出來了，但 rear 指標已經頂到天花板，回不去了。
這就是所謂的**「假溢出（False Overflow）」**——明明有空間，卻因為指標的單向移動而無法使用。這個陣列變成了一次性用品，這在電腦系統中是不可接受的浪費。
五、 總結
• 兩個指標定乾坤：front 追著 rear 跑，中間的差距就是隊列中的數據。 • 初始化為 -1：這是一種方便的慣例，讓 front 指向「待處理數據的前一格」，rear 指向「最新數據的當下格」。 • 線性隊列的極限：這種簡單的實作方式會導致空間無法重複利用，這就是為什麼我們下一章必須引入「環形」的概念。
