キュー （待ち行列） Queue

キューは「待ち行列」とも呼ばれ、データを到着順に処理したいときに使用するデータ構 造で、データの中で最初に入ったものが最初に取り出される、先入れ先出し（FIFO: First In First Out）のルールに従ってデータを管理します。スーパーのレジやＡＴＭの待ち行列にお ける人々の動きやそこにある暗黙のルール（割り込みや追い越しの禁止）は、キューのデー タ構造そのものです。

キューの操作

• enqueue(x): キューの末尾に要素 x を追加します。
• dequeue(): キューの先頭から要素を取り出します。
• isEmpty(): キューが空かどうかを調べます。
• isFull(): キューが満杯かどうかを調べます。

実用的なキューには、これらの他にもキューの先頭の要素を参照したり、キューに指定され たデータが含まれているかを調べたりするオプション的な操作も含まれますが、ここでは上 記４つの操作を含むキューを実装します。

キューの制約

• データの中で最初に入ったものが最初に取り出されます。

整数型のデータが格納されるキューを配列を用いて実装します。以下に、実装に必要なもの を示します(下図参照)。



データを格納するための整数型1 次元配列: buffer
配列buffer の各要素にエンキューされたデータを格納していきます。問題に応じた十分な 記憶領域を確保することが必要です。Fig.4.3-1 では、既にいくつかの要素が格納されてい ます。

先頭カーソルである整数型変数：head
キューの先頭の場所を指し示す変数です。dequeue されるとhead で指された要素が取り出 されます。キューの先頭の要素のインデックスが0 とは限らないことに注意して下さい。

末尾カーソルである整数型変数：tail
キューの末尾＋ 1 の場所（最後の要素の隣）を指し示す変数です。tail は新しい要素が追加 される場所を示します。

実際にキューのデータ構造を操作する様子を見てみましょう。Fig. 4.3-2は、実際にキューに適当な値を適当に出し入れしている様子を示しています。

初期化: head = tailのときキューが空になります。初期値はhead = tail = 0とします。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 3 ）。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 7 ）。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 1 ）。 dequeue: headが指す要素を取り出し、headを1増やします （例: 3を取り出す）。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 8 ）。 dequeue: headが指す要素を取り出し、headを1増やします （例: 7を取り出す）

このように配列によってキューを実装すると、上図に示すように、データの追加と取り出し操作を繰り返すことによって、headとtailに挟まれたキューのデータ本体が配列の末尾に向かって（図の右側に）移動していき、すぐに要領をオーバーしてしまいそうに見えます。

下図に示すように、dequeueされたときにheadを常に0に保つようにデータ全体を配列の先頭に（左に）向かってシフトしていては、dequeueの度にO(n)の計算が必要になってしまいます。一方で、tailが配列の領域を超えた時点でoverflowとしてしまったのでは、まだ使える配列の領域を無駄にしてしまいます。


これらの問題を避けるために、配列によるキューの実装ではFig.4.3-4に示すように、配列をリングバッファとみなしてキュー内のデータを管理します。


リングバッファとは通常の1次元配列で実現しますが、キューの範囲を指し示すカーソルheadまたはtailが配列の領域を超えてしまったときにこれらのカーソルを循環させます。つまり、カーソルを1つ増やして、それが配列の範囲を超えてしまった場合には、カーソルを0にリセットします。

上図は既にいくつかのデータが格納されたキューにデータを出し入れしている様子を示しています。最初に1を追加したときに、tailの値が1つ増えますが、配列の領域を超えてしまうので、tailを0に設定します。リングバッファを時計回りに見ると、キューにデータがある場合は必ずhead→tailの順番に並びます。

次のは配列によってキューを実現し、キューへのデータの追加・取り出しをシミュレーションします。

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

#define MAX 100

class Queue{
    private:
    int buffer[MAX];
    int head, tail;

    public:
    Queue(){
        initialize();
    }

    void initialize(){
        head = tail = 0;
    }

    bool isEmpty(){
        return ( head == tail );
    }

    bool isFull(){
        return ( head == tail + 1 );
    }

    void enqueue( int x ){
        if ( isFull() ){
            cout << "overflow" << endl;
            return;
        } else {
            buffer[tail] = x;
            if ( tail + 1 == MAX ) tail = 0; // 循環
            else tail++;
        }
    }

    int dequeue(){
        if ( isEmpty() ){
            cout << "underflow" << endl;
        } else {
            int x = buffer[head];
            if ( head + 1 == MAX ) head = 0; // 循環
            else head++;
            return x;
        }
    }
};

int main(void){
    Queue queue;
    int x;
    string command;

    while (1){
            cin >> command;
            if ( command == "enqueue" ) {
                cin >> x;
                queue.enqueue(x);
            } else if ( command == "dequeue" ){
                cout << queue.dequeue() << endl;
            } else break;
    }

    return 0;
}

main関数
キューのオブジェクトqueueを操作します。無限ループによってキーボードからコマンドcommandの入力を待ち続けます。commandがenqueueであればxを読み込みそれをqueueに追加します。commandがdequeueであればqueueからデータを取り出し、それを出力します。それ以外のcommandが入力されたときループから抜けプログラムが終了します。

initialize
queue を空にします。queue が空のときhead とtail が同じ位置を示します。ここでは初期 値を0 と設定します。

isEmpty
queue が空の場合真を返します。head とtail が同じ値のときキューが空となります。

isFull
queue が満杯の場合真を返します。プログラムではbuffer の容量がMAX で定義されていま す。head が(tail+1)%MAX に等しいとき、queue が満杯になります。リングバッファを時 計回りに見ると、tail → head の間は常に1 つ以上の空きがあります。

enqueue(x)
queue が満杯の場合は”overflow” と出力します。そうでなければ、tail が指す場所にx を追 加します。queue の要素が1 つ増えたのでtail を1 増やします。ただし、増やした値が配 列の容量であるMAX 以上になってしまう場合はtail を0 として循環させます。

dequeue
queue が空の場合は”underflow” と出力します。そうでなければ、head が指すqueue の先 頭の要素を変数x に一時記録し、head を1 増やしてからx を返します。ただし、head を 増やした値がMAX 以上になってしまう場合はhead を0 として循環させます。