想像大家排隊買票：先到的人先買，後來的人排到隊伍最後面。資料結構裡的**佇列（queue）**也是這樣運作：先放進去的資料，會先被取出來。這剛好和上一篇的堆疊相反，堆疊是最後放進去的資料先取出。

先進先出：佇列的順序規則

佇列遵守**先進先出（First In, First Out, FIFO）**的規則。假設依序放入 A、B、C，A 最早來，所以最先離開；C 最晚來，要等 A、B 都離開後才輪到它：

簡單說，佇列就像一條不能插隊的隊伍：新資料一律排到最後面，離開的一定是排在最前面的那一筆。

加入與取出資料

佇列有兩個基本操作：

• enqueue：把新資料排到隊伍最後面。
• dequeue：把隊伍最前面的資料取出，並從佇列中移除。

為了知道隊伍的頭尾在哪裡，會用兩個名稱來標記：

• front（隊首）：隊伍最前面，也就是下一筆要離開的資料。
• rear（隊尾）：隊伍最後面，也就是最後加入的資料。

依序執行 enqueue(A)、enqueue(B)、enqueue(C) 後，隊伍長這樣：

這時執行一次 dequeue，會取出 A，B 就變成新的隊首。不能跳過 A 先取出 B，這就是「不能插隊」的意思。

要注意的是，front 和 rear 實際指向哪一格，不同實作可能不一樣。例如有些實作讓 rear 指向「下一個可以放資料的空格」，而不是最後一筆資料。本篇的圖都採用上面的說法；之後看課本或寫程式時，要先確認它們在該實作中的定義。

用陣列做佇列，為什麼會浪費空間？

如果用陣列存放佇列，每加入一筆資料，rear 就往後移一格；每取出一筆資料，front 也往後移一格。兩者都只會往後走，不會回頭。這種做法稱為線性佇列。

問題就出在「不會回頭」。假設陣列有 5 格，先放入 10、20、30、40、50，再取出 10 和 20：

前面兩格已經空出來了，但 rear 已經走到陣列最後一格，後面沒有位置可以放。結果明明還有空格，卻不能加入新資料。

一種解法是每次取出資料後，把剩下的資料全部往前搬，讓空格回到後面。但這樣每次取出都要搬動資料，資料越多，搬得越久。

環狀佇列：讓陣列頭尾相連

**環狀佇列（circular queue）**換個想法：不搬資料，而是把陣列的最後一格和第一格接起來，想像成一個圓圈。走到最後一格之後，下一格就回到索引 0。

以 5 格的陣列為例，位置依序是 0、1、2、3、4，從索引 4 再往下一格就回到索引 0：

回到剛才的例子：放入 10、20、30、40、50，再取出 10 和 20，前兩格空了出來。這時要加入 60 和 70，rear 會從位置 4 繞回位置 0，把它們放進前面的空格：

這張圖有兩件事要特別注意：

1. 讀取順序要從 front 開始繞一圈。 60 和 70 雖然放在陣列的位置 0、1，但它們是最後才加入的。佇列真正的順序是 30、40、50、60、70，不能照陣列從左到右讀。
2. 這個佇列已經滿了。 5 個格子都有資料，再加入就沒有位置可放。

環狀佇列的關鍵在於：資料本身不用移動，只要讓 front 和 rear 走到底時繞回開頭，就能重複利用空出來的格子。

空佇列與滿佇列

佇列裡沒有任何資料，稱為空佇列；所有格子都放滿，稱為滿佇列。這兩種狀態都要在操作前檢查：

• 對空佇列執行 dequeue，沒有資料可取，稱為下溢（underflow）。
• 對滿佇列執行 enqueue，沒有位置可放，稱為上溢（overflow）。

在環狀佇列中，分辨空和滿會變得有點麻煩。看看上一張圖：佇列滿的時候，rear（位置 1）就在 front（位置 2）的前一格。如果接著把 5 筆資料全部取出，front 會一路往後移、繞過開頭，最後停在位置 2，而 rear 仍在位置 1。也就是說，空佇列和滿佇列的 front、rear 位置關係一模一樣，只看這兩個位置無法分辨。

常見的解決方法有兩種：

• 另外記錄資料筆數：用變數 count 記錄目前有幾筆資料。count 為 0 表示空，count 等於陣列格數 n 表示滿。也可以改用一個旗標（flag）記錄佇列目前是否已滿。
• 刻意空一格不用：這種做法通常讓 rear 指向「下一個可以放資料的空格」。front == rear 表示空；如果 rear 再往下一格就會碰到 front，也就是 (rear + 1) % n == front，就視為滿。因為永遠留一格空著，空和滿的條件不會重疊，代價是 n 格的陣列最多只能放 n - 1 筆資料。

公式中的 % n 是取餘數，負責處理「繞回開頭」。例如 n 為 5 時，(4 + 1) % 5 等於 0，代表位置 4 的下一格是位置 0。

本篇的環狀佇列圖採用「5 格都能放資料」的想法。如果改用空一格的做法，5 格陣列最多只能放 4 筆，上面那張滿載的圖就不會出現。實作時要依照自己採用的做法寫判斷條件，兩種做法的條件不能混用。

小結

佇列就像不能插隊的隊伍：資料從隊尾加入、從隊首離開，先來的先走。用陣列做線性佇列時，前面空出的格子沒辦法直接再利用；環狀佇列把陣列頭尾接起來，讓 front 和 rear 走到底後繞回開頭，就能重複使用這些空格。不過繞回來之後，空和滿的位置關係會變得一樣，需要另外記錄筆數，或刻意空一格來分辨。

今日重點：

• 佇列遵守先進先出（FIFO）：資料從隊尾加入，從隊首取出。
• enqueue 把資料加到隊尾；dequeue 取出並移除隊首資料。
• 線性佇列的前端空格無法直接重用；環狀佇列把陣列尾端接回開頭來解決這個問題。
• 環狀佇列的資料順序要從 front 開始，沿著環繞方向讀。
• 環狀佇列只看 front、rear 分不出空和滿，常用筆數 count 或空一格的方式判斷。
• 空佇列取出資料會下溢；滿佇列加入資料會上溢。

下一篇將比較陣列版與鏈結版的堆疊、佇列，看看它們在容量管理和記憶體使用上的差異。