Learning Objectives
- 說明用一般陣列做佇列時，front 一路往後走會讓前面的空位再也用不到
- 用取餘數 % cap 讓 front 與 rear 走到最後一格之後繞回 0，畫出環狀佇列在陣列裡的樣子
- 比較「front＋count」與「front＋rear，留一格」兩種判斷空與滿的寫法
- 說明 (front - 1) % cap 在 C++、Java 會得到負數，改寫成 (front - 1 + cap) % cap
- 用同一個環狀陣列做雙端佇列（deque）的兩頭進出，並使用 Python、C++、Java 內建的雙端佇列
佇列要怎麼放進一塊固定大小的記憶體
印表機的列印工作、客服的等候電話、鍵盤按下但程式還沒處理的按鍵，都是佇列（queue）：先來的先處理，新來的排在最後面。
佇列只有兩個主要操作：
| 操作 | 意思 |
|---|---|
| enqueue | 從後端（rear）放入一個元素 |
| dequeue | 從前端（front）取出一個元素 |
演算法軌第 10 課談過佇列怎麼用。這一課看的是它怎麼做出來：很多系統（作業系統的鍵盤緩衝區、網路卡收封包的緩衝區、音訊播放的緩衝區）只有一塊固定大小的陣列可以用，不能隨時要新的記憶體。在這種限制下，要怎麼讓前端一直取出、後端一直放入，又不浪費空間？
這一課的每個範例都有 Python、C++、Java 三種寫法，可以用動畫上方的按鈕切換；三種寫法的輸出完全相同。
最直覺的做法：兩個只會往前走的索引
用一個容量 cap 的陣列 data，再記兩個索引：
front：下一個要取出的位置rear：下一個要放入的位置
放入時寫到 data[rear]，然後 rear += 1；取出時讀 data[front]，然後 front += 1。兩個操作都只改一個索引，是 O(1)。
問題在於兩個索引只會往前走。取出之後，front 前面的格子已經沒人用了，可是 rear 走到 cap 之後就判斷「放不下」。下面的範例容量 5，放 4 個、取 2 個之後，佇列裡只剩 2 個元素，卻放不進第 4 個以後的東西。
只往前走的佇列：前面空出來的格子用不到
看兩個 ▲：front 和 rear 都只往右走。取出 10、20 之後，索引 0、1 變成虛線空位；rear 走到 5（超出陣列，標在格子下方）之後，50、60 都放不進去，可是陣列裡明明還有 2 格空位。這種「明明有空位卻判斷為滿」的情況叫做假溢位。
把陣列頭尾接起來：取餘數
解法之一是每次取出就把後面的元素全部往前搬一格，但這樣 dequeue 變成 O(n)。更好的做法是把陣列想成一個圓環：最後一格的下一格是第 0 格。
讓索引「走到尾端就回到 0」只要一個運算：取餘數。
i = (i + 1) % cap # cap = 5 時：0 → 1 → 2 → 3 → 4 → 0 → 1 …
這樣的佇列叫環狀佇列（circular queue），也叫環形緩衝區（ring buffer）。這一節用兩個變數記錄它的狀態：
front：第一個元素的位置count：目前有幾個元素
下一個空位不必另外記，從 front 往後數 count 格就是：rear = (front + count) % cap。第 k 個元素（從 0 算起）在 (front + k) % cap。
判斷空與滿也很直接：count == 0 是空，count == cap 是滿，容量的每一格都能用。
環狀佇列：front 與 count
容量 5。先放 10、20、30，再取出 10、20；接下來放 40、50 之後已經寫到索引 4，60 會繞回索引 0、70 放在索引 1。這時 count = 5 = cap，80 就放不進去了。注意佇列裡的元素在陣列中是 3、4、0、1 這幾格，前後不連續，但從 front 繞一圈讀過去順序是對的。
另一種記法：front 與 rear，留一格不用
很多教科書與函式庫不用 count，而是直接記 front 和 rear（下一個空位）。放入時寫 data[rear]、rear = (rear + 1) % cap；取出時讀 data[front]、front = (front + 1) % cap。
麻煩在判斷空與滿：
- 空的時候：front 追上了 rear，
front == rear - 如果把 cap 格全部放滿：rear 繞了一圈也追上 front，還是
front == rear
兩種情況長得一模一樣，程式分不出來。常見的解法是故意留一格不放：rear 的下一格就是 front 時就算滿了。
| 判斷 | 條件 |
|---|---|
| 空 | front == rear |
| 滿 | (rear + 1) % cap == front |
| 元素個數 | (rear - front + cap) % cap |
代價是容量 cap 的陣列只能放 cap - 1 個元素。元素個數的公式先加 cap 再取餘數，是因為 rear 繞回來之後可能比 front 小，rear - front 會是負數（下一節會說明負數取餘數的問題）。
兩種記法都對，差別只是「多存一個 count」或「少用一格」。
front 與 rear：容量 4 只能放 3 個
放 10、20、30 之後 rear = 3，再放 40 的話 rear 會變成 0、等於 front，所以 40 被擋下來。取出 10 之後 50 可以放進索引 3，rear 繞回 0。接著連續取出，front 追上 rear 時就是空的；最後放入的 60 寫在索引 0。
想一想：環狀佇列的索引
環狀佇列的容量 cap = 8，目前 front = 6、count = 3。佇列裡的三個元素在陣列的哪三格？
用 front 和 rear（留一格不用）的寫法，容量 cap = 6 的陣列最多能放幾個元素？
下面的程式會印出什麼？
兩頭都能進出：雙端佇列
雙端佇列（double-ended queue，簡稱 deque，念作 deck）兩端都可以放入、取出：
| 操作 | 做法（front＋count 記法） |
|---|---|
| push_back | 寫到 (front + count) % cap，count + 1（和環狀佇列的 enqueue 一樣） |
| pop_front | 讀 data[front]，front 往後一格，count - 1（和 dequeue 一樣） |
| push_front | front 往前退一格，寫到新的 data[front]，count + 1 |
| pop_back | 讀最後一個 data[(front + count - 1) % cap]，count - 1 |
四個操作都是 O(1)。只用 push_back 和 pop_front，它就是佇列；只用 push_back 和 pop_back，它就是堆疊。
往前退一格要特別小心。直覺會寫 (front - 1) % cap，但 front = 0 時：
| 語言 | (0 - 1) % 5 |
|---|---|
| Python | 4（餘數的正負號跟除數相同） |
| C++、Java | -1（餘數的正負號跟被除數相同） |
C++、Java 拿到 -1 當索引，會讀寫到陣列外面（Java 丟出例外，C++ 是未定義行為）。三種語言都通用的寫法是先加 cap：(front - 1 + cap) % cap，括號裡一定不是負數。
用環狀陣列做雙端佇列
push_front 5 時 front 從 0 退到 4（陣列最後一格），push_front 1 再退到 3。此時佇列由前到後是 1、5、10、20，在陣列裡卻是索引 3、4、0、1。pop_back 取出 20，push_front 9 寫到索引 2，pop_front 又把 9 取出。
各語言內建的雙端佇列
實際寫程式時直接用內建的雙端佇列，它們都是 O(1) 的兩端操作，而且會自動長大，不會「滿」：
| 操作 | Python collections.deque |
C++ std::deque |
Java ArrayDeque |
|---|---|---|---|
| 後端放入 | dq.append(x) |
dq.push_back(x) |
dq.addLast(x) |
| 前端放入 | dq.appendleft(x) |
dq.push_front(x) |
dq.addFirst(x) |
| 前端取出 | dq.popleft() |
dq.front() 再 dq.pop_front() |
dq.pollFirst() |
| 後端取出 | dq.pop() |
dq.back() 再 dq.pop_back() |
dq.pollLast() |
三者內部的做法不同：Java 的 ArrayDeque 就是這一課的環狀陣列，滿了就換一個更大的陣列再搬過去；
Python 的 deque 把資料分成固定大小的區塊，區塊之間用雙向鏈結串列串起來；C++ 的 std::deque 通常也是分成區塊，另外用一個表記住各區塊的位置。兩者在兩端不夠用時都是加一個新區塊，不必搬動舊資料。
細節依實作而定，使用上的共同點是兩端進出都很快。
不要用 Python 的 list 當佇列：lst.pop(0) 會把後面每個元素往前搬一格，是 O(n)。
下面用雙端佇列判斷迴文（正著讀和倒著讀一樣的字）：每一輪從前端和後端各取一個字元比較，相同就繼續往中間靠。
內建雙端佇列：判斷迴文
level、racecar 每一輪兩端取出的字元都相同，最後剩 0 或 1 個字元就是迴文。abcda 第一輪 a 和 a 相同，第二輪 b 和 d 不同，立刻回傳「不是」。（C++、Java 的函式名稱是 isPalindrome。）
想一想：雙端佇列與負數取餘數
Java 執行 System.out.println((0 - 1) % 5); 會印出什麼？
容量 cap = 6 的環狀雙端佇列，front = 4、count = 3。執行 pop_back 會取出陣列哪一格的元素？
用 Python 的 list 當佇列，每次 lst.pop(0) 取出第一個元素。n 個元素全部取完，總共大約要搬動幾次元素？
實作：只保留最近 k 筆資料
感測器、聊天室、「最近瀏覽」常常只要保留最近 k 筆：還沒滿就放在後面，滿了就蓋掉最舊的那一筆。請完成 add：還沒滿時寫到 (front + count) % cap、count 加 1；滿了就把新值寫在 front（最舊的那一格），再讓 front 往後一格。預期輸出在右邊。
重點整理
- 用陣列做佇列，如果 front、rear 只往前走，取出後空出來的格子再也用不到（假溢位）
- 環狀佇列用
% cap讓索引走到最後一格之後回到 0，放入、取出都是 O(1)，空位可以重複使用 - 記法一：
front與count。空＝count == 0，滿＝count == cap，下一個空位(front + count) % cap - 記法二：
front與rear，留一格不用。空＝front == rear，滿＝(rear + 1) % cap == front，最多放 cap - 1 個 - C++、Java 的負數取餘數會是負的；往前退一格寫
(front - 1 + cap) % cap - 雙端佇列兩端都能進出，同一個環狀陣列多寫 push_front、pop_back 就能做到；內建的是 Python
collections.deque、C++std::deque、JavaArrayDeque
下一課：堆疊的應用。堆疊只在一端進出，看它怎麼檢查括號、把運算式轉成電腦好計算的順序。