TechCodeview

循環キューの概念はなぜ導入されたのですか?

の配列実装には 1 つの制限がありました。

上の画像でわかるように、後部はキューの最後の位置にあり、前部は 0 ではなくどこかを指しています。^番目位置。上記の配列には要素が 2 つだけあり、他の 3 つの位置は空です。後部はキューの最後の位置にあります。要素を挿入しようとすると、キューに空のスペースがないことが表示されます。このようなメモリ空間の無駄を避けるための 1 つの解決策は、左側の両方の要素をシフトし、それに応じてフロントエンドとリアエンドを調整することです。すべての要素を移動すると多大な時間がかかるため、これは現実的には良いアプローチではありません。メモリの無駄を避けるための効率的なアプローチは、循環キュー データ構造を使用することです。

循環キューとは何ですか?

循環キューは、円を形成する循環キューの最後の位置が最初の位置に接続されることを除いて、同じく FIFO (先入れ先出し) 原理に基づいているため、線形キューに似ています。としても知られています リングバッファ 。

循環キューの操作

循環キューに対して実行できる操作は次のとおりです。

フロント：キューからフロント要素を取得するために使用されます。後方：キューから後部の要素を取得するために使用されます。enQueue(値):この関数は、新しい値をキューに挿入するために使用されます。新しい要素は常に後端から挿入されます。デキュー():この関数は、キューから要素を削除します。キュー内の削除は常にフロントエンドから行われます。

循環キューの応用

循環キューは次のシナリオで使用できます。

メモリ管理：循環キューはメモリ管理を提供します。すでに見たように、線形キューではメモリがあまり効率的に管理されません。ただし、循環キューの場合は、要素を未使用の場所に配置することでメモリが効率的に管理されます。CPU スケジューリング:オペレーティング システムも循環キューを使用してプロセスを挿入し、実行します。交通システム:コンピュータ制御の交通システムにおいて、信号機は循環列の最良の例の 1 つです。信号機の各ライトは、一定時間ごとに 1 つずつ点灯します。赤色のライトが 1 分間点灯し、次に黄色のライトが 1 分間点灯し、次に緑色のライトが点灯するようにします。緑色に点灯した後、赤色が点灯します。

エンキュー操作

エンキュー操作の手順は次のとおりです。

• まず、Queue がいっぱいかどうかを確認します。
• 最初はフロントとリアが -1 に設定されています。 Queue に最初の要素を挿入すると、前後の要素が両方とも 0 に設定されます。
• 新しい要素を挿入すると、後部が増分されます。 リア=リア+1 。

要素を挿入するシナリオ

キューがいっぱいではないシナリオは 2 つあります。

リアの場合 != max - 1、その後リアは に増加します mod(最大サイズ) 新しい値はキューの最後に挿入されます。フロント != 0、リア = max - 1 の場合、これはキューがいっぱいではないことを意味し、rear の値を 0 に設定し、そこに新しい要素を挿入します。

要素を挿入できないケースは 2 つあります。

ラヴェルはPythonで何をしますか

プッシュ用の git コマンド

ステップ 3: フロント = リアの場合
フロント = リア = -1 を設定
それ以外
フロント = 最大 -1 の場合
フロントセット = 0
それ以外
フロントを設定 = フロント + 1
[IFの終わり]
[IFの終わり]

ステップ 4: 出口

図による表現を通じて、エンキューとデキューの操作を理解しましょう。

配列を使用した循環キューの実装

 #include # define max 6 int queue[max]; // array declaration int front=-1; int rear=-1; // function to insert an element in a circular queue void enqueue(int element) { if(front==-1 && rear==-1) // condition to check queue is empty { front=0; rear=0; queue[rear]=element; } else if((rear+1)%max==front) // condition to check queue is full { printf('Queue is overflow..'); } else { rear=(rear+1)%max; // rear is incremented queue[rear]=element; // assigning a value to the queue at the rear position. } } // function to delete the element from the queue int dequeue() { if((front==-1) && (rear==-1)) // condition to check queue is empty { printf('
Queue is underflow..'); } else if(front==rear) { printf('
The dequeued element is %d', queue[front]); front=-1; rear=-1; } else { printf('
The dequeued element is %d', queue[front]); front=(front+1)%max; } } // function to display the elements of a queue void display() { int i=front; if(front==-1 && rear==-1) { printf('
 Queue is empty..'); } else { printf('
Elements in a Queue are :&apos;); while(i<=rear) { printf('%d,', queue[i]); i="(i+1)%max;" } int main() choice="1,x;" variables declaration while(choice<4 && choice!="0)" while loop printf('
 press 1: insert an element'); printf('
press 2: delete 3: display the printf('
enter your choice'); scanf('%d', &choice); switch(choice) case printf('enter element which is to be inserted'); &x); enqueue(x); break; dequeue(); display(); }} return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/14/circular-queue-10.webp" alt="Circular Queue"> <h3>Implementation of circular queue using linked list</h3> <p>As we know that linked list is a linear data structure that stores two parts, i.e., data part and the address part where address part contains the address of the next node. Here, linked list is used to implement the circular queue; therefore, the linked list follows the properties of the Queue. When we are implementing the circular queue using linked list then both the <strong> <em>enqueue and dequeue</em> </strong> operations take <strong> <em>O(1)</em> </strong> time.</p> <pre> #include // Declaration of struct type node struct node { int data; struct node *next; }; struct node *front=-1; struct node *rear=-1; // function to insert the element in the Queue void enqueue(int x) { struct node *newnode; // declaration of pointer of struct node type. newnode=(struct node *)malloc(sizeof(struct node)); // allocating the memory to the newnode newnode-&gt;data=x; newnode-&gt;next=0; if(rear==-1) // checking whether the Queue is empty or not. { front=rear=newnode; rear-&gt;next=front; } else { rear-&gt;next=newnode; rear=newnode; rear-&gt;next=front; } } // function to delete the element from the queue void dequeue() { struct node *temp; // declaration of pointer of node type temp=front; if((front==-1)&amp;&amp;(rear==-1)) // checking whether the queue is empty or not { printf(&apos;
Queue is empty&apos;); } else if(front==rear) // checking whether the single element is left in the queue { front=rear=-1; free(temp); } else { front=front-&gt;next; rear-&gt;next=front; free(temp); } } // function to get the front of the queue int peek() { if((front==-1) &amp;&amp;(rear==-1)) { printf(&apos;
Queue is empty&apos;); } else { printf(&apos;
The front element is %d&apos;, front-&gt;data); } } // function to display all the elements of the queue void display() { struct node *temp; temp=front; printf(&apos;
 The elements in a Queue are : &apos;); if((front==-1) &amp;&amp; (rear==-1)) { printf(&apos;Queue is empty&apos;); } else { while(temp-&gt;next!=front) { printf(&apos;%d,&apos;, temp-&gt;data); temp=temp-&gt;next; } printf(&apos;%d&apos;, temp-&gt;data); } } void main() { enqueue(34); enqueue(10); enqueue(23); display(); dequeue(); peek(); } </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/14/circular-queue-11.webp" alt="Circular Queue"> <hr></=rear)>

出力：