C++で学ぶ循環キュー（リングバッファ）データ構造の実装方法

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

キューは線形データ構造として表現できますが、単純な配列で実装すると問題が発生する場合があります。挿入操作と削除操作を繰り返すうちに、先頭（front）と末尾（rear）の位置が配列の後方へ移動していきます。その結果、実際には空きスペースが残っているにもかかわらず、論理的な制約によって新しい要素を挿入できなくなることがあります。

この問題を解決するために使われるのが循環キュー（Circular Queue）です。循環キューとは、配列の最後の位置と最初の位置を論理的につなぎ、円環状の構造を作ったキューのことです。これにより、削除済みの領域も再利用できるため、メモリを無駄なく活用できます。

C++での循環キューの実装例

以下は、C++で循環キューを実装したサンプルプログラムです。挿入（Insert）、削除（Delete）、表示（Display）の3つの基本操作をメニュー形式で提供しています。

#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 {
        // frontがrearより後ろにある場合（折り返し発生時）
        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;
}

実行結果

1)Insert
2)Delete
3)Display
4)Exit
Enter choice :
1
Input for insertion:
10
Enter choice :
1
Input for insertion:
20
Enter choice :
1
Input for insertion:
30
Enter choice :
1
Input for insertion:
40
Enter choice :
1
Input for insertion:
50
Enter choice :
3
Queue elements are :
10 20 30 40 50
Enter choice :
2
Element deleted from queue is : 10
Enter choice :
2
Element deleted from queue is : 20
Enter choice :
3
Queue elements are :
30 40 50
Enter choice :
4
Exit

コードのポイント解説

オーバーフロー判定

挿入時には、(front == 0 && rear == n-1) または (front == rear+1) の条件でキューが満杯かどうかを判定します。この条件により、配列全体が使用されている場合に「Queue Overflow」を通知します。

折り返し処理

rearやfrontが配列の末尾（n-1）に到達した場合、次の位置としてインデックス0に戻る処理が組み込まれています。これが循環キューの核心部分であり、これにより削除済み領域を再利用できます。

表示処理における注意点

表示関数では、frontがrearより大きい値を持つケース（配列を一周して折り返している状態）を考慮し、2つのループに分けて要素を出力しています。この処理を忘れると、折り返し後の要素が正しく表示されません。

まとめ

循環キューは、固定サイズの配列でも効率的にキュー操作を実現できる優れたデータ構造です。OSのタスクスケジューリング、ストリーミングバッファ、プリンタの印刷待ち行列など、さまざまな場面で応用されています。FIFOの性質を保ちながらメモリを最大限に活用したい場合は、ぜひ循環キューの導入を検討してみてください。