C++のデキュー（両端キュー）と優先度付きキューの基本と使い方

キュー（Queue）は、FIFO（First In First Out：先入れ先出し）方式で動作するデータ構造として広く知られています。キューにはいくつかの派生形が存在し、その代表的なものが「デキュー（Dequeue：両端キュー）」と「優先度付きキュー（Priority Queue）」です。

デキュー（両端キュー）とは

デキューは、文字どおり「両端からアクセスできるキュー（Double Ended Queue）」のことです。front（先頭）とrear（末尾）のポインタの組み合わせが2組あり、一方のペアは左側から、もう一方のペアは右側からキューを管理します。この構造では、両端のどちらからでも要素の挿入・削除が可能という特徴があります。

ここでは、C++の deque STL を使ったサンプルコードを見ながら、その機能を確認していきましょう。

サンプルコード（デキュー）

#include <iostream>
#include <deque>
using namespace std;

void dequeElements(deque<int> que) {
    deque<int>::iterator it;
    for (it = que.begin(); it != que.end(); ++it)
        cout << *it << " ";
    cout << endl;
}

int main() {
    deque<int> que;
    que.push_back(10);
    que.push_front(20);
    que.push_back(30);
    que.push_front(15);

    cout << "現在のキューの中身 : ";
    dequeElements(que);
    cout << "キューのサイズ : " << que.size() << endl;
    cout << "位置2の要素 : " << que.at(2) << endl;
    cout << "先頭の要素 : " << que.front() << endl;
    cout << "末尾の要素 : " << que.back() << endl;

    cout << "先頭から削除 : ";
    que.pop_front();
    dequeElements(que);

    cout << "末尾から削除 : ";
    que.pop_back();
    dequeElements(que);
}

出力結果

現在のキューの中身 : 15 20 10 30
キューのサイズ : 4
位置2の要素 : 10
先頭の要素 : 15
末尾の要素 : 30
先頭から削除 : 20 10 30
末尾から削除 : 20 10

このコードでは、push_front() と push_back() によって両端への挿入を行い、pop_front() と pop_back() によって両端からの削除を行っています。また、at()・front()・back() を使えば、任意位置や両端の要素へ直接アクセスできることもわかります。

優先度付きキューとは

キューのもう一つの重要な派生形が優先度付きキュー（Priority Queue）です。このデータ構造では、キュー内の各要素がそれぞれ独自の優先度を持ちます。要素を挿入する際に優先度の値を割り当てる必要があり、削除の際には最も優先度の高い要素から順に取り出されるという仕組みです。

優先度付きキューを実装する最も簡単な方法のひとつが、ヒープ（Heap）データ構造を利用することです。ヒープを使うことで、最大値（または最小値）の取得と挿入を効率的に行えます。

それでは、C++の priority_queue STL を使ったサンプルコードを見てみましょう。この例では、要素の値そのものが優先度として扱われるため、大きい値ほど高い優先度を持つことになります。

サンプルコード（優先度付きキュー）

#include <iostream>
#include <queue>
using namespace std;

void showElements(priority_queue<int> que) {
    priority_queue<int> q = que;
    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;
}

int main() {
    priority_queue<int> que;
    que.push(10);
    que.push(20);
    que.push(30);
    que.push(5);
    que.push(1);

    cout << "現在のキューの中身 : ";
    showElements(que);
    cout << "キューのサイズ : " << que.size() << endl;
    cout << "先頭（最優先）の要素 : " << que.top() << endl;

    cout << "要素を削除 : ";
    que.pop();
    showElements(que);

    cout << "要素を削除 : ";
    que.pop();
    showElements(que);
}

出力結果

現在のキューの中身 : 30 20 10 5 1
キューのサイズ : 5
先頭（最優先）の要素 : 30
要素を削除 : 20 10 5 1
要素を削除 : 10 5 1

priority_queue では top() で最も優先度の高い要素を参照し、pop() でそれを取り除きます。出力結果から、挿入順序に関係なく常に大きな値から順に取り出されていることが確認できます。なお、小さい値を優先したい場合は、比較関数に greater<int> を指定して priority_queue<int, vector<int>, greater<int>> のように宣言すれば対応可能です。