キュー

キューとは

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

計算量

計算量を以下にまとめる。

操作	計算量
enqueue (追加)	O(1)
dequeue (取り出し)	O(1)
peek (先頭を参照)	O(1)

TypeScript での実装

TypeScript での実装のコード例を示す。

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() は O(n) のため、大量のデータを扱う場合は Map ベースの実装が効率的だ。

キューの種類

キューの種類を以下にまとめる。

種類	特徴	用途
FIFO キュー	先入れ先出し	メッセージキュー、タスクキュー
優先度キュー	優先度順に取り出し	スケジューリング、ダイクストラ法
双方向キュー (Deque)	両端から追加・取り出し	スライディングウィンドウ
循環キュー	固定サイズ、末尾が先頭に繋がる	バッファ、ログの保持

AWS のメッセージキュー

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

サービス	種類	特徴
SQS Standard	FIFO ではない (ベストエフォート順序)	高スループット、at-least-once
SQS FIFO	厳密な FIFO	順序保証、exactly-once
Kinesis	ストリーム (シャード内 FIFO)	リアルタイム処理、複数コンシューマー

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

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;
}

スタックとの比較

スタックとの主な違いを以下に比較する。

データ構造	順序	用途
キュー (FIFO)	先入れ先出し	メッセージキュー、BFS
スタック (LIFO)	後入れ先出し	関数呼び出し、Undo、DFS

キューを扱う関連書籍も多い。