C++で双方向リンクリストを使用した優先度付きキューの実装

整数値のデータと優先度が与えられ、その優先度に従って双方向リンクリスト(doubly linked list)を作成し、結果を表示することが本記事の課題です。

優先度付きキューとは?

キュー(Queue)はFIFO(First In, First Out:先入れ先出し)方式のデータ構造であり、最初に挿入された要素が最初に取り出されます。優先度付きキュー(Priority Queue)は、要素の優先度に応じて挿入や削除を行えるキューの一種です。キュー、スタック、リンクリストなどのデータ構造を使って実装でき、本記事では双方向リンクリストを用います。

優先度付きキューは、次のルールに従って動作します。

• 優先度が最も高いデータ(要素)は、優先度の低いものよりも先に処理される。
• 2つの要素が同じ優先度を持つ場合は、リストに追加された順番どおりに処理される。

ノードの構成

優先度付きキューを実装するための双方向リンクリストのノードは、主に次の4つの情報で構成されます。

• データ(info):整数値を格納します。
• 次ノードへのアドレス(next):次のノードのアドレスを格納します。
• 前ノードへのアドレス(prev):前のノードのアドレスを格納します。
• 優先度(priority):整数値の優先度を格納します。0〜10の範囲を想定し、0が最も高い優先度、10が最も低い優先度を表します。

入力例と出力例

入力:

出力:

アルゴリズム

全体の処理の流れは次のとおりです。

開始
ステップ1:構造体Nodeを宣言する
    info(データ)とpriority(優先度)を宣言する
    struct Node *prev, *next を宣言する
ステップ2:関数 push(Node** fr, Node** rr, int n, int p)
    Node* news = (Node*)malloc(sizeof(Node)) で新しいノードを確保する
    news->info = n を設定する
    news->priority = p を設定する
    もし *fr == NULL ならば(リストが空の場合)
        *fr = news とする
        *rr = news とする
        news->next = NULL とする
    そうでなく p <= (*fr)->priority ならば(先頭より優先度が高い場合)
        news->next = *fr とする
        (*fr)->prev = news->next とする
        *fr = news とする
    そうでなく p > (*rr)->priority ならば(末尾より優先度が低い場合)
        news->next = NULL とする
        (*rr)->next = news とする
        news->prev = (*rr)->next とする
        *rr = news とする
    それ以外の場合(中間に挿入する場合)
        Node* start = (*fr)->next とする
    start->priority > p の間繰り返す
        start = start->next とする
        (start->prev)->next = news とする
        news->next = start->prev とする
        news->prev = (start->prev)->next とする
        start->prev = news->next とする
ステップ3:関数 int peek(Node *fr)
    fr->info を返す
ステップ4:関数 bool isEmpty(Node *fr)
    (fr == NULL) を返す
ステップ5:関数 int pop(Node** fr, Node** rr)
    Node* temp = *fr とする
    res = temp->info とする
    (*fr) = (*fr)->next とする
    free(temp) でメモリを解放する
    もし *fr == NULL ならば
        *rr = NULL とする
    res を返す
ステップ6:関数 int main()
    Node *front = NULL, *rear = NULL を宣言して初期化する
    push(&front, &rear, 4, 3) を呼び出す
    push(&front, &rear, 3, 2) を呼び出す
    push(&front, &rear, 5, 2) を呼び出す
    push(&front, &rear, 5, 7) を呼び出す
    push(&front, &rear, 2, 6) を呼び出す
    push(&front, &rear, 1, 4) を呼び出す
    pop(&front, &rear) の戻り値を出力する
    peek(front) の戻り値を出力する
終了

C++での実装例

#include <bits/stdc++.h>
using namespace std;

// 双方向リンクリストのノード
struct Node {
    int info;       // データ
    int priority;   // 優先度
    struct Node *prev, *next;
};

// 新しいノードを優先度に応じて挿入する
void push(Node** fr, Node** rr, int n, int p) {
    Node* news = (Node*)malloc(sizeof(Node));
    news->info = n;
    news->priority = p;

    // リンクリストが空の場合
    if (*fr == NULL) {
        *fr = news;
        *rr = news;
        news->next = NULL;
    } else {
        // 新しいノードの優先度が先頭ノード以下なら先頭に挿入
        if (p <= (*fr)->priority) {
            news->next = *fr;
            (*fr)->prev = news->next;
            *fr = news;
        } else if (p > (*rr)->priority) {
            // 末尾ノードより優先度が低ければ末尾に挿入
            news->next = NULL;
            (*rr)->next = news;
            news->prev = (*rr)->next;
            *rr = news;
        } else {
            // 挿入すべき位置を探す
            Node* start = (*fr)->next;
            while (start->priority > p)
                start = start->next;
            (start->prev)->next = news;
            news->next = start->prev;
            news->prev = (start->prev)->next;
            start->prev = news->next;
        }
    }
}

// 先頭の値を参照する
int peek(Node *fr) {
    return fr->info;
}

// キューが空かどうかを判定する
bool isEmpty(Node *fr) {
    return (fr == NULL);
}

// 先頭の要素を取り出す
int pop(Node** fr, Node** rr) {
    Node* temp = *fr;
    int res = temp->info;
    (*fr) = (*fr)->next;
    free(temp);
    if (*fr == NULL)
        *rr = NULL;
    return res;
}

// メイン関数
int main() {
    Node *front = NULL, *rear = NULL;
    push(&front, &rear, 4, 3);
    push(&front, &rear, 3, 2);
    push(&front, &rear, 5, 2);
    push(&front, &rear, 5, 7);
    push(&front, &rear, 2, 6);
    push(&front, &rear, 1, 4);
    printf("%d\n", pop(&front, &rear));
    printf("%d\n", peek(front));
    return 0;
}

実行結果

5
3

解説

このプログラムでは、優先度の数値が小さいほど高い優先度として扱われます。挿入時には、新規ノードの優先度をまず先頭・末尾ノードと比較し、どちらにも当てはまらない場合はリストを走査して適切な位置に挿入します。同じ優先度の要素は先頭側に挿入されるため、追加された順序が保たれる仕組みです。

pop()は先頭ノードを取り出してメモリを解放し、peek()は先頭ノードの値のみを参照します。挿入操作の計算量は最悪でO(n)となりますが、先頭要素の参照や削除はO(1)で高速に行える点が、この実装の特徴です。