JavaScriptで実装するPriorityQueue(優先度付きキュー)クラスの完全ガイド

優先度付きキュー(Priority Queue)は、通常のFIFO(先入れ先出し)キューとは異なり、各要素が持つ「優先度」に基づいて処理順序が決まるデータ構造です。優先度の高い要素から順に取り出されるため、タスクスケジューリング、ダイクストラ法などのアルゴリズム、イベント処理システムなどで広く活用されています。ここでは、JavaScriptによるPriorityQueueクラスの完全な実装例を紹介します。

PriorityQueueクラスの完全な実装

以下がPriorityQueueクラスの完全な実装コードです。要素は内部で常に優先度順にソートされた状態で保持されます。

class PriorityQueue {
    constructor(maxSize) {
        // サイズが指定されない場合はデフォルト値を設定
        if (isNaN(maxSize)) {
            maxSize = 10;
        }
        this.maxSize = maxSize;
        // キューの値を格納する配列を初期化
        this.container = [];
    }
    // 開発時に全要素を表示するためのヘルパー関数
    display() {
        console.log(this.container);
    }
    // キューが空かどうかを判定
    isEmpty() {
        return this.container.length === 0;
    }
    // キューが満杯かどうかを判定
    isFull() {
        return this.container.length >= this.maxSize;
    }
    enqueue(data, priority) {
        // キューが満杯かどうかをチェック
        if (this.isFull()) {
            console.log("Queue Overflow!");
            return;
        }
        let currElem = new this.Element(data, priority);
        let addedFlag = false;
        // 優先度に応じた適切な位置へ要素を挿入
        for (let i = 0; i < this.container.length; i++) {
            if (currElem.priority < this.container[i].priority) {
                this.container.splice(i, 0, currElem);
                addedFlag = true; break;
            }
        }
        if (!addedFlag) {
            this.container.push(currElem);
        }
    }
    dequeue() {
        // 空かどうかをチェック
        if (this.isEmpty()) {
            console.log("Queue Underflow!");
            return;
        }
        return this.container.pop();
    }
    peek() {
        if (this.isEmpty()) {
            console.log("Queue Underflow!");
            return;
        }
        return this.container[this.container.length - 1];
    }
    clear() {
        this.container = [];
    }
}
// キューのノードを作成するための内部クラス
// 各要素はデータと優先度を持つ
PriorityQueue.prototype.Element = class {
    constructor(data, priority) {
        this.data = data;
        this.priority = priority;
    }
};

各メソッドの解説

constructor(maxSize)

コンストラクタではキューの最大サイズを受け取ります。引数が渡されなかった場合や数値以外の値が渡された場合(isNaNで判定)は、デフォルト値として10が設定されます。また、キューの本体となる空の配列containerを初期化しています。

enqueue(data, priority)

新しい要素をキューに追加するメソッドです。まずisFull()で満杯かどうかを確認し、満杯の場合は「Queue Overflow!」と表示して処理を終了します。そうでなければ、既存の要素と優先度を先頭から順に比較し、自分より優先度の数値が大きい要素の直前にspliceで挿入します。これにより配列は常に優先度の昇順で維持され、数値が大きいほど優先度が高い扱いになります。挿入箇所が見つからなかった場合は単純に末尾へ追加します。

dequeue()

キューから最も優先度の高い要素を取り出して返します。内部的には配列の末尾からpop()しているだけですが、enqueueの段階で優先度順に並んでいるため、必ず最も優先度の高い要素が取得できる仕組みです。キューが空の場合は「Queue Underflow!」と表示します。

peek()

要素を取り出さずに、最も優先度の高い要素(配列の末尾)を参照するメソッドです。次にどの要素が処理されるのかを事前に確認したい場合に便利です。

その他のユーティリティメソッド

display()は開発中のデバッグ用にキューの中身をコンソールへ出力します。isEmpty()とisFull()はそれぞれキューが空か・満杯かを真偽値で返し、clear()は全要素を削除してキューを初期状態に戻します。

また、PriorityQueue.prototype.Elementとして定義されている内部クラスは、キューに格納する個々のノードを生成するためのものです。各ノードはdata(本体のデータ)とpriority(優先度)という2つのプロパティを持ちます。

使用例

const pq = new PriorityQueue();
pq.enqueue("メール送信", 1);
pq.enqueue("エラー処理", 3);
pq.enqueue("ログ出力", 2);

console.log(pq.dequeue().data); // 「エラー処理」(優先度3が最高)

実装上の注意点

この実装はシンプルで理解しやすい反面、enqueueのたびに先頭から線形探索を行うため、計算量はO(n)になります。数千件以上の要素を扱うケースでは、二分ヒープ(binary heap)を用いた実装(O(log n))に置き換えることで大幅に効率が向上します。

なお、クラス内で別のメソッドを呼び出す際はthis.isEmpty()のようにthisを付ける必要があります。thisを付け忘れるとReferenceErrorが発生するので注意しましょう。