c circular queue data structure
C ++循環キューのデータ構造に関するこのチュートリアルでは、循環キューとは何か、実装とアプリケーションに伴う基本的な操作について説明します。
循環キューは、前に説明した基本キューの拡張です。 「リングバッファ」とも呼ばれます。
C ++の循環キューとは何ですか？
循環キューは、データ項目を格納するために使用される線形データ構造です。 FIFO（先入れ先出し）アプローチに従って操作を実行し、キューの最後の位置を最初の位置に接続して円を形成します。
=> ここでC ++トレーニングシリーズ全体を探してください
学習内容：
C ++の循環キュー
次の図は、循環キューを示しています。
上の画像は、サイズ10の循環データ構造を示しています。最初の6つの要素はすでにキューにあり、最初の位置と最後の位置が結合されていることがわかります。この配置により、線形キューで発生するようにスペースが無駄になることはありません。
cssセレクターによるセレン検索要素
キューがいっぱいになった後の線形キューでは、別の端から要素を削除しますが、キューのステータスはまだいっぱいとして表示され、それ以上要素を挿入することはできません。
循環キューでは、キューがいっぱいになり、最後と最初の位置が接続されているために前面から要素を削除すると、要素を削除することで、空になった要素を背面に挿入できます。
次のセクションでは、循環キューの基本的な操作について学習します。
基本操作
循環キューの基本的な操作の一部は次のとおりです。
フロント： 循環キューの先頭の位置を返します。
リア： 循環キューの後方位置を返します。
エンキュー： エンキュー（値）は、循環キューに要素を挿入するために使用されます。要素は常にキューの後端に挿入されます。
次の一連の手順に従って、循環キューに新しい要素を挿入します。
＃1） 循環キューがいっぱいかどうかを確認します：test（（rear == SIZE-1 && front == 0）||（rear == front-1））、ここで「SIZE」は循環キューのサイズです。
＃二） 循環キューがいっぱいになると、「キューがいっぱいです」というメッセージが表示されます。キューがいっぱいでない場合は、（rear == SIZE – 1 && front！= 0）かどうかを確認します。 trueの場合、rear = 0に設定し、要素を挿入します。
デキュー： デキュー機能は、キューから要素を削除するために使用されます。循環キューでは、要素は常にフロントエンドから削除されます。以下に、循環キューでのデキュー操作のシーケンスを示します。
手順：
＃1） 循環キューが空かどうかを確認します：（front ==-1）かどうかを確認します。
＃二） 空の場合は、「キューが空です」というメッセージを表示します。キューが空でない場合は、手順3を実行します。
＃3） （フロント==リア）かどうかを確認します。 trueの場合はfront = Rear = -1に設定し、そうでない場合は（front == size-1）を確認し、trueの場合はfront = 0に設定して、要素を返します。
図
このセクションでは、循環キュー内の要素の追加/削除の詳細な図を見ていきます。
以下に示すように、5つの要素からなる次の循環キューについて考えてみます。
次に、アイテム1をキューに挿入します。
次に、値3のアイテムを挿入します。
C ++とは何ですか
要素を挿入してキューをいっぱいにすると、表現は次のようになります。
次に、以下に示すように、2つの要素、つまりアイテム1とアイテム3をキューから削除します。
次に、以下に示すように、要素11を循環キューに挿入またはエンキューします。
ここでも、要素13を循環キューに挿入しましょう。キューは次のようになります。
循環キューでは、要素を円に移動または挿入していることがわかります。したがって、キューがいっぱいになるまで、キューのスペース全体を消費できます。
実装
C ++を使用して循環キューを実装しましょう。
#include using namespace std; class Queue { public: // Initialize front and rear int rear, front; // Circular Queue int size; int *circular_queue; Queue(int sz) { front = rear = -1; size = sz; circular_queue = new int(sz); } void enQueue(int elem); int deQueue(); void displayQueue(); }; /* Function to create Circular queue */ void Queue::enQueue(int elem) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { cout<<'
Queue is Full'; return; } else if (front == -1) { /* Insert First Element */ front = rear = 0; circular_queue(rear) = elem; } else if (rear == size-1 && front != 0) { rear = 0; circular_queue(rear) = elem; } else { rear++; circular_queue(rear) = elem; } } // Function to delete element from Circular Queue int Queue::deQueue() { if (front == -1) { cout<<'
Queue is Empty'; return -1; } int data = circular_queue(front); circular_queue(front) = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } //display elements of Circular Queue void Queue::displayQueue() { if (front == -1) { cout<<'
Queue is Empty'<= front) { for (int i = front; i <= rear; i++) cout< 上に示したのは、循環キュー操作の出力です。まず、要素を追加してから、2つの要素をデキューまたは削除します。次に、循環キューにさらに3つの要素を挿入またはエンキューします。線形キューとは異なり、要素はキューの最後に追加されていることがわかります。
リンクリストの実装
ここで、循環キューのリンクリストの実装について説明します。以下に示すのは、C ++での循環キューのリンクリストの実装です。 structを使用して各ノードを表すことに注意してください。操作は前に説明したものと同じですが、この場合、リンクリストノードに対して実行する必要があります。
出力には、エンキュー操作、デキュー、および2番目のエンキュー操作後の循環キューが表示されます。
#include using namespace std; struct Node { int data; struct Node* link; }; struct PQueue { struct Node *front, *rear; }; /* this functions performs enqueue operation for circular queue */ void enQueue(PQueue *pq,int elem) { struct Node *temp = new Node; temp->data = elem; if (pq->front == NULL) pq->front = temp; else pq->rear->link = temp; pq->rear = temp; pq->rear->link = pq->front; } // This function performs dequeue operation for Circular Queue int deQueue(PQueue *pq) { if (pq->front == NULL) { cout<<'Queue is empty!!'; return -1; } int elem; // item to be dequeued // item is the last node to be deleted if (pq->front == pq->rear) { elem = pq->front->data; free(pq->front); pq->front = NULL; pq->rear = NULL; } else //more than one nodes { struct Node *temp = pq->front; elem = temp->data; pq->front = pq->front->link; pq->rear->link= pq->front; free(temp); } return elem ; } //display elements of Circular Queue void displayQueue(struct PQueue *pq) { struct Node *temp = pq->front; while (temp->link != pq->front) { cout<data<<' '; temp = temp->link; } cout<data; } //main program int main() { // Create a circular queue and initialize front and rear PQueue *pq = new PQueue; pq->front = pq->rear = NULL; // Insert/enqueue elements in Circular Queue enQueue(pq, 1); enQueue(pq, 3); enQueue(pq, 5); cout<<'
Circular Queue elements after enqueue operation: '; // Display elements in Circular Queue displayQueue(pq); // Delete/dequeue elements from Circular Queue cout<<'
Dequeued Item: '< 出力：
次の実装は、リンクリストを使用して循環キューを示すJavaプログラムです。
import java.util.* ; class Main { // Node structure static class Node { int data; Node link; } static class CQueue { Node front, rear; } // Enqueue operation for circular queue static void enQueue(CQueue cq, int value) { Node temp = new Node(); temp .data = value; if (cq .front == null) cq .front = temp; else cq .rear .link = temp; cq .rear = temp; cq .rear .link = cq .front; } // Dequeue operation for Circular Queue static int deQueue(CQueue cq) { if (cq .front == null) { System.out.printf ('Queue is empty!!'); return Integer.MIN_VALUE; } int value; // Value to be dequeued // the last node to be deleted if (cq.front == cq.rear) { value = cq.front.data; cq.front = null; cq.rear = null; } else { // There are more than one nodes Node temp = cq.front; value = temp.data; cq.front = cq.front.link; cq.rear.link= cq.front; } return value ; } // display the elements of Circular Queue static void displayQueue( CQueue cq) { Node temp = cq.front; while (temp.link != cq.front) { System.out.printf('%d ', temp.data); temp = temp.link; } System.out.printf('%d', temp.data); } /* main program */ public static void main(String args()) { // Create a queue and initialize front and rear CQueue cq = new CQueue(); cq.front = cq.rear = null; // Insert/enqueue elements in Circular Queue enQueue(cq, 2); enQueue(cq, 4); enQueue(cq, 6); System.out.print('
Circular Queue elements after Enqueue Operation:'); // Display elements in Circular Queue displayQueue(cq); // Delete/dequeue elements from Circular Queue System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.print('
Circular Queue elements after Dequeue Operation:'); displayQueue(cq); enQueue(cq, 8); enQueue(cq, 10); System.out.print('
Circular Queue elements after second Enqueue Operation:'); displayQueue(cq); } } 出力：
上記のプログラムの出力は、前のプログラムと同様です。
アプリケーション
循環キューのいくつかのアプリケーションについて説明しましょう。
- CPUスケジューリング： 何らかのイベントの発生または実行のために他のプロセスの完了を必要とするオペレーティングシステムプロセスは、多くの場合、すべての条件が満たされたとき、またはすべてのイベントが発生したときに次々に実行されるように、循環キューに保持されます。
- メモリ管理： 上記の説明ですでに述べたように、通常のキューを使用するとメモリスペースが無駄になります。メモリ管理に循環キューを使用すると、最適なメモリ使用量に役立ちます。
- コンピュータ制御の交通信号システム： コンピュータ化された信号機は、指定された時間間隔が経過した後に繰り返されるように、循環キューに追加されることがよくあります。
結論
循環キューは、通常のキューの主な欠点を修正します。要素を削除してスペースを空にしても、後部ポインターがキューの最後にあると要素を挿入できません。循環キューでは、要素が循環的に配置されるため、スペースがまったく無駄になりません。
循環キューの主要な操作も確認しました。循環キューは、主にスケジューリングの目的や、信号が順番に光る信号システムなどのアプリケーションに役立ちます。
Windows10を最適化するための最良のソフトウェア
次のチュートリアルでは、単に「deque」と呼ばれる両端キューについて学習します。
=> ゼロからC ++を学ぶには、こちらにアクセスしてください
推奨読書
