sko.kr

アルゴリズム - 9. キュー

algorithmsdata-structuresqueuelinked-list
By sko•10/7/2025•6 min read

キューを使うタイミング

先入れ先出し（FIFO）順序でアイテムを処理する必要がある場合にキューを使用します - 最初に追加されたアイテムが最初に削除されます。タスクスケジューリングに最もよく使用されますが、以下の場合に不可欠です：

  • 幅優先探索（BFS）（クラシックな使用例）
  • タスクスケジューリング（到着順に処理）
  • メッセージキューイングシステム（メッセージの順序を維持）
  • プリントスプーラー（印刷ジョブを提出順に処理）
  • コールセンターシステム（受信順に通話を処理）
  • アイテムが到着順に処理される必要がある公平な順序付けを必要とするあらゆる問題

例題

カスタマーサービスシステム：コーヒーショップでは、到着順にお客様にサービスを提供する必要があります。お客様は異なる時間に列に加わり、公平にサービスを受ける必要があります。

  • お客様Aが午前9:00に到着
  • お客様Bが午前9:02に到着
  • お客様Cが午前9:05に到着
  • お客様Dが午前9:07に到着

答え：キューを使用することで、お客様Aが最初にサービスを受け、次にB、次にC、次にDという順序が保証されます - FIFO順序による完璧な公平性が維持されます。

最も重要な洞察

キューは追加ポイント（後部）と削除ポイント（前部）を分離することで順序を維持します - そして2つのポインターを使用して両端を追跡することで、アイテムが入った正確な順序で出ることを保証しながらO(1)操作を実現します。

メンタルノート：キューの天才的な点は、その2ポインター設計にあります。削除（デキュー/シフト）時は前部とのみ、追加（エンキュー/プッシュ）時は後部とのみやり取りします。この関心の分離により、トラバースや再編成が不要になります - 構造自体がその二重端アクセスパターンを通じて自動的に順序を維持します。

意思決定フレームワーク

ダミーノードパターンを使用すると、操作が非常に一貫性のあるものになります：

  • プッシュ：常に後部に追加 - 特別なケースは一切ありません！
  • シフト：常にdummyHead.nextから削除（存在する場合）
  • エッジケースの簡略化：チェックは1つだけ - dummyHead.nextがnullか？（空のキュー）

コード

// 列にいる各お客様は、その値と次の人を含む「ノード」です
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// ダミーノードによるよりクリーンな実装 - nullチェック不要！
class Queue {
  constructor() {
    // 常に存在するダミーノードを作成（「ここから列が始まります」の看板のよう）
    this.dummyHead = new ListNode(null);
    this.rear = this.dummyHead; // 最初は、rearはダミーを指します
  }

  // 列の最後に新しいお客様を追加
  push(value) {
    const newCustomer = new ListNode(value);

    // ステップ1：現在の最後の人を新しいお客様につなげる
    this.rear.next = newCustomer;

    // ステップ2：rearポインターを新しい最後の人を指すように更新
    // 「最後の人」の看板を新しいお客様に移動するように考えてください
    this.rear = newCustomer;
    // これでthis.rearは古いものではなく、新しい最後のノードを指します
  }

  // 前にいるお客様にサービスを提供し、列から削除
  shift() {
    // 意思決定フレームワーク：列が空かチェック（ダミーの後に誰もいない）
    if (this.dummyHead.next === null) {
      return undefined;
    }

    // 最初の実際のお客様は常にdummyHead.nextにいます
    const firstCustomer = this.dummyHead.next;
    const servedValue = firstCustomer.value;

    // 列を前に進める - 最初のお客様をスキップ
    // これによりdummyHeadが2番目のお客様（いなければnull）を直接指すようになります
    this.dummyHead.next = firstCustomer.next;
    // 基本的にfirstCustomerをチェーンから「切り取っています」

    // 意思決定フレームワーク：最後のお客様を削除した場合、rearを更新
    if (this.dummyHead.next === null) {
      this.rear = this.dummyHead; // 空の時はrearをダミーにリセット
    }

    return servedValue;
  }

  // サービスせずに次の人を見る
  peek() {
    if (this.dummyHead.next === null) {
      return undefined;
    }
    return this.dummyHead.next.value;
  }

  // 列が空かチェック
  isEmpty() {
    return this.dummyHead.next === null;
  }

  // キューを視覚化（デバッグに便利）
  display() {
    const items = [];
    let current = this.dummyHead.next;

    while (current !== null) {
      items.push(current.value);
      current = current.next;
    }

    return items.join(" → ");
  }
}

// 例：コーヒーショップの列
const coffeeLine = new Queue();

// 朝のラッシュ - お客様が列に加わる
coffeeLine.push("Alice");
coffeeLine.push("Bob");
coffeeLine.push("Charlie");

console.log("列:", coffeeLine.display()); // 'Alice → Bob → Charlie'
console.log("列の先頭:", coffeeLine.peek()); // 'Alice'

// お客様へのサービス開始（FIFO順序）
console.log("サービス中:", coffeeLine.shift()); // 'Alice'
console.log("列:", coffeeLine.display()); // 'Bob → Charlie'

// サービス中に新しいお客様が到着
coffeeLine.push("Diana");
console.log("列:", coffeeLine.display()); // 'Bob → Charlie → Diana'

console.log("サービス中:", coffeeLine.shift()); // 'Bob'
console.log("サービス中:", coffeeLine.shift()); // 'Charlie'
console.log("サービス中:", coffeeLine.shift()); // 'Diana'
console.log("サービス中:", coffeeLine.shift()); // undefined (空)

ポインターの再割り当てを理解する

this.rear = newCustomerを行うと、rearポインターを移動して別のノードを指すようにしています：

push('Alice')前：
dummyHead → null
rear ↑ (dummyHeadを指す)

this.rear.next = newCustomerの後：
dummyHead → Alice → null
rear ↑ (まだdummyHeadを指す)

this.rear = newCustomerの後：
dummyHead → Alice → null
            rear ↑ (今はAliceを指す)

重要な洞察：this.rearは「現在どのノードが最後か」を教えてくれる単なる参照/ポインターです。this.rear = newCustomerと書くとき、ノードを変更しているのではありません - 新しい最後のノードを指すように参照を更新しているだけです。これは「列の最後」の看板を一人から別の人に移動するようなものです。

シフトのポインターバイパスを理解する

this.dummyHead.next = firstCustomer.nextを行うと、最初のお客様をバイパスしています：

shift()前：
dummyHead → Alice → Bob → Charlie → null
            ↑ firstCustomerはここを指す

const firstCustomer = this.dummyHead.nextの後：
Aliceへの参照を保存

this.dummyHead.next = firstCustomer.nextの後：
dummyHead → Bob → Charlie → null
(Aliceはバイパスされました - もうチェーンにいません！)

this.dummyHead.next = firstCustomer.nextという行は、「Aliceが指していたもの（Bob）に、ダミーが直接指すようにする」と言っています。これによりAliceは効果的にチェーンから削除されます - 彼女は「サービスを受けた」ので、もう列にはいません。

ダミーノードがよりクリーンにする理由

ダミーノードは決して動かない「ここから列が始まります」の看板のように機能します。これにより特別なケースが排除されます：

ダミーノードなし：

  • 最初の要素を追加する前にキューがnullかチェックする必要がある
  • frontとrearの両方がnullである必要がある
  • 最初の要素と後続の要素で異なるロジックが必要

ダミーノードあり：

  • ダミーは常に存在するため、構造自体のnullチェックが不要
  • 追加は常に同じ：rearに接続、rearを更新
  • 削除は常に同じ：dummyHead.nextから取得
  • 必要なチェックはキューが空かどうか（dummyHead.next === null）だけ

疑問を解消する

よくある疑問：「なぜキューに連結リストを使うのですか？配列を使ってインデックスを追跡するだけではダメですか？その方が簡単ではないでしょうか？」

これは重要なパフォーマンスの考慮事項を浮き彫りにする優れた質問です。両方のアプローチを検討してみましょう。

なぜ配列の方が簡単だと思うかもしれない

配列でキューを実装することを考えてみてください：

  • 「配列はインデックスアクセスを提供 - より直接的に見える」
  • 「push()で追加し、shift()で削除するだけでよい」
  • 「ノードポインターやnext参照を管理する必要がない」

この考えが重要な問題を見逃している理由

重要な認識：配列ベースのキューには隠れたパフォーマンスの罠があります！

配列実装で何が起こるかを追跡してみましょう：

初期： [1, 2, 3, 4, 5]

デキュー（前から削除）：
ステップ1：インデックス0の要素を削除： [_, 2, 3, 4, 5]
ステップ2：残りの要素をすべて左にシフト： [2, 3, 4, 5]
        - インデックス1の要素がインデックス0に移動
        - インデックス2の要素がインデックス1に移動
        - インデックス3の要素がインデックス2に移動
        - インデックス4の要素がインデックス3に移動

パフォーマンスの災害：すべてのデキュー操作で残りのすべての要素をシフトする必要があり、O(1)ではなくO(n)になります！

具体例：パフォーマンス比較

1000個のアイテムを持つキューでの操作を比較してみましょう：

配列ベースのキュー：

  • エンキュー：O(1) - 末尾に追加するだけ
  • デキュー：O(n) - 999個の要素をシフトする必要がある！
  • 1000個すべてのアイテムの処理：合計O(n²)操作

連結リストキュー：

  • エンキュー：O(1) - rearポインターを更新
  • デキュー：O(1) - frontポインターを更新
  • 1000個すべてのアイテムの処理：合計O(n)操作

循環配列の代替案

「でも待って」とあなたは言うかもしれません、「frontとrearのインデックスを持つ循環配列を使うのはどうですか？」

class ArrayQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.front = 0;
    this.rear = -1;
    this.size = 0;
    this.capacity = capacity;
  }
}

このアプローチには独自の問題があります：

  • 固定容量：最大サイズを事前に決定する必要がある
  • 無駄なスペース：使用されていない配列スロットがメモリを消費
  • リサイズの複雑さ：キューを拡大するにはすべての要素をコピーする必要がある
  • インデックスの折り返しロジック：モジュロ演算を使用したより複雑なメンタルモデル

連結リストが最適な選択である理由

連結リスト実装はこれらすべての問題をエレガントに解決します：

  1. 定数時間操作：エンキューとデキューの両方が常にO(1)
  2. 動的サイズ：必要に応じて拡大縮小
  3. メモリ効率的：実際に使用されるものだけを割り当てる
  4. シンプルなメンタルモデル：削除用のfrontポインター、追加用のrearポインター
  5. シフトやコピーなし：ノードはその場にとどまる；ポインターのみが変更

保証：構造の端（中央ではない）にのみ触れ、ポインターの更新がO(1)操作であるため、必要なメモリだけを使用しながら、すべてのコア操作で定数時間の複雑さを維持します。

2ポインター連結リスト設計は単なる実装の詳細ではありません - それは、意図されたFIFO目的に対してキューを効率的にする基本的なメカニズムです！

← Back to Blog