KRUHOVÁ FRONTA DS

Proč byl zaveden koncept kruhové fronty?

V implementaci pole bylo jedno omezení

Jak můžeme vidět na obrázku výše, zadní část je na poslední pozici fronty a přední část ukazuje někam spíše než 0^čtpozice. Ve výše uvedeném poli jsou pouze dva prvky a další tři pozice jsou prázdné. Zadní část je na poslední pozici fronty; pokud se pokusíme vložit prvek, ukáže se, že ve frontě nejsou žádná prázdná místa. Existuje jedno řešení, jak se takovému plýtvání paměťovým prostorem vyhnout, posunutím obou prvků doleva a odpovídajícím nastavením přední a zadní části. Není to prakticky dobrý přístup, protože přesunutí všech prvků zabere spoustu času. Efektivním přístupem k zamezení plýtvání pamětí je použití kruhové datové struktury fronty.

Co je kruhová fronta?

Kruhová fronta je podobná lineární frontě, protože je také založena na principu FIFO (First In First Out) kromě toho, že poslední pozice je spojena s první pozicí v kruhové frontě, která tvoří kruh. Je také známý jako a Ring Buffer .

Operace na kruhové frontě

V kruhové frontě lze provádět následující operace:

Přední:Používá se k získání předního prvku z fronty.Zadní:Používá se k získání zadního prvku z fronty.enQueue(hodnota):Tato funkce se používá k vložení nové hodnoty do fronty. Nový prvek se vždy vkládá ze zadního konce.deQueue():Tato funkce odstraní prvek z fronty. Smazání ve frontě vždy probíhá z frontendu.

Aplikace kruhové fronty

Kruhovou frontu lze použít v následujících scénářích:

Správa paměti:Kruhová fronta zajišťuje správu paměti. Jak jsme již viděli, v lineární frontě není paměť spravována příliš efektivně. Ale v případě kruhové fronty je paměť spravována efektivně umístěním prvků na místo, které se nepoužívá.Plánování CPU:Operační systém také používá kruhovou frontu k vložení procesů a jejich následnému spuštění.Dopravní systém:V počítačově řízeném dopravním systému je semafor jedním z nejlepších příkladů kruhové fronty. Každé světlo semaforu se rozsvěcí jedno po druhém po každém časovém intervalu. Jako by se na jednu minutu rozsvítilo červené světlo, pak na minutu žluté světlo a pak zelené světlo. Po zeleném světle se rozsvítí červené světlo.

Operace zařazení do fronty

Kroky operace enqueue jsou uvedeny níže:

Nejprve zkontrolujeme, zda je fronta plná nebo ne.
Zpočátku jsou přední a zadní část nastaveny na -1. Když vložíme první prvek do fronty, přední i zadní jsou nastaveny na 0.
Když vložíme nový prvek, zadní část se zvětší, tj. zadní=zadní+1 .

Scénáře pro vložení prvku

Existují dva scénáře, kdy fronta není plná:

mod(maxsize)

Existují dva případy, kdy prvek nelze vložit:

konkretizace v Javě

Když přední ==0 && zadní = max-1 , což znamená, že přední strana je na první pozici fronty a zadní strana je na poslední pozici fronty.
přední == zadní + 1;

Algoritmus pro vložení prvku do kruhové fronty

Krok 1: POKUD (ZADNÍ+1)%MAX = PŘEDNÍ
Napište ' PŘETEČENÍ '
Přejděte na krok 4
[Konec POKUD]

částečná diferenciace v latexu

Krok 2: POKUD PŘEDNÍ = -1 a ZADNÍ = -1
SET FRONT = REAR = 0
JINAK POKUD ZADNÍ = MAX - 1 a PŘEDNÍ ! = 0
SET REAR = 0
JINÝ
SET REAR = (REAR + 1) % MAX
[KONEC POKUD]

Krok 3: SET QUEUE[REAR] = HODNOTA

Krok 4: VÝSTUP

Vyřazení z fronty

Kroky operace dequeue jsou uvedeny níže:

Nejprve zkontrolujeme, zda je fronta prázdná nebo ne. Pokud je fronta prázdná, nemůžeme operaci vyřazení z fronty provést.
Když je prvek odstraněn, hodnota fronty se sníží o 1.
Pokud zbývá pouze jeden prvek, který má být vymazán, pak se přední a zadní část resetují na -1.

Algoritmus pro odstranění prvku z kruhové fronty

Krok 1: POKUD PŘEDNÍ = -1
Napište 'POTEČENÍ'
Přejděte na krok 4
[KONEC IF]

prioritní fronta c++

Krok 2: NASTAVIT HODNOTU = FRONTA[FRONT]

Krok 3: POKUD PŘEDNÍ = ZADNÍ
SET PŘEDNÍ = ZADNÍ = -1
JINÝ
POKUD PŘEDNÍ = MAX -1
SET FRONT = 0
JINÝ
SET FRONT = FRONT + 1
[KONEC IF]
[KONEC POKUD]

Krok 4: VÝSTUP

Pojďme porozumět operaci zařazování a vyřazování z fronty prostřednictvím schematického znázornění.

Implementace kruhové fronty pomocí 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 &amp;&amp; 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(&apos;Queue is overflow..&apos;); } 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) &amp;&amp; (rear==-1)) // condition to check queue is empty { printf(&apos;
Queue is underflow..&apos;); } else if(front==rear) { printf(&apos;
The dequeued element is %d&apos;, queue[front]); front=-1; rear=-1; } else { printf(&apos;
The dequeued element is %d&apos;, queue[front]); front=(front+1)%max; } } // function to display the elements of a queue void display() { int i=front; if(front==-1 &amp;&amp; rear==-1) { printf(&apos;
 Queue is empty..&apos;); } else { printf(&apos;
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)>

Výstup: