DS KRUŽNI RED ČEKANJA

Zašto je uveden koncept kružnog reda?

Postojalo je jedno ograničenje u implementaciji polja

Kao što možemo vidjeti na gornjoj slici, stražnja strana je na posljednjoj poziciji reda čekanja, a prednja strana pokazuje negdje, a ne 0^thpoložaj. U gornjem nizu postoje samo dva elementa, a ostale tri pozicije su prazne. Stražnja strana je na zadnjoj poziciji u redu čekanja; ako pokušamo umetnuti element tada će pokazati da nema praznih mjesta u redu čekanja. Postoji jedno rješenje za izbjegavanje takvog rasipanja memorijskog prostora pomicanjem oba elementa ulijevo i prilagođavanjem prednjeg i stražnjeg kraja u skladu s tim. To nije praktički dobar pristup jer će pomicanje svih elemenata oduzeti puno vremena. Učinkovit pristup izbjegavanju rasipanja memorije je korištenje strukture podataka kružnog reda čekanja.

Što je kružni red čekanja?

Kružni red čekanja sličan je linearnom redu čekanja jer se također temelji na FIFO principu (First In First Out) osim što je posljednja pozicija povezana s prvom pozicijom u kružnom redu čekanja koja tvori krug. Također je poznat kao a Međuspremnik zvona .

Operacije na kružnom redu čekanja

Sljedeće su operacije koje se mogu izvesti na kružnom redu čekanja:

Ispred:Koristi se za dobivanje prednjeg elementa iz reda čekanja.straga:Koristi se za dobivanje stražnjeg elementa iz reda čekanja.EnQueue(vrijednost):Ova se funkcija koristi za umetanje nove vrijednosti u red čekanja. Novi element uvijek se umeće sa stražnje strane.dequeue():Ova funkcija briše element iz reda čekanja. Brisanje u redu čekanja uvijek se odvija s prednje strane.

Primjene kružnog reda čekanja

Kružni red čekanja može se koristiti u sljedećim scenarijima:

Upravljanje memorijom:Kružni red omogućuje upravljanje memorijom. Kao što smo već vidjeli, u linearnom redu čekanja memorijom se ne upravlja vrlo učinkovito. Ali u slučaju kružnog reda čekanja, memorijom se učinkovito upravlja postavljanjem elemenata na mjesto koje se ne koristi.CPU raspored:Operativni sustav također koristi kružni red čekanja za umetanje procesa i njihovo izvršavanje.Prometni sustav:U sustavu računalnog upravljanja prometom, semafor je jedan od najboljih primjera kružnog reda čekanja. Svako svjetlo na semaforu se pali jedno po jedno nakon svakog vremenskog intervala. Kao što se crveno svjetlo pali jednu minutu, zatim žuto svjetlo jednu minutu i zatim zeleno svjetlo. Nakon zelenog svjetla pali se crveno svjetlo.

Stavljanje u red čekanja

Koraci operacije stavljanja u red čekanja navedeni su u nastavku:

Prvo ćemo provjeriti je li red čekanja pun ili ne.
U početku su prednji i stražnji dio postavljeni na -1. Kada umetnemo prvi element u red čekanja, i prednji i stražnji su postavljeni na 0.
Kada umetnemo novi element, stražnji dio se povećava, tj. straga=straga+1 .

Scenariji za umetanje elementa

Postoje dva scenarija u kojima red čekanja nije pun:

mod (maksimalna veličina)

Postoje dva slučaja u kojima se element ne može umetnuti:

Kada prednji ==0 && straga = max-1 , što znači da je prednji dio na prvoj poziciji u redu čekanja, a stražnji dio na zadnjoj poziciji u redu čekanja.
prednji== stražnji + 1;

Algoritam za umetanje elementa u kružni red

Korak 1: AKO (STRAGA+1)%MAX = NAPRIJED
Napišite 'PRELIVANJE'
Idi na korak 4
[KRAJ AKO]

Korak 2: AKO je NAPRIJED = -1 i STRAGA = -1
POSTAVITE NAPRIJED = STRAGA = 0
INAČE AKO STRAGA = MAX - 1 i PREDNJE! = 0
POSTAVITE STRAŽNJI = 0
DRUGO
POSTAVITE STRAŽNJI = (STRAŽNJI + 1) % MAKS
[KRAJ AKO]

Korak 3: POSTAVITE ČEK [STRAŽNJI] = VRED

Korak 4: IZLAZ

Operacija uklanjanja iz reda čekanja

Koraci operacije uklanjanja iz reda čekanja navedeni su u nastavku:

Prvo provjeravamo je li red čekanja prazan ili ne. Ako je red čekanja prazan, ne možemo izvršiti operaciju uklanjanja reda čekanja.
Kada se element izbriše, vrijednost fronta se smanjuje za 1.
Ako je preostao samo jedan element koji treba izbrisati, tada se prednji i stražnji dio vraćaju na -1.

Algoritam za brisanje elementa iz kružnog reda čekanja

for petlja u c

Korak 1: AKO JE NAPRIJED = -1
Napišite ' UNDERFLOW '
Idi na korak 4
[KRAJ AKO]

Korak 2: POSTAVITE VAL = QUEUE[FRONT]

Korak 3: AKO JE NAPRIJED = STRAGA
POSTAVITE NAPRIJED = STRAGA = -1
DRUGO
AKO JE NAPRIJED = MAX -1
POSTAVITE NAPRIJED = 0
DRUGO
POSTAVITE NAPRIJED = NAPRIJED + 1
[KRAJ AKO]
[KRAJ AKO]

Korak 4: IZLAZ

Razumimo operaciju stavljanja u red i uklanjanja iz reda kroz dijagramski prikaz.

Implementacija kružnog reda čekanja pomoću polja

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

Izlaz: