循環キューを実装するC++プログラム

キューは、要素の集合を格納する抽象データ構造の一つです。キューはFIFO（First In First Out：先入れ先出し）方式を採用しており、最初に挿入された要素が最初に取り出されます。

循環キュー（Circular Queue）はキューの一種で、配列の末尾と先頭をつなげて円形にした構造を持っています。これにより、配列の後方に空きがなくても、先頭側の空きスペースを再利用できるという利点があります。

この記事では、挿入・削除・表示の3つの操作を実装した、循環キューのC++プログラムを紹介します。

循環キューの基本的な仕組み

循環キューでは、front（先頭）とrear（末尾）の2つのインデックスを使用して要素を管理します。

• 挿入（enqueue）：rearを1つ進めてその位置に要素を格納します。rearが配列の末尾に達した場合は、先頭（0番目）に戻ります。
• 削除（dequeue）：frontの位置にある要素を取り出し、frontを1つ進めます。frontが配列の末尾に達した場合は、先頭に戻ります。
• 満杯判定：(front == 0 && rear == n-1) または (front == rear+1) の場合、キューは満杯です。

C++による実装例

以下は、循環キューをC++で実装したプログラムです。メニュー形式で挿入、削除、表示の操作を選択できます。

#include <iostream>
using namespace std;

int cqueue[5];
int front = -1, rear = -1, n=5;

void insertCQ(int val) {
    if ((front == 0 && rear == n-1) || (front == rear+1)) {
        cout<<"Queue Overflow \n";
        return;
    }
    if (front == -1) {
        front = 0;
        rear = 0;
    } else {
        if (rear == n - 1)
        rear = 0;
        else
        rear = rear + 1;
    }
    cqueue[rear] = val ;
}
void deleteCQ() {
    if (front == -1) {
        cout<<"Queue Underflow\n";
        return ;
    }
    cout<<"Element deleted from queue is : "<<cqueue[front]<<endl;

    if (front == rear) {
        front = -1;
        rear = -1;
    } else {
        if (front == n - 1)
        front = 0;
        else
        front = front + 1;
    }
}
void displayCQ() {
    int f = front, r = rear;
    if (front == -1) {
        cout<<"Queue is empty"<<endl;
        return;
    }
    cout<<"Queue elements are :\n";
    if (f <= r) {
        while (f <= r){
            cout<<cqueue[f]<<" ";
            f++;
        }
    } else {
        while (f <= n - 1) {
            cout<<cqueue[f]<<" ";
            f++;
        }
        f = 0;
        while (f <= r) {
            cout<<cqueue[f]<<" ";
            f++;
        }
    }
    cout<<endl;
}
int main() {

    int ch, val;
    cout<<"1)Insert\n";
    cout<<"2)Delete\n";
    cout<<"3)Display\n";
    cout<<"4)Exit\n";
    do {
        cout<<"Enter choice : "<<endl;
        cin>>ch;
        switch(ch) {
            case 1:
            cout<<"Input for insertion: "<<endl;
            cin>>val;
            insertCQ(val);
            break;

            case 2:
            deleteCQ();
            break;

            case 3:
            displayCQ();
            break;

            case 4:
            cout<<"Exit\n";
            break;
            default: cout<<"Incorrect!\n";
        }
    } while(ch != 4);
    return 0;
}

コードの解説

insertCQ関数（挿入処理）

まずオーバーフロー（満杯）のチェックを行い、キューが満杯の場合はメッセージを表示して終了します。キューが空の場合（front == -1）は、frontとrearを0に初期化します。それ以外の場合はrearを1つ進めますが、rearが配列の末尾に達していれば0に戻すことで循環を実現しています。

deleteCQ関数（削除処理）

キューが空の場合（front == -1）はアンダーフローのメッセージを表示します。削除対象の要素を表示した後、frontとrearが同じ位置ならキューは空になったため両者を-1にリセットし、そうでなければfrontを1つ進めます（末尾に達していれば0に戻る）。

displayCQ関数（表示処理）

キューが空の場合はその旨を表示します。frontがrearより小さい場合は単純に順番に表示しますが、循環によってfrontがrearより大きくなっている場合は、末尾まで表示した後に先頭からrearまでを続けて表示することで、正しい順序で全要素を出力できます。

実行結果

上記プログラムの実行例は以下の通りです。要素5、3、2、7、9を挿入した後、3つの要素を削除し、さらに6を挿入して表示しています。

1)Insert
2)Delete
3)Display
4)Exit

Enter choice : 1
Input for insertion: 5
Enter choice : 1
Input for insertion: 3
Enter choice : 1
Input for insertion: 2
Enter choice : 1
Input for insertion: 7
Enter choice : 1
Input for insertion: 9
Enter choice : 2
Element deleted from queue is : 5
Enter choice : 2
Element deleted from queue is : 3
Enter choice : 2
Element deleted from queue is : 2
Enter choice : 1
Input for insertion: 6
Enter choice : 3
Queue elements are :
7 9 6
Enter choice : 4
Exit

このように、通常のキューでは一度削除された領域は再利用できませんが、循環キューではrearが配列の先頭に回り込むことで、空いた領域を効率的に使い続けることができます。この特性により、循環キューはOSのタスクスケジューリングやストリーミング処理など、限られたメモリを繰り返し利用する場面で広く活用されています。