TechCodeview

Чому було введено поняття кругової черги?

У реалізації масиву було одне обмеження

Як ми можемо бачити на зображенні вище, задня частина знаходиться в останній позиції черги, а передня частина вказує кудись, а не на 0^тисположення. У наведеному вище масиві лише два елементи, а інші три позиції порожні. Задня частина знаходиться в останній позиції черги; якщо ми спробуємо вставити елемент, тоді він покаже, що в черзі немає порожніх місць. Є одне рішення, щоб уникнути такої втрати пам’яті, перемістивши обидва елементи ліворуч і відповідно налаштувавши передню та задню частини. Практично це не дуже хороший підхід, тому що пересування всіх елементів займе багато часу. Ефективним підходом до уникнення втрати пам’яті є використання структури даних циклічної черги.

Що таке циклічна черга?

Кругова черга подібна до лінійної черги, оскільки вона також базується на принципі FIFO (першим прийшов, першим вийшов), за винятком того, що остання позиція з’єднана з першою позицією в кільцевій черзі, яка утворює коло. Він також відомий як a Кільцевий буфер .

java switch int

алгоритми сортування злиття сортування

крок 4: ВИХІД

Операція видалення з черги

Нижче наведено кроки операції вилучення з черги:

• Спочатку ми перевіряємо, порожня Черга чи ні. Якщо черга порожня, ми не можемо виконати операцію вилучення з черги.
• Коли елемент видаляється, значення фронту зменшується на 1.
• Якщо залишився лише один елемент, який потрібно видалити, передня і задня частина скидаються до -1.

Алгоритм видалення елемента з циклічної черги

Крок 1: IF FRONT = -1
Напишіть 'UNDERFLOW'
Перейти до кроку 4
[КІНЕЦЬ ЯКЩО]

Крок 2: SET VAL = QUEUE[FRONT]

крок 3: ЯКЩО СПЕРЕД = ЗАДНІЙ
ВСТАНОВИТИ ПЕРЕДНІЙ = ЗАДНИЙ = -1
ІНШЕ
IF FRONT = MAX -1
SET FRONT = 0
ІНШЕ
SET FRONT = FRONT + 1
[КІНЕЦЬ ЯКЩО]
[КІНЕЦЬ ЯКЩО]

крок 4: ВИХІД

Давайте розберемося з операціями постановки в чергу та вилучення з черги через діаграмне представлення.

Реалізація циклічної черги з використанням Array

 #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)>

Вихід: