データ構造におけるキューの基本操作と実装例を徹底解説

キュー（Queue）とは

キューは「先入れ先出し（FIFO: First In First Out）」と呼ばれるデータ構造です。最初に追加された要素が最初に取り出されるという特性を持ち、グラフの探索アルゴリズムである幅優先探索（BFS: Breadth First Search）をはじめ、さまざまな分野で幅広く活用されています。

キューには、いくつかの基本的な操作（プリミティブ操作）が定義されています。本記事では、キューの主な操作について解説し、キューのADT（抽象データ型）を使用した実装例を紹介します。

ADT（抽象データ型）とは

ADT（Abstract Data Type：抽象データ型）は、値の集合と操作の集合によってその振る舞いが定義される特殊なデータ型です。「抽象（Abstract）」という言葉が使われているのは、利用者がこれらのデータ型を使用してさまざまな操作を実行できる一方で、その操作が内部でどのように実装・動作しているのかは完全に隠されているためです。ADTはプリミティブなデータ型から構成されていますが、操作のロジック自体は外部からは見えないようになっています。

キューの主な操作

キューのADTには、以下のような操作（関数）が用意されています。

• isFull()：キューが満杯かどうかを判定します
• isEmpty()：キューが空かどうかを判定します
• enqueue(x)：要素xをキューの末尾に追加します
• dequeue()：キューの先頭から要素を1つ削除します
• front()：キューの最前面にある要素を取得します
• size()：キュー内に存在する要素の数を取得します

実装例（C++）

以下は、C++のSTLキューを使用した実装例です。

#include<iostream>
#include<queue>
using namespace std;
main(){
    queue<int> que;
    if(que.empty()){
        cout << "Queue is empty" << endl;
    } else {
        cout << "Queue is not empty" << endl;
    }
    //キューに要素を挿入
    que.push(10);
    que.push(20);
    que.push(30);
    que.push(40);
    que.push(50);
    cout << "Size of the queue: " << que.size() << endl;
    //要素を削除して表示
    while(!que.empty()) {
        int item = que.front(); //先頭の要素を読み取る
        que.pop();
        cout << item << " ";
    }
}

実行結果

Queue is empty
Size of the queue: 5
10 20 30 40 50

コードの解説

このプログラムでは、まず空のキューを作成し、empty()関数によってキューが空であることを確認しています。その後、push()関数を使って10から50までの5つの整数をキューに挿入し、size()関数でキューのサイズ（5）を表示しています。

最後に、front()で先頭の要素を読み取り、pop()で削除する処理を、キューが空になるまで繰り返しています。その結果、挿入した順番どおり「10 20 30 40 50」と出力され、キューのFIFO（先入れ先出し）の動作が確認できます。