跳到主要內容
Jasonmel Online

資料結構

資料怎麼排，決定了哪些操作便宜

主題 · 佇列與雙端佇列

佇列與雙端佇列

先進先出：從尾端排進來、從前端出去。用環狀陣列實作，兩端進出都只要一步，不用搬動任何元素。

雙端佇列：
底下的陣列（4 格，第 3 格之後接回第 0 格）
  1. 0
  2. 20
    1head
  3. 30
    2
  4. 3tail
排隊順序（前 → 後）：20 → 30
剛寫入剛取出擴容時複製過來空格

head 指著最前面的元素，tail 是下一個要寫入的格子。兩個索引都只會往前走，走過最後一格就繞回第 0 格：取出時沒有任何元素需要搬動。

元素／容量
2 / 4
head
1
tail
3
這次碰了幾格
–
亮起來的是這一步執行的程式碼
class RingDeque {
  private buf: number[] = new Array(4);
  private head = 0;
  private size = 0;
 
  pushBack(value: number): void {
    if (this.size === this.buf.length) this.grow();
    this.buf[(this.head + this.size) % this.buf.length] = value;
    this.size++;
  }
 
  pushFront(value: number): void {
    if (this.size === this.buf.length) this.grow();
    this.head = (this.head - 1 + this.buf.length) % this.buf.length;
    this.buf[this.head] = value;
    this.size++;
  }
 
  popFront(): number | undefined {
    if (this.size === 0) return undefined;
    const value = this.buf[this.head];
    this.head = (this.head + 1) % this.buf.length;
    this.size--;
    return value;
  }
 
  popBack(): number | undefined {
    if (this.size === 0) return undefined;
    this.size--;
    return this.buf[(this.head + this.size) % this.buf.length];
  }
 
  private grow(): void {
    const bigger = new Array(this.buf.length * 2);
    for (let i = 0; i < this.size; i++) {
      bigger[i] = this.buf[(this.head + i) % this.buf.length];
    }
    this.buf = bigger;
    this.head = 0;
  }
}

模型假設與範圍

  • Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

  • 先到先處理：工作排隊、印表機佇列、BFS（Breadth-First Search，廣度優先搜尋）一圈一圈往外擴。
  • 生產者和消費者速度不一樣時當緩衝區：鍵盤輸入、網路封包、音訊播放。
  • 兩端都要進出（雙端佇列）：滑動視窗、只保留最近 N 筆的紀錄。

和其他主題的關係

由這些組成
動態陣列
延伸閱讀
堆疊

語言內建的版本

Array<T> + head index

JavaScript 沒有內建的佇列或雙端佇列。陣列的 shift() 會把後面每一格往前挪，是 O(n)；量大時改用「陣列加一個頭索引」，或兩個堆疊拼成的佇列。

操作寫法成本
入隊q.push(4)O(1) amortised
出隊（頭索引）q[head++]O(1)
出隊（shift）slow.shift()O(n)
看隊首q[head]O(1)
長度q.length - headO(1)
// Simple but O(n) per dequeue: shift moves every element.
const slow = [1, 2, 3];
slow.shift();                  // → 1
slow;                          // → [2, 3]
 
// O(1): never move elements, just advance a head index.
const q = [1, 2, 3];
let head = 0;
q.push(4);                     // → 4
q[head];                       // → 1
q[head++];                     // → 1
q[head++];                     // → 2
q.length - head;               // → 2
// Drop the consumed prefix once it is at least half the array.
if (head * 2 >= q.length) { q.splice(0, head); head = 0; }
q;                             // → [3, 4]
 
// Two stacks: push onto inbox, pop from outbox; each item moves once.
const inbox: number[] = [], outbox: number[] = [];
const enqueue = (x: number) => inbox.push(x);
const dequeue = () => {
  if (outbox.length === 0) while (inbox.length) outbox.push(inbox.pop()!);
  return outbox.pop();
};
enqueue(1); enqueue(2); enqueue(3);
dequeue();                     // → 1
enqueue(4);
[dequeue(), dequeue(), dequeue()];  // → [2, 3, 4]
dequeue();                     // → undefined

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

  • 幾百、幾千個元素時 shift() 夠快（V8 對小陣列有優化），寫 BFS 練習題常常直接用；但上萬個以上，O(n) 的 shift() 會讓 BFS 從 O(V + E) 變成平方級。
  • 兩個堆疊的佇列：每個元素最多被搬一次，所以出隊攤銷是 O(1)，但單次出隊最壞是 O(n)。

時間與空間複雜度（Big O）

操作平均最差
任一端加入
均攤 O(1)：只有擴容那一次要複製
O(1)O(n)
任一端取出O(1)O(1)
讀第 i 個
位置是 (head + i) mod 容量
O(1)O(1)
用一般陣列在前端取出O(n)O(n)

空間：O(n)，容量最多是元素數的兩倍

Big O 實測：n 變大時步數怎麼長

數的是：佇列裡有 n 個元素時，每次操作碰到的格子數（100 次取平均）

Big On = 1,000n = 10,000n = 100,000成長倍數：實測（理論）
環狀陣列：前端取出O(1)111×1.0 (×1.0)
環狀陣列：尾端加入（含擴容）O(1)2.02.62.3×1.1 (×1.0)
一般陣列：前端取出O(n)9999,99999,999×100 (×100)

和其他做法比

環狀陣列一般陣列（前端固定在第 0 格）
尾端加入11
前端取出11,000
前端加入11,001
尾端取出11

佇列裡有 1,000 個元素時，每種操作碰到的格子數。一般陣列在前端進出都得把全部元素搬一格，這就是 JavaScript 的 shift() 和 Python 的 list.pop(0) 在做的事。

真實世界裡的它

  • Python 的 collections.deque、Java 的 ArrayDeque、C++ 的 std::deque。
  • 網路卡和音效卡驅動程式的環狀緩衝區；Linux 的 io_uring 就是一對環狀佇列。
  • 訊息佇列是同一個概念放大到好幾台機器（見系統設計）。

取捨與陷阱

  • 拿一般陣列當佇列（JavaScript 的 shift()、Python 的 list.pop(0)）：每次取出都要搬動全部元素，整段變成 O(n²)。
  • 環狀陣列要分得出「空」和「滿」：兩種情況下 head 都等於 tail，所以這裡另外記 size。
  • 有上限的佇列滿了要選策略：擋住生產者、丟掉最舊的，還是拒絕新的。

LeetCode 練習