C++で配列を使ってキュー（Queue）を実装する方法

キューと配列とは

キュー（Queue）は、FIFO（First In First Out：先入れ先出し）という順序で操作を行う線形データ構造です。最初に入れた要素が、最初に取り出されます。

一方、配列は同じデータ型の要素を連続したメモリ領域に格納するデータ構造です。

キューでは、要素の挿入と削除がそれぞれキューの反対側の端で行われます。そのため、片方の端だけで操作するスタックに比べて、実装はやや複雑になります。

配列によるキューの実装の考え方

配列でキューを実装する場合、サイズ n の配列 queue を用意し、top と end という2つの変数を使用します。

初期状態では配列は空であり、top と end はどちらも配列のインデックス0を指しています。要素を追加（insertion：エンキュー）するたびに end の値が1ずつ増えていき、end は配列の最大長 n まで増加できます。

要素を削除（deletion：デキュー）する際は、残りの要素を前方にシフトすることで先頭の要素を取り除きます。top は end の値まで移動可能です。

キューの基本操作

Enqueue（エンキュー：挿入）

キューに要素を追加する操作です。追加の前に、キューが満杯でないかを確認します。end が n 未満であれば queue[end] に要素を格納し、end を1増やします。end == n の場合はオーバーフロー（満杯）状態です。

Dequeue（デキュー：削除）

キューから要素を削除する操作です。削除の前に、top と end の値を比較してキューが空かどうかを確認します。top == end であればキューは空です。要素が存在する場合は、すべての要素を1つずつ左にシフトして先頭要素を取り除き、end を1減らします。

Front（先頭要素の参照）

キューの先頭要素、すなわち queue[top] を取得する操作です。この操作はキューが空でない場合にのみ実行できます。

Display（表示）

キュー内のすべての要素を表示する操作です。キュー全体を走査（トラバース）します。

アルゴリズム

ENQUEUE :
Step 1 : if (end == n)、"OVERFLOW" を出力して終了
Step 2 : queue[end] = data とし、end++
DEQUEUE :
Step 1 : if (top == end)、"empty Queue" を出力して終了
Step 2 : すべての要素を1つ左へシフトし、end--

C++での実装例

#include <bits/stdc++.h>
using namespace std;
struct Queue {
    int top, end, n;
    int* queue;
    Queue(int c){
        top = end = 0;
        n = c;
        queue = new int[c];
    }
    ~Queue() { delete[] queue;
}
void Enqueue(int data){
    if (n == end) {
        printf("\nQueue is full\n");
        return;
    }
    else {
        queue[end] = data;
        end++;
    }
    return;
}
void Dequeue(){
    if (top == end) {
        printf("\nQueue is empty\n");
        return;
    }
    else {
        for (int i = 0; i < end - 1; i++) {
            queue[i] = queue[i + 1];
        }
        end--;
    }
    return;
}
void Display(){
    int i;
    if (top == end) {
        printf("\nQueue is Empty\n");
        return;
    }
    for (i = top; i < end; i++) {
        printf(" %d <-- ", queue[i]);
    }
    return;
}
void Front(){
    if (top == end) {
        printf("\nQueue is Empty\n");
        return;
    }
    printf("\nFront Element is: %d", queue[top]);
    return;
}
};
int main(void){
    Queue q(4);
    q.Display();
    q.Enqueue(12);
    q.Enqueue(89);
    q.Enqueue(65);
    q.Enqueue(34);
    q.Display();
    q.Enqueue(92);
    q.Display();
    q.Dequeue();
    q.Dequeue();
    q.Display();
    q.Front();
    return 0;
}

実行結果

Queue is Empty
12 <-- 89 <-- 65 <-- 34 <--
Queue is full
12 <-- 89 <-- 65 <-- 34 <-- 65 <-- 34 <--
Front Element is: 65

なお、Display 関数は末尾で改行を出力しないため、連続して呼び出した場合は出力が同じ行に続けて表示される点に注意してください。上記の実行結果では、最後の Display の出力「65 <-- 34 <--」が前の表示に続いて出力されています。