佇列與雙端佇列：先進先出

銀行裡的隊伍

佇列就是一條井然有序的隊伍。新來的人從隊尾加入；櫃員從隊首叫號。最先來的人最先離開——先進先出，即 FIFO。只要關乎公平或到達順序，它就是自然的選擇。

兩個核心操作各有名字：enqueue（入隊）從隊尾加入，dequeue（出隊）從隊首移除。兩者都是 O(1)——在一端加、在另一端刪，從不需要移動任何人。

dequeue <- [ 1 | 2 | 3 ] <- enqueue
          front        back

enqueue 4:  [ 1 | 2 | 3 | 4 ]
dequeue  :  returns 1 ->  [ 2 | 3 | 4 ]

隊尾加，隊首刪。兩端相對——這正是 FIFO 的由來。

C++ 裡的 std::queue

標準函式庫提供 `std::queue`。它的術語和堆疊略有不同：在隊尾 `push`（入隊），用 `front()` 讀隊首，從隊首 `pop()`。

#include <queue>
#include <iostream>

std::queue<int> q;
q.push(1);              // enqueue
q.push(2);
q.push(3);
std::cout << q.front(); // 1 (the FIRST one in)
q.pop();                // dequeue -> removes 1
std::cout << q.front(); // 2

std::queue：push 在隊尾加，front() 讀隊首，pop() 移除隊首。

環形緩衝區的思路

用普通陣列實作佇列會遇到個麻煩：如果每次從隊首刪除都把後面整體左移，那麼每次出隊都要 O(n)。聰明的辦法是環形緩衝區——維護兩個索引 `head` 和 `tail`，讓它們到達固定陣列末端後繞回開頭。這樣從不需要移動元素。

capacity 5, head=front, tail=next free slot:

  index:  0   1   2   3   4
        [ . | 2 | 3 | 4 | . ]
              ^head       ^tail

enqueue 5 -> tail goes to 4; enqueue 6 -> tail WRAPS to 0
        [ 6 | 2 | 3 | 4 | 5 ]
          ^tail ^head

(use tail = (tail + 1) % capacity to wrap)

環形緩衝區用取模讓索引繞回，從而複用前端空出的格子。

關鍵技巧是取模：`index = (index + 1) % capacity` 讓索引從最後一格跳回第 0 格。有了它，入隊和出隊都保持 O(1)，且沒有任何元素被移動。

雙端佇列，以及佇列的用武之地

deque（雙端佇列，讀作 "deck"）允許你在兩端都進行加和刪——隊首和隊尾皆可。它是堆疊和佇列的超集。在 C++ 裡，`std::deque` 提供 `push_front`、`push_back`、`pop_front`、`pop_back`，全是 O(1)。

#include <deque>

std::deque<int> d;
d.push_back(2);    // [2]
d.push_front(1);   // [1, 2]
d.push_back(3);    // [1, 2, 3]
d.pop_front();     // [2, 3]   removed 1
d.pop_back();      // [2]      removed 3

std::deque：兩端都能 O(1) 地伸縮。

為什麼要在意它？任務佇列按到達順序處理作業。作業系統從一個佇列裡排程程式。而廣度優先搜尋——逐層探索圖，你將在"樹與圖"那一階見到它——完全建立在佇列之上：你把鄰居入隊，再按發現順序出隊。佇列正是"按到達順序處理事情"的引擎。