C++で優先キュー（プライオリティキュー）を実装する方法

通常のキュー（待ち行列）は、FIFO（First-In-First-Out：先入れ先出し）方式で動作するデータ構造です。要素の挿入は一方の端（末尾）から行い、削除はもう一方の端（先頭）から行います。そのため、最初に入った要素が必ず最初に取り出されます。

キューの基本操作

• EnQueue(int data)：末尾に要素を挿入する
• int DeQueue()：先頭から要素を削除する

一方、優先キュー（プライオリティキュー）はFIFOの原則には従いません。代わりに、各要素が「緊急度」に応じた優先度を持ちます。

• 同じ優先度を持つ要素同士は、FIFO（先入れ先出し）の順序で処理されます。
• 優先度の高い要素は、優先度の低い要素よりも先に処理されます。

クラスの設計方針

ここでは、連結リストを用いて優先キューを実装します。クラスPriority_Queueの擬似コードによる設計概要は以下の通りです。

Begin
    クラス Priority_Queue は以下の関数を持つ：
    関数 insert()：優先度付きで要素を優先キューに挿入する
        1) キューが空の場合、データをキューの先頭に挿入する。
        2) キューに既存ノードがある場合、新しいノードと同じ優先度を持つ
           ノード群の末尾に、かつ新しいノードより優先度が低いすべての
           ノードの手前に挿入する。
    関数 del()：キューから要素を削除する
    キューが完全に空の場合はアンダーフローを表示し、
    そうでなければ先頭要素を削除してフロントポインタを更新する。
End

C++による実装例

以下のコードでは、優先度の小さい値ほど高い優先度として扱われ、キューの先頭に近い位置へ挿入されます。メニュー形式の対話型プログラムとして、挿入・削除・表示・終了の操作を選択できます。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

struct n // ノードの宣言 {
    int p;       // 優先度
    int info;    // データ本体
    struct n *l; // 次のノードへのポインタ
};

class Priority_Queue {
    private:
        // 先頭ポインタ f を宣言し、NULL で初期化
        n *f;
    public:
        Priority_Queue() // コンストラクタ {
            f = NULL;
        }
        void insert(int i, int p) {
            n *t, *q;
            t = new n;
            t->info = i;
            t->p = p;
            if (f == NULL || p < f->p) {
                // 空のキュー、または最高優先度なら先頭に挿入
                t->l = f;
                f = t;
            } else {
                // 挿入位置を探索
                q = f;
                while (q->l != NULL && q->l->p <= p)
                    q = q->l;
                t->l = q->l;
                q->l = t;
            }
        }
        void del() {
            n *t;
            if (f == NULL) // キューが空の場合
                cout<<"Queue Underflow\n";
            else {
                t = f;
                cout<<"Deleted item is: "<<t->info<<endl;
                f = f->l;
                delete t;
            }
        }
        void show() // キューの内容を表示 {
            n *ptr;
            ptr = f;
            if (f == NULL)
                cout<<"Queue is empty\n";
            else {
                cout<<"Queue is :\n";
                cout<<"Priority Item\n";
                while(ptr != NULL) {
                    cout<<ptr->p<<" "<<ptr->info<<endl;
                    ptr = ptr->l;
                }
            }
        }
};

int main() {
    int c, i, p;
    Priority_Queue pq;
    do // switch文による操作の実行 {
        cout<<"1.Insert\n";
        cout<<"2.Delete\n";
        cout<<"3.Display\n";
        cout<<"4.Exit\n";
        cout<<"Enter your choice : ";
        cin>>c;
        switch(c) {
            case 1:
                cout<<"Input the item value to be added in the queue : ";
                cin>>i;
                cout<<"Enter its priority : ";
                cin>>p;
                pq.insert(i, p);
                break;
            case 2:
                pq.del();
                break;
            case 3:
                pq.show();
                break;
            case 4:
                break;
            default:
            cout<<"Wrong choice\n";
        }
    }
    while(c != 4);
    return 0;
}

実装のポイント

• insert()：新規ノードは、自分より優先度が高いノードの後ろ・同じ優先度のノードの末尾に配置されます。これにより、常に先頭から優先度順に並んだ状態が保たれます。
• del()：先頭ノードを取り出して削除するため、最も優先度の高い要素が常に最初に取得されます。
• show()：先頭から順に「優先度 データ」の形式で全要素を表示します。

実行結果

1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Input the item value to be added in the queue : 7
Enter its priority : 2
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Input the item value to be added in the queue : 6
Enter its priority : 1
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Input the item value to be added in the queue : 3
Enter its priority : 3
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Input the item value to be added in the queue : 4
Enter its priority : 3
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Queue is :
Priority Item
1 6
2 7
3 3
3 4
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 4

この実行例では、優先度1の「6」が最も先に並び、続いて優先度2の「7」、そして同じ優先度3を持つ「3」と「4」が挿入された順序で並んでいることが確認できます。これは、優先キューが「優先度順・同一優先度内ではFIFO」という規則に従って動作していることを示しています。