C++で学ぶ循環キュー：挿入・削除操作の完全ガイド

キュー(Queue)は、要素の集合を格納する抽象データ構造の一つです。キューはFIFO(First In, First Out:先入れ先出し)方式を採用しており、最初に挿入された要素が最初に取り出されるという特性を持ちます。

キューは本来、線形データ構造として実装されます。しかし、配列を使ってキューを実装した場合、いくつかの問題が発生することがあります。挿入(insert)と削除(delete)の操作を繰り返すうちに、front(先頭ポインタ)とrear(末尾ポインタ)の位置が徐々に後方へ移動していきます。その結果、配列の後ろ側に空き領域が残っているにもかかわらず、論理上の制約によりその領域を利用できず、「キューが満杯である」と誤認識されてしまうのです。

この問題を解決するために考案されたのが循環キュー(Circular Queue)です。循環キューでは、配列の最後尾の位置を先頭の位置につなげてリング状(円環)の構造を作ります。これにより、rearが配列の末端に達した際に自動的に先頭へ戻るため、空き領域を無駄なく再利用できるようになります。

循環キューのアルゴリズム

挿入操作：insert(queue, key)

begin
   もし front = 0 かつ rear = n – 1、または front = rear + 1 の場合、
   　→ キューは満杯のため処理を終了して戻る
   そうでない場合：
   　もし front = -1 ならば、front = 0、rear = 0 とする（初回挿入時）
   　それ以外の場合：
   　　もし rear = n – 1 ならば rear = 0、そうでなければ rear := rear + 1
   queue[rear] = key

削除操作：delete(queue)

begin
   もし front = -1 の場合、
   　→ キューは空のため処理を終了して戻る
   そうでない場合：
   　item := queue[front]
   　もし front = rear ならば、front と rear を -1 に戻す（キューが空になった状態）
   　それ以外の場合：
   　　もし front = n – 1 ならば front := 0、そうでなければ front := front + 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;
}

実行結果

プログラムを実行し、要素10〜50を順番に挿入し、その後に削除を行った場合の出力例は以下の通りです。

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

まとめ

この記事では、循環キューの基本概念から、挿入・削除操作のアルゴリズム、そしてC++による実際の実装までを解説しました。循環キューを活用することで、配列ベースのキューで発生しがちな「未使用の空き領域」問題を回避でき、限られたメモリ領域を効率的に活用できます。オーバーフロー(Queue Overflow)やアンダーフロー(Queue Underflow)のチェックも組み込まれているため、堅牢なデータ構造として幅広い場面で応用できます。