キューとは？
キュー(Queue)は、先に入ったものが先に出る(FIFO, First-In-First-Out) 構造です。チケット売り場に並ぶ人を思い浮かべてください — 最初に並んだ人が最初にチケットを買います。
後ろへ入れる操作を enqueue、前から取り出す操作を dequeue と呼びます。BFS(幅優先探索)、ジョブ待ち行列、プリンタキュー、ネットワークバッファなど「到着順に処理」が必要な場所で登場します。
スタックとの違い
| スタック | キュー | |
|---|---|---|
| 規則 | LIFO(後入先出) | FIFO(先入先出) |
| 入れる | push(最上段) | enqueue(後ろ) |
| 出す | pop(最上段) | dequeue(前) |
スタックは「最後に積んだもの」から、キューは「最初に入れたもの」から出ます。
核心は循環キュー(circular queue)
配列でキューを作るときの典型的な落とし穴は、前から取り出すたびに残りを1つずつ詰めることで、これだとdequeueがO(n)になります。
解決策は前(front)・後(rear)インデックスを別々に持ち、末尾に達したら0へ戻す循環キューです。要素を実際に動かさず (i + 1) % capacity でインデックスだけ回せば、enqueue・dequeueの両方がO(1)になります。
動作原理
ステップ1. front = rear = 0、サイズ0で始めます。
ステップ2. enqueue(x): arr[rear] = x のあと rear = (rear + 1) % cap、サイズ+1。(満杯なら拒否)
ステップ3. dequeue(): arr[front] を返し front = (front + 1) % cap、サイズ-1。(空なら拒否)
ステップ4. 満杯/空の区別: frontとrearだけでは区別しにくいので、別にサイズ(size)変数を持つのが安全です。
AlgoNoteの可視化は、front・rearポインタが循環して回る様子とキューが満ちて空になる過程を示します。
時間計算量と空間計算量
| 操作 | 計算量 |
|---|---|
| enqueue / dequeue | O(1) |
| 先頭確認(peek) | O(1) |
| 空間 | O(n) |
例で追ってみる
容量3の循環キュー:
- •enqueue A, B → [A, B, _]、front=0、rear=2
- •dequeue → A を返す、front=1
- •enqueue C, D → Cはインデックス2、Dは
(3)%3=0の位置へ → [D, B, C]、インデックスが循環
先に入れたA・Bが先に出る順序がそのまま保たれます。
よくあるミス
- •前からのshift:
arr.shift()のような操作はO(n)。フロントインデックスや循環キュー、またはデック(deque)を使いましょう。 - •空キューの処理: dequeue前に空かを確認しないと不正な値を読みます。
- •満杯判定: size変数なしでfront==rearだけ見ると「満杯」と「空」を混同します。
AlgoNoteで直接確認しましょう
要素が後ろから入り前から出て、front・rearポインタが循環する過程をAlgoNoteでステップごとに確認できます。