キュークラス（enqueue と dequeue）｜コードで実践

キュークラス（enqueue と dequeue）

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

enqueue は append で O(1)、dequeue は pop(0) で O(n) です

キュー (queue) は、最初に入れたものを最初に取り出す データ構造です

キュー に必要な要素を洗い出します

キュークラスとは

FIFO のキューをクラスで実装し、queueOps(ops) で enqueue / dequeue の操作列を適用した最終状態を配列で返す。

キュー (queue) は、最初に入れたものを最初に取り出す データ構造です。列に並ぶのと同じで、先に並んだ人から順番にサービスを受けます。略して FIFO (First In, First Out) と呼びます。前のレッスンで扱った スタック (LIFO) と対をなす存在で、OS のタスクスケジューラ、プリンタ のジョブ管理、BFS (幅優先探索) などで広く使われます。

キューは「先に入れたものが先に出る」、つまり FIFO の代表的なデータ構造だ。

クラスでキューを設計する

キュー に必要な要素を洗い出します。

属性 — 中身を保持する 配列 (内部リスト)
メソッド — enqueue(x) で末尾に追加、dequeue() で先頭を取り出す、peek() で先頭を覗く、size() で要素数を返す

Python

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, x):
        self.items.append(x)

    def dequeue(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)

enqueue は append で O(1)、dequeue は pop(0) で O(n) です。要素数が大きい場合は collections.deque を使うと dequeue も O(1) になりますが、本レッスンでは挙動の理解を優先して list で書きます。

キューの動きを図で理解

diagram (will load when visible)

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

左から並び、左から抜けていく

左から並び、左から抜けていく。これが キュー の基本動作です。スタック (右から積み、右から抜ける) との違いを意識して覚えましょう。

JavaScript での実装

JavaScript

class Queue {
  constructor() { this.items = []; }
  enqueue(x) { this.items.push(x); }
  dequeue() { return this.items.shift(); }
  size() { return this.items.length; }
}

JavaScript の Array には shift メソッドがあり、これが dequeue に相当します。Array.prototype.shift も O(n) で内部要素を全部ずらします。push は O(1)。

スタックとの比較

どちらも「片側から入れる」のは同じ。違いは「出す側」だ。スタック は同じ側、キュー は反対側から出す。

操作	スタック	キュー
追加	`push` (末尾)	`enqueue` (末尾)
削除	`pop` (末尾)	`dequeue` (先頭)
規則	LIFO	FIFO
用途	関数呼び出し / Undo	タスク待ち行列 / BFS

このレッスンでやること

関数 queueOps(ops) を実装します。ops は ["enqueue", 1] / ["dequeue"] の操作列を表す 配列の配列 です。順番に Queue クラスに適用し、最後に キュー の中身を 配列 として返します。例として [["enqueue", 1], ["enqueue", 2], ["dequeue"], ["enqueue", 3]] を渡すと、内部状態は [2, 3] になります。

キューが活躍する場面

キュー は身近な「順番待ち」の概念をプログラムに落とし込んだものです。具体的な使い所を挙げます。

BFS (幅優先探索) — グラフや木を「近い順」で訪問するのに必須
タスクスケジューラ — OS がプロセスを公平に実行する仕組み
メッセージキュー — 非同期処理で 生産者 から 消費者 へ仕事を流す
プリンタジョブの管理 — 先に入れた印刷ジョブから順に処理する

後の章で扱う グラフの BFS では、キュー を使って「最短距離」を求めます。本レッスンでの実装感覚が、そのまま BFS の理解に直結します。

スタック は深く潜るときに使い、キュー は広く広がるときに使う、と覚えておくと、DFS / BFS でどちらを選ぶか迷わない。

よくある間違い

スタック と キュー を混同して、末尾から取り出す 実装にしてしまう。
dequeue で pop() (引数なし、末尾を取る) と書く。正しくは pop(0) (先頭を取る)。
JavaScript で shift の代わりに pop を使ってしまう。

やってみよう

queueOps(ops) を実装してください。Queue クラスを内部で定義し、enqueue / dequeue メソッドを実装してから使う構成にします。dequeue の戻り値は捨てて構いません。最終的に内部の キュー を 配列 として返します。dequeue が空キューに来ることはない、と仮定して大丈夫です。

よくある質問

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）