キュー

キューとは

キュー (Queue) は、先に追加された要素が先に取り出される FIFO (First-In, First-Out) のデータ構造である。enqueue (末尾に追加) と dequeue (先頭から取り出し) の 2 つの操作で構成される。レジの行列と同じ原理だ。

要素の出入口を両端に分けているのが機序の核心である。追加は末尾だけ、取り出しは先頭だけに限ることで、待った順序が構造そのものに保存される。後から来た要素が先に処理される追い越しが起きないため、先に受け付けた処理が後回しにならない。到着順の公平さが要件になる場面 (印刷ジョブ、リクエストの受付、探索の走査順) では、この性質がそのまま採用理由になる。

計算量

両端を分けた設計は計算量にも表れる。要素数がいくら増えても主要な操作のコストが変わらない。

TypeScript での実装

O(1) を保つには、先頭を取り出すたびに残りの要素をずらす実装を避ける必要がある。次の実装は先頭と末尾の位置を番号で覚えておき、要素そのものを動かさずに出入りさせる。

class Queue<T> {
  private items: Map<number, T> = new Map();
  private head = 0;
  private tail = 0;

  enqueue(item: T): void {
    this.items.set(this.tail++, item);
  }

  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    const item = this.items.get(this.head);
    this.items.delete(this.head++);
    return item;
  }

  peek(): T | undefined {
    return this.items.get(this.head);
  }

  isEmpty(): boolean {
    return this.head === this.tail;
  }

  get size(): number {
    return this.tail - this.head;
  }
}

配列の shift() は先頭を取り除いた後に残りの要素を 1 つずつ前へ詰めるため O(n) になる。20 万件の enqueue と dequeue を Node.js v26 で測ると、shift() を使う実装が 2727 ms、上の Map ベースが 17 ms だった。件数が増えるほど差は開く。ただし Map ベースにも落とし穴がある。dequeue で delete を省くと取り出し済みの要素が Map に残り続け、長く動くプロセスではメモリが単調に増えていく。

キューの種類

用途に応じて FIFO の制約を緩めた派生形がある。

AWS のメッセージキュー

キューのデータ構造は、分散システムのメッセージングに直接応用される。

BFS (幅優先探索) でのキュー

循環キューは容量が固定なので、満杯になったときの振る舞いを先に決めておく必要がある。古い要素を上書きするか、追加そのものを拒否するかで意味が変わり、直近の記録だけ残せばよい用途なら上書き、取りこぼしを許さない用途なら拒否が妥当になる。

キューが最も素直に効く応用が幅優先探索である。訪問予定を到着順に処理すると、始点から近い順に探索が広がる。

function bfs(graph: Map<string, string[]>, start: string): string[] {
  const visited = new Set<string>();
  const queue = new Queue<string>();
  const result: string[] = [];

  queue.enqueue(start);
  visited.add(start);

  while (!queue.isEmpty()) {
    const node = queue.dequeue()!;
    result.push(node);
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.enqueue(neighbor);
      }
    }
  }
  return result;
}

スタックとの比較

対になる構造がスタックで、取り出す端がどちらかという 1 点だけが違う。

SQS FIFO の exactly-once には条件が付く。重複が排除されるのは同じ重複排除 ID を 5 分の重複排除期間内に送った場合で、それを過ぎた再送は別のメッセージとして扱われる。順序が守られるのもメッセージグループ ID の単位で、異なるグループ間の前後関係は保証されない。厳密な順序を求めて 1 つのグループへ集約すると、同時に処理できる本数もその分だけ減る。

選ぶときの基準

到着順に意味があるかどうかで判断する。順序が要件でなければ FIFO にこだわる理由はなく、待ち行列の長さだけを見ればよい。順序が要件なら、どの単位で順序を守るのかを先に決める。全体で 1 列にするのか、利用者ごとや注文ごとに列を分けるのかで、処理能力の上限が変わる。自前実装なら容量の上限を決めておくことも要る。上限のないキューは、入れる側が取り出す側より速いときにメモリを使い切るまで伸び続ける。