KRUHOVÝ RAD DS - NÁVOD DS

Prečo bol zavedený koncept kruhového radu?

V implementácii poľa existovalo jedno obmedzenie

Ako môžeme vidieť na obrázku vyššie, zadná časť je na poslednej pozícii fronty a predná časť smeruje niekam namiesto 0^thpozíciu. Vo vyššie uvedenom poli sú iba dva prvky a ďalšie tri pozície sú prázdne. Zadná časť je na poslednej pozícii frontu; ak sa pokúsime vložiť prvok, ukáže sa, že vo fronte nie sú žiadne prázdne miesta. Existuje jedno riešenie, ako sa vyhnúť takémuto plytvaniu pamäťovým priestorom posunutím oboch prvkov doľava a zodpovedajúcim nastavením predného a zadného konca. Nie je to prakticky dobrý prístup, pretože presunutie všetkých prvkov zaberie veľa času. Efektívnym prístupom, ako sa vyhnúť plytvaniu pamäťou, je použiť dátovú štruktúru kruhového frontu.

Čo je to kruhový rad?

Kruhový rad je podobný lineárnemu radu, pretože je tiež založený na princípe FIFO (First In First Out) okrem toho, že posledná pozícia je spojená s prvou pozíciou v kruhovom rade, ktorý tvorí kruh. Je tiež známy ako a Ring Buffer .

Operácie v kruhovom rade

Nasledujú operácie, ktoré možno vykonať v kruhovom fronte:

Predná časť:Používa sa na získanie predného prvku z frontu.zadná časť:Používa sa na získanie zadného prvku z frontu.enQueue(hodnota):Táto funkcia sa používa na vloženie novej hodnoty do frontu. Nový prvok sa vždy vkladá zo zadnej strany.deQueue():Táto funkcia vymaže prvok z frontu. Odstránenie vo fronte sa vždy uskutoční z frontendu.

Aplikácie Circular Queue

Kruhový front možno použiť v nasledujúcich scenároch:

fonty pre gimp

Správa pamäte:Kruhový rad poskytuje správu pamäte. Ako sme už videli, v lineárnom rade sa pamäť nespravuje veľmi efektívne. Ale v prípade kruhového radu je pamäť riadená efektívne umiestnením prvkov na miesto, ktoré sa nepoužíva.Plánovanie CPU:Operačný systém tiež používa kruhový front na vloženie procesov a ich následné vykonanie.Dopravný systém:V počítačovo riadenom dopravnom systéme je semafor jedným z najlepších príkladov kruhového radu. Každé svetlo semaforu sa rozsvieti jeden po druhom po každom časovom intervale. Akoby sa na jednu minútu rozsvietilo červené svetlo, potom na jednu minútu žlté svetlo a potom zelené svetlo. Po zelenom svetle sa rozsvieti červené svetlo.

Prevádzka zaradenia

Kroky operácie zaraďovania sú uvedené nižšie:

Najprv skontrolujeme, či je front plný alebo nie.
Na začiatku je predná a zadná časť nastavená na -1. Keď vložíme prvý prvok do frontu, predné aj zadné sú nastavené na 0.
Keď vložíme nový prvok, zadná časť sa zvýši, t.j. zadný=zadný+1 .

Scenáre na vloženie prvku

Existujú dva scenáre, v ktorých nie je front plný:

mod(maxsize)

Existujú dva prípady, v ktorých prvok nemožno vložiť:

Kedy vpredu ==0 && vzadu = max-1 , čo znamená, že predná časť je na prvej pozícii poradia a zadná časť je na poslednej pozícii poradia.
predné = = zadné + 1;

Algoritmus na vloženie prvku do kruhového radu

Krok 1: AK (ZADNÉ+1)%MAX = PREDNÉ
Napíšte ' PRETEČENIE '
Prejdite na krok 4
[Koniec AK]

Krok 2: AK PREDNÉ = -1 a ZADNÉ = -1
SET PREDNÁ = REAR = 0
INAK AK ZADNÉ = MAX - 1 a PREDNÉ ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[KONIEC AK]

java objekt do json

Krok 3: SET QUEUE[REAR] = HODNOTA

triedenie zoznamov java

Krok 4: VÝCHOD

Dequeue Operation

Kroky operácie dequeue sú uvedené nižšie:

Najprv skontrolujeme, či je front prázdny alebo nie. Ak je front prázdny, nemôžeme vykonať operáciu dequeue.
Po odstránení prvku sa hodnota frontu zníži o 1.
Ak zostane len jeden prvok, ktorý sa má vymazať, predná a zadná časť sa nastavia na -1.

Algoritmus na odstránenie prvku z kruhového frontu

Krok 1: AK PREDNÁ = -1
Napíšte „PODETOK“
Prejdite na krok 4
[KONIEC AK]

Krok 2: NASTAVIŤ HODNOTU = QUEUE[FRONT]

Krok 3: AK PREDNÉ = ZADNÉ
SET PREDNÁ = REAR = -1
ELSE
AK PREDNÁ = MAX -1
SET PREDNÁ = 0
ELSE
SET FRONT = FRONT + 1
[KONIEC AK]
[KONIEC AK]

trie dátovú štruktúru

Krok 4: VÝCHOD

Poďme pochopiť operáciu zaraďovania a vyraďovania z frontu prostredníctvom schematického znázornenia.

Implementácia kruhovej fronty pomocou 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ýkon: