C++でデキュー（両端キュー）を実装する方法｜アルゴリズムとサンプルコード解説

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

デキュー（Dequeue／Double Ended Queue：両端キュー）は、通常のキューを一般化したデータ構造で、先頭と末尾の両端から要素の挿入・削除が可能な点が最大の特徴です。通常のキューでは「末尾への挿入」と「先頭からの削除」しか行えませんが、デキューではどちらの端からでも操作できます。

デキューの基本的な操作は以下の4つです。

• insert_at_beg() … デキューの先頭に要素を挿入する
• insert_at_end() … デキューの末尾に要素を挿入する
• delete_fr_beg() … デキューの先頭から要素を削除する
• delete_fr_rear() … デキューの末尾から要素を削除する

以下では、これらの操作を配列ベースで実装したC++プログラムを紹介します。

アルゴリズム

Begin
    クラス dequeue を宣言し、先頭位置 f・末尾位置 r および以下の関数を定義する

    関数 insert_at_beg(int)（先頭への挿入）:
        キューが満杯でなければ、先頭に要素を挿入して f と r を更新する
        満杯の場合は「オーバーフロー」を表示する

    関数 insert_at_end(int)（末尾への挿入）:
        キューが満杯でなければ、末尾に要素を挿入して f と r を更新する
        満杯の場合は「オーバーフロー」を表示する

    関数 delete_fr_beg()（先頭からの削除）:
        キューが空なら「アンダーフロー」を表示する
        空でなければ先頭の要素を削除して f を更新する

    関数 delete_fr_end()（末尾からの削除）:
        キューが空なら「アンダーフロー」を表示する
        空でなければ末尾の要素を削除して r を更新する
End

C++サンプルコード

#include <iostream>
#include <cstdlib>
using namespace std;
#define SIZE 10

class dequeue {
    int a[20], f, r;
public:
    dequeue();
    void insert_at_beg(int);
    void insert_at_end(int);
    void delete_fr_front();
    void delete_fr_rear();
    void show();
};

// コンストラクタ：初期状態ではキューは空
.dequeue::dequeue() {
    f = -1;
    r = -1;
}

// 末尾への挿入
void dequeue::insert_at_end(int i) {
    if (r >= SIZE - 1) {
        cout << "\n insertion is not possible, overflow!!!!";
    } else {
        if (f == -1) {
            f++;
            r++;
        } else {
            r = r + 1;
        }
        a[r] = i;
        cout << "\nInserted item is " << a[r];
    }
}

// 先頭への挿入
void dequeue::insert_at_beg(int i) {
    if (f == -1) {
        f = 0;
        a[++r] = i;
        cout << "\n inserted element is: " << i;
    } else if (f != 0) {
        a[--f] = i;
        cout << "\n inserted element is: " << i;
    } else {
        cout << "\n insertion is not possible, overflow!!!";
    }
}

// 先頭からの削除
void dequeue::delete_fr_front() {
    if (f == -1) {
        cout << "deletion is not possible::dequeue is empty";
        return;
    }
    cout << "the deleted element is: " << a[f];
    if (f == r) {
        f = r = -1;   // 最後の1要素を削除したので空に戻す
    } else {
        f = f + 1;
    }
}

// 末尾からの削除
void dequeue::delete_fr_rear() {
    if (f == -1) {
        cout << "deletion is not possible::dequeue is empty";
        return;
    }
    cout << "the deleted element is: " << a[r];
    if (f == r) {
        f = r = -1;   // 最後の1要素を削除したので空に戻す
    } else {
        r = r - 1;
    }
}

// キューの中身を表示
void dequeue::show() {
    if (f == -1) {
        cout << "Dequeue is empty";
    } else {
        for (int i = f; i <= r; i++) {
            cout << a[i] << " ";
        }
    }
}

int main() {
    int c, i;
    dequeue d;
    do {
        cout << "\n 1.insert at beginning";
        cout << "\n 2.insert at end";
        cout << "\n 3.show";
        cout << "\n 4.deletion from front";
        cout << "\n 5.deletion from rear";
        cout << "\n 6.exit";
        cout << "\n enter your choice:";
        cin >> c;
        switch (c) {
            case 1:
                cout << "enter the element to be inserted ";
                cin >> i;
                d.insert_at_beg(i);
                break;
            case 2:
                cout << "enter the element to be inserted ";
                cin >> i;
                d.insert_at_end(i);
                break;
            case 3:
                d.show();
                break;
            case 4:
                d.delete_fr_front();
                break;
            case 5:
                d.delete_fr_rear();
                break;
            case 6:
                exit(1);
                break;
            default:
                cout << "invalid choice";
                break;
        }
    } while (c != 7);
    return 0;
}

実行例

1.insert at beginning
2.insert at end
3.show
4.deletion from front
5.deletion from rear
6.exit
enter your choice:4
deletion is not possible::dequeue is empty

（以降、メニュー表示は省略）

enter your choice:1
enter the element to be inserted 7
inserted element is: 7

enter your choice:1
enter the element to be inserted 6
insertion is not possible, overflow!!!

enter your choice:2
enter the element to be inserted 6
Inserted item is 6

enter your choice:2
enter the element to be inserted 4
Inserted item is 4

enter your choice:3
7 6 4

enter your choice:4
the deleted element is: 7

enter your choice:5
the deleted element is: 4

enter your choice:1
enter the element to be inserted 7
inserted element is: 7

enter your choice:3
7 6

enter your choice:6

コードのポイント

• 要素は配列 a[20] に格納し、先頭インデックス f と末尾インデックス r の2つの変数で管理します。
• キューが空かどうかは f == -1 で判定します。
• 先頭への挿入は、f がすでに 0 の場合（それより前に空きがない場合）にオーバーフローとなります。
• 末尾への挿入は、r >= SIZE - 1 の場合にオーバーフローとなります。
• 要素が1つだけの状態（f == r）で削除を行うと、f = r = -1 としてキューを空の状態に戻します。

補足：実務ではSTLのstd::dequeが便利

学習目的で自前実装する場合は上記のような配列ベースの実装が有効ですが、実際の開発では標準テンプレートライブラリ（STL）の std::deque を使うのが一般的です。#include <deque> を追加するだけで、push_front()・push_back()・pop_front()・pop_back() などの両端操作を安全かつ効率的に利用できます。