JavaScriptで優先キュー（プライオリティキュー）を作成する方法

優先キュー（プライオリティキュー）は、通常のキューとは異なり、各要素に優先度が割り当てられたデータ構造です。優先度の高い要素から順に取り出される仕組みのため、タスクスケジューリングやDijkstra法などのグラフ探索アルゴリズム、イベント処理システムなど、幅広い場面で活用されています。この記事では、JavaScriptを使って優先キューの基本クラスを実装する方法を解説します。

優先キュークラスに実装する機能一覧

今回作成するクラスには、以下の関数を実装していきます。

• enqueue(element)：キューに要素を追加する関数
• dequeue()：キューから要素を取り出す（削除する）関数
• peek()：キューの先頭にある要素を返す関数
• isFull()：キューの要素数が上限に達しているかどうかを確認する関数
• isEmpty()：キューが空かどうかを確認する関数
• clear()：すべての要素を削除する関数
• display()：配列の内容をすべて表示する関数

クラスの基本構造を定義する

まず、キューの最大サイズを受け取るコンストラクタと、後続の関数を実装する際に役立つヘルパー関数を備えたシンプルなクラスを定義することから始めましょう。

さらに、PriorityQueueクラスのプロトタイプの一部として、各ノードの「データ」と「優先度」を保持するための内部構造も定義する必要があります。スタックを実装したときと同様に、優先キューも配列（Array）を使って実装します。

コード例

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;
    }
}
// キューに新しいノードを作成するために使用する内部クラス
// 各要素は「データ」と「優先度」を持つ
PriorityQueue.prototype.Element = class {
    constructor(data, priority) {
        this.data = data;
        this.priority = priority;
    }
}

isFull関数とisEmpty関数の解説

上記のコードでは、キューが満杯か空かを判定するためのisFull関数とisEmpty関数という2つの関数も定義しました。

isFull関数は、コンテナ配列の長さがmaxSize以上であるかどうかをチェックし、その結果（true / false）を返すだけのシンプルな実装です。

isEmpty関数は、コンテナ配列のサイズが0であるかどうかを確認します。

これらの関数は、enqueueやdequeueなど、他の操作を定義する際の事前チェックとして非常に役立ちます。たとえば、満杯のキューにこれ以上要素を追加できないようにしたり、空のキューから要素を取り出そうとするエラーを防いだりすることができます。

以降で定義していく関数は、すべてこのPriorityQueueクラスの中に実装していきます。