C++でのキューの配列実装

キューは、操作の順序がFIFO（先入れ先出し）である線形データ構造です。

配列は、同じデータ型の要素を含むデータ構造であり、連続したメモリ位置に格納されます。

キューでは、キューの両端で行われる挿入および削除操作。実装は、スタックと比較して少し複雑です。

キューの配列実装では、topとendの2つの変数を持つサイズnの配列キューを作成します。

現在、最初は配列は空です。つまり、先頭と末尾の両方が配列の0インデックスにあります。そして、要素がキューに追加されると、（挿入） 終了変数の値が増加します。 endの値は、nまで増加する可能性があります。つまり、配列の最大長です。

要素をキューから削除する場合（削除） 、一番上の変数の値が増加します。 topの値は、endの値まで上がる可能性があります。

キュー操作の実装

エンキュー −キューに要素を追加するための操作です。キューに要素を追加する前に、キューがいっぱいかどうかを確認します。終了を確認する条件。n未満の場合は、queue[end]に要素を保存できます。そして、endを1増やします。

オーバーフロー状態は、配列がいっぱいになったとき、つまりend==nのときです。

デキュー −キューの要素を削除する操作です。キューの要素を削除する前に、キューが空かどうかを確認します。キューが空かどうかをチェックする条件で、topとendの値がチェックされます。 top ==endの場合、配列は空です。

要素がある場合は、配列をデキューします。配列の左側にあるすべての要素を1つシフトします。

フロント −キューの最初の要素、つまりarray[top]を抽出します。この操作は、アレイが空でない場合にのみ実行できます。

表示 −この操作は、キューのすべての要素を表示します。つまり、キューをトラバースします。

アルゴリズム

ENQUEUE :
Step 1 : if (end == n), print : “OVERFLOW”. Exit
Step 2 : queue[end] = data and end++
DEQUEUE :
Step 1 : If (top == 0), print : “empty Queue”. Exit
Step 2 : shift all elements one position left. End-- ;

例

#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;
   }
   ~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