【C++】配列でキュー（Queue）を実装する方法とサンプルコード

キュー（Queue）とは

キューはFIFO（First In First Out：先入れ先出し）方式のデータ構造です。要素の挿入は一端（後端＝rear）から行い、削除はもう一方の端（前端＝front）から行います。そのため、最初に入った要素が最初に取り出されます。

キューの基本操作

• EnQueue(int data)：後端（rear）に要素を挿入する
• DeQueue()：前端（front）から要素を削除する

この記事では、配列を使ってC++でキューを実装する方法とサンプルコードを紹介します。

アルゴリズム

1. Enqueue()：キューへの挿入
   キューが満杯の場合は「Overflow」と表示します。空きがある場合は後端（rear）に要素を格納し、rearの値を更新します。
2. Dequeue()：キューからの削除
   キューが空の場合は「Underflow」と表示します。要素がある場合は前端（front）の要素を取り除き、rearの値を更新します。

C++サンプルコード

以下は、構造体Qとしてキューを実装したC++のコード例です。メンバー変数には前端f・後端r・容量capacity、そして動的に確保した配列qを使用しています。

#include <bits/stdc++.h>
using namespace std;

struct Q {
   int f, r, capacity; // f: 前端 / r: 後端 / capacity: 容量
   int* q;             // キュー本体の配列
   Q(int c) {
      f = r = 0;
      capacity = c;
      q = new int[c];  // 容量分のメモリを確保
   }
   ~Q() { delete[] q; }
   void Enqueue(int d) {
      if (capacity == r) {       // 満杯かどうかを確認
         printf("\nQueue is full\n");
         return;
      } else {
         q[r] = d;               // データを挿入
         r++;                    // 後端を更新
      }
      return;
   }
   void Dequeue() {
      if (f == r) {              // 空かどうかを確認
         printf("\nQueue is empty\n");
         return;
      } else {
         for (int i = 0; i < r - 1; i++) {
            q[i] = q[i + 1];     // 要素を前方へ詰める
         }
         r--;                    // 後端を更新
      }
      return;
   }
   void Display() {              // キューの内容を表示
      int i;
      if (f == r) {
         printf("\nQueue is Empty\n");
         return;
      }
      for (i = f; i < r; i++) {
         printf(" %d <-- ", q[i]);
      }
      return;
   }
   void Front() {                // 先頭要素を表示
      if (f == r) {
         printf("\nQueue is Empty\n");
         return;
      }
      printf("\nFront Element is: %d", q[f]);
      return;
   }
};

int main(void) {
   Q qu(3);
   qu.Display();
   cout << "after inserting elements" << endl;
   qu.Enqueue(10);
   qu.Enqueue(20);
   qu.Enqueue(30);
   qu.Display();
   qu.Dequeue();
   qu.Dequeue();
   printf("\n\nafter two node deletion\n\n");
   qu.Display();
   qu.Front();
   return 0;
}

Enqueue()は後端へデータを追加し、Dequeue()は前端のデータを削除して残りの要素を前方へ詰めます。また、Display()でキューの内容を表示し、Front()で先頭要素を参照できます。

実行結果

Queue is Empty
10 <-- 20 <-- 30 <--

after two node deletion

30 <--
Front Element is: 30

実装のポイント

• この実装ではDequeue()のたびに全要素を1つずつ前方へ移動するため、削除操作の計算量はO(n)になります。
• 循環配列（リングバッファ）を使えば、挿入・削除をO(1)で処理できるようになります。
• 実務ではSTLのstd::queueを使うのが一般的で、安全かつ効率的にキューを扱えます。