キュー (enqueue / dequeue) を実装する｜コードで実践

キュー (enqueue / dequeue) を実装する

このレッスンで分かること

配列だけで FIFO を作ると dequeue が O(n)

配列だけで素朴に実装するなら、enqueue は append / push で末尾追加、dequeue は pop(0) / shift で先頭削除になります

キューに必要な操作は enqueue (push) と dequeue (pop) の 2 つだけです

キュー (enqueue / dequeue) を実装するとは

先入れ先出し (FIFO) のキューを enqueue / dequeue の操作シーケンスで動かし、最終状態を配列で返す。

前のレッスンでは スタック (LIFO) を扱いました。今度はその対になるデータ構造、キュー (queue) です。キューは 先に入れたものが先に出る 構造、つまり FIFO (First In, First Out) です。レジの列、プリンタの印刷待ち、メッセージキュー、BFS (幅優先探索) の管理など、現実でも CS でも応用先がたくさんあります。

本レッスンでは、初期キューに対して enqueue 5 enqueue 3 dequeue のような操作列を順番に実行し、最後に残ったキューを配列として返します。enqueue は 末尾に追加、dequeue は 先頭から取り出す が基本ルールです。

キューは FIFO。先に並んだお客さんから順番に処理する、これが全て。

操作は 2 つだけ

キューに必要な操作は enqueue (push) と dequeue (pop) の 2 つだけです。本問では、操作列は ["enq", 5] ["deq"] という配列の配列で渡されます。空のキューに dequeue が来たら無視するルールです。

配列だけで素朴に実装するなら、enqueue は append / push で末尾追加、dequeue は pop(0) / shift で先頭削除になります。ただし 先頭削除 は要素を 1 つずつずらすため O(n) です。要素数が多い実戦では Python の collections.deque や JavaScript の二重リンクリストなど、O(1) で先頭削除できる構造を使うのが定番です。今回は学習目的なので、配列の先頭 を dequeue する素直な書き方で十分です。

キューはスタックと違って 両端を触る。素朴な配列だと dequeue が O(n) になる点に注意。

動きを図で追う

diagram (will load when visible)

図のポイント (テキスト併記)

最初は []、enq 5 で [5]、enq 3 で [5, 3]、deq で [3] (先頭の 5 が出ていく)、enq 9 で [3, 9] です

最初は []、enq 5 で [5]、enq 3 で [5, 3]、deq で [3] (先頭の 5 が出ていく)、enq 9 で [3, 9] です。先頭が古い、末尾が新しい という向きを最後まで意識しましょう。

Python での実装

Python

def queueOps(initial, operations):
    queue = list(initial)
    for op in operations:
        if op[0] == 'enq':
            queue.append(op[1])
        elif op[0] == 'deq':
            if queue:
                queue.pop(0)
    return queue

pop(0) で先頭を取り出します。append で末尾に追加します。空キューでの deq は無視。これだけで FIFO の最小実装ができます。

JavaScript での実装

JavaScript

function queueOps(initial, operations) {
  const queue = [...initial];
  for (const op of operations) {
    if (op[0] === 'enq') {
      queue.push(op[1]);
    } else if (op[0] === 'deq') {
      if (queue.length > 0) queue.shift();
    }
  }
  return queue;
}

Array.prototype.shift() で先頭削除。これは内部的には全要素を 1 つずつずらすので、要素数が多いと遅くなります。実戦では Map を使った疑似 Deque や Linked List を検討します。

計算量

本実装では enqueue は O(1)、dequeue は 配列の先頭削除 なので O(n)、全体は最悪 O(n^2) になります。要素数が数千程度ならまったく問題ありません。それ以上になると collections.deque のような両端キューを使い、dequeue も O(1) にするのが定番です。今回はあくまで「キューの考え方を掴む」段階なので、簡潔さを優先します。

配列だけで FIFO を作ると dequeue が O(n)。本格的な用途では Deque を使うべし。

よくある間違い

1 つ目は 先頭と末尾を逆に扱う ケースです。dequeue を末尾から取ってしまうとそれはスタックと同じ動作になります。「先頭が古いお客さん」というイメージを忘れずに。

2 つ目は 空キューでの dequeue です。pop(0) を空配列に呼ぶと IndexError になります (Python)。JavaScript の shift() は undefined を返しますが、無音で進むので別のバグを生みます。必ず空チェックを入れます。

3 つ目は 入力を破壊 してしまうケース。queue = initial で参照を共有すると、呼び出し元の配列も書き換わります。スタック編と同じく list(initial) などでコピーを取りましょう。

やってみよう

initial = []、operations = [["enq", 1], ["enq", 2], ["deq"], ["enq", 3]] を手で追って、結果が [2, 3] になることを確認する。
operations が [["deq"], ["deq"]] だけだったら、initial = [] の結果が [] で済むことを確認する。
dequeue を O(1) で実装するために、Python の collections.deque を使ったバージョンも書いてみる。
スタック (前のレッスン) との 対応関係 を整理する。逆順にすればキューになるか、それとも別物か?

よくある質問

Q. キューとスタックの違いは？

A. キューは FIFO（先に入れたものから取り出す）、スタックは LIFO（後に入れたものから取り出す）です。順番に処理したいタスク管理は queue、後戻り可能な処理は stack というイメージで使い分けます。BFS は queue、DFS は stack を使います。

Q. Java での実装は何が良いですか？

A. ArrayDeque を Queue として使うのが最も高速です。LinkedList も Queue を実装していますが、メモリ効率・参照速度ともに ArrayDeque が優位です。並行アクセスが必要なら ConcurrentLinkedQueue / LinkedBlockingQueue を選んでください。

Q. 優先度付きキューはいつ使う？

A. 「常に最小（最大）の要素を取り出したい」場合に使います。タスクスケジューラ、ダイクストラ法、A* 探索などが代表例です。Java は PriorityQueue、Python は heapq モジュール、JS は手書きヒープが必要です。

次のレッスン

次は カッコのバランス判定 (スタック応用) に進みましょう。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

キューの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. キューとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

キュー (enqueue / dequeue) を実装する