logo

TechCodeview

Krožna čakalna vrsta

Zakaj je bil uveden koncept krožne čakalne vrste?

Pri implementaciji matrike je bila ena omejitev

Kot lahko vidimo na zgornji sliki, je zadnji del na zadnjem položaju čakalne vrste, sprednji del pa kaže nekam in ne 0thpoložaj. V zgornjem nizu sta samo dva elementa, drugi trije položaji pa so prazni. Zadnji del je na zadnjem položaju v čakalni vrsti; če poskušamo vstaviti element, bo prikazano, da v čakalni vrsti ni praznih prostorov. Obstaja ena rešitev, da se izognete takšni izgubi pomnilniškega prostora, tako da premaknete oba elementa na levo in ustrezno prilagodite sprednji in zadnji del. Praktično ni dober pristop, saj bo prestavljanje vseh elementov vzelo veliko časa. Učinkovit pristop, da se izognete izgubi pomnilnika, je uporaba podatkovne strukture krožne čakalne vrste.

Kaj je krožna čakalna vrsta?

Krožna čakalna vrsta je podobna linearni čakalni vrsti, saj prav tako temelji na načelu FIFO (First In First Out), le da je zadnji položaj povezan s prvim položajem v krožni čakalni vrsti, ki tvori krog. Znan je tudi kot a Medpomnilnik zvonjenja .

Operacije v krožni čakalni vrsti

Naslednje so operacije, ki jih je mogoče izvesti v krožni čakalni vrsti:

    Spredaj:Uporablja se za pridobivanje sprednjega elementa iz čakalne vrste.Zadaj:Uporablja se za pridobitev zadnjega elementa iz čakalne vrste.enQueue(vrednost):Ta funkcija se uporablja za vstavljanje nove vrednosti v čakalno vrsto. Nov element se vedno vstavi z zadnje strani.deQueue():Ta funkcija izbriše element iz čakalne vrste. Brisanje v čakalni vrsti vedno poteka s sprednje strani.

Aplikacije krožne čakalne vrste

Krožno čakalno vrsto je mogoče uporabiti v naslednjih scenarijih:

    Upravljanje pomnilnika:Krožna čakalna vrsta omogoča upravljanje pomnilnika. Kot smo že videli, se v linearni čakalni vrsti pomnilnik ne upravlja zelo učinkovito. Toda v primeru krožne čakalne vrste se pomnilnik učinkovito upravlja tako, da se elementi postavijo na neuporabljeno mesto.Razporejanje procesorja:Operacijski sistem uporablja tudi krožno čakalno vrsto za vstavljanje procesov in njihovo izvajanje.Prometni sistem:V računalniško vodenem prometnem sistemu je semafor eden najboljših primerov krožne čakalne vrste. Vsaka luč na semaforju se prižge ena za drugo po vsakem časovnem intervalu. Kot da se za eno minuto prižge rdeča luč, nato za eno minuto rumena in nato zelena. Po zeleni luči se prižge rdeča luč.

Postopek v čakalni vrsti

Spodaj so navedeni koraki delovanja v čakalni vrsti:

primeri dfa
  • Najprej bomo preverili, ali je čakalna vrsta polna ali ne.
  • Sprva sta sprednji in zadnji del nastavljena na -1. Ko vstavimo prvi element v čakalno vrsto, sta sprednji in zadnji element nastavljena na 0.
  • Ko vstavimo nov element, se zadnja stran poveča, tj. zadaj=zadaj+1 .

Scenariji za vstavljanje elementa

Obstajata dva scenarija, v katerih čakalna vrsta ni polna:

    Če je zadaj != max - 1, potem bo zadaj povečan na mod (največja velikost) in nova vrednost bo vstavljena na zadnji konec čakalne vrste.Če je spredaj != 0 in zadaj = max - 1, to pomeni, da čakalna vrsta ni polna, nato nastavite vrednost rear na 0 in tja vstavite nov element.

Obstajata dva primera, v katerih elementa ni mogoče vstaviti:

  • Kdaj spredaj ==0 && zadaj = max-1 , kar pomeni, da je sprednja stran na prvem mestu čakalne vrste, zadnja stran pa na zadnji poziciji čakalne vrste.
  • spredaj== zadaj + 1;

Algoritem za vstavljanje elementa v krožno čakalno vrsto

Korak 1: ČE (ZADAJ+1)%MAX = SPREDAJ
Napišite 'OVERFLOW'
Pojdite na 4. korak
[KONEC ČE]

2. korak: ČE SPREDAJ = -1 in ZADAJ = -1
NASTAVI SPREDAJ = ZADAJ = 0
ALSE IF REAR = MAX - 1 in SPREDAJ ! = 0
NASTAVITE ZADAJ = 0
DRUGEGA
NASTAVITE ZADAJ = (ZADAJ + 1) % NAJV
[KONEC ČE]

3. korak: NASTAVI ČAKALNO VRSTO [ZADAJ] = VRED

4. korak: IZHOD

Operacija odstranitve iz čakalne vrste

Spodaj so navedeni koraki za odstranitev iz čakalne vrste:

  • Najprej preverimo, ali je čakalna vrsta prazna ali ne. Če je čakalna vrsta prazna, ne moremo izvesti operacije odstranitve iz čakalne vrste.
  • Ko je element izbrisan, se vrednost fronte zmanjša za 1.
  • Če ostane le še en element, ki ga želite izbrisati, se sprednji in zadnji del ponastavita na -1.

Algoritem za brisanje elementa iz krožne čakalne vrste

Korak 1: ČE SPREDAJ = -1
Napišite 'UNDERFLOW'
Pojdite na 4. korak
[KONEC ČE]

2. korak: NASTAVI VRED = ČAKALNA VRSTA[SPREDAJ]

3. korak: ČE SPREDAJ = ZADAJ
NASTAVI SPREDAJ = ZADAJ = -1
DRUGEGA
ČE SPREDAJ = NAJVEČ -1
NASTAVI SPREDAJ = 0
DRUGEGA
NASTAVI SPREDAJ = SPREDAJ + 1
[KONEC ČE]
[KONEC ČE]

4. korak: IZHOD

Razumejmo operacijo postavljanja v čakalno vrsto in odstranjevanja iz čakalne vrste s pomočjo diagramske predstavitve.

Krožna čakalna vrsta
Krožna čakalna vrsta
Krožna čakalna vrsta
Krožna čakalna vrsta
Krožna čakalna vrsta
Krožna čakalna vrsta
Krožna čakalna vrsta
Krožna čakalna vrsta

Implementacija krožne čakalne vrste z uporabo 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)>

Izhod:

Krožna čakalna vrsta