logo

Cirkulær kø

Hvorfor blev konceptet med den cirkulære kø introduceret?

Der var én begrænsning i array-implementeringen af

Som vi kan se på billedet ovenfor, er bagsiden i den sidste position i køen, og fronten peger et sted hen i stedet for 0thposition. I ovenstående array er der kun to elementer, og tre andre positioner er tomme. Bagsiden er i den sidste position i køen; hvis vi forsøger at indsætte elementet, vil det vise, at der ikke er tomme mellemrum i køen. Der er én løsning til at undgå et sådant spild af hukommelsesplads ved at flytte begge elementer til venstre og justere for- og bagenden i overensstemmelse hermed. Det er ikke en praktisk god tilgang, fordi at skifte alle elementer vil forbruge masser af tid. Den effektive tilgang til at undgå spild af hukommelsen er at bruge den cirkulære kødatastruktur.

Hvad er en cirkulær kø?

En cirkulær kø ligner en lineær kø, da den også er baseret på FIFO-princippet (First In First Out) bortset fra, at den sidste position er forbundet med den første position i en cirkulær kø, der danner en cirkel. Det er også kendt som en Ringbuffer .

listenode

Operationer på cirkulær kø

Følgende er de operationer, der kan udføres på en cirkulær kø:

    Foran:Det bruges til at hente frontelementet fra køen.Bag:Det bruges til at hente det bagerste element fra køen.enQueue(værdi):Denne funktion bruges til at indsætte den nye værdi i køen. Det nye element indsættes altid fra bagenden.deQueue():Denne funktion sletter et element fra køen. Sletningen i en kø foregår altid fra frontenden.

Anvendelser af Circular Queue

Den cirkulære kø kan bruges i følgende scenarier:

    Hukommelseshåndtering:Den cirkulære kø giver hukommelsesstyring. Som vi allerede har set, styres hukommelsen i lineær kø ikke særlig effektivt. Men i tilfælde af en cirkulær kø, styres hukommelsen effektivt ved at placere elementerne på et sted, som er ubrugt.CPU-planlægning:Operativsystemet bruger også den cirkulære kø til at indsætte processerne og derefter udføre dem.Trafiksystem:I et computerstyret trafiksystem er trafiklys et af de bedste eksempler på den cirkulære kø. Hvert lys i lyskrydset tænder et efter et efter hvert tidsinterval. Ligesom rødt lys tændes i et minut, derefter gult lys i et minut og derefter grønt lys. Efter grønt lys tændes det røde lys.

Drift i kø

Trinene til kødrift er angivet nedenfor:

  • Først vil vi kontrollere, om køen er fuld eller ej.
  • Til at begynde med er for- og bagsiden indstillet til -1. Når vi indsætter det første element i en kø, er både front og bag sat til 0.
  • Når vi indsætter et nyt element, øges bagsiden, dvs. bag=bag+1 .

Scenarier for indsættelse af et element

Der er to scenarier, hvor køen ikke er fuld:

    Hvis bag != max - 1, så vil bagsiden blive forøget til mod (maxsize) og den nye værdi vil blive indsat bagerst i køen.Hvis front != 0 og bagside = max - 1, betyder det, at køen ikke er fuld, så sæt værdien af ​​bag til 0 og indsæt det nye element der.

Der er to tilfælde, hvor elementet ikke kan indsættes:

  • Hvornår foran ==0 && bag = max-1 , hvilket betyder, at fronten er i den første position i køen og den bagerste er i den sidste position i køen.
  • forside== bagside + 1;

Algoritme til at indsætte et element i en cirkulær kø

Trin 1: HVIS (REAR+1)%MAX = FRONT
Skriv ' OVERFLØD '
Gå til trin 4
[SLUT PÅ HVIS]

Trin 2: HVIS FRONT = -1 og BAG = -1
INDSTILL FRONT = BAG = 0
ANDET HVIS BAG = MAX - 1 og FRONT ! = 0
SÆT BAG = 0
ANDET
INDSTIL BAG = (BAG + 1) % MAKS
[SLUT PÅ HVIS]

Trin 3: SÆT KØ[BAGESTE] = VÆRDI

ls kommandoer linux

Trin 4: AFSLUT

Udskydelse af kø

Trinene for dekødrift er angivet nedenfor:

  • Først tjekker vi, om køen er tom eller ej. Hvis køen er tom, kan vi ikke udføre dekø-handlingen.
  • Når elementet slettes, bliver værdien af ​​front reduceret med 1.
  • Hvis der kun er ét element tilbage, som skal slettes, så nulstilles front og bag til -1.

Algoritme til at slette et element fra den cirkulære kø

Trin 1: HVIS FRONT = -1
Skriv ' UNDERFLØD '
Gå til trin 4
[SLUT AF HVIS]

Trin 2: INDSTIL VÆRDI = KØ[FRONT]

Trin 3: HVIS FRONT = BAG
SÆT FORAN = BAG = -1
ANDET
HVIS FRONT = MAKS -1
SÆT FRONT = 0
ANDET
SÆT FRONT = FRONT + 1
[SLUT AF HVIS]
[SLUT PÅ HVIS]

Trin 4: AFSLUT

Lad os forstå enqueue og dequeue operationen gennem den diagrammatiske repræsentation.

Cirkulær kø
Cirkulær kø
Cirkulær kø
Cirkulær kø
Cirkulær kø
Cirkulær kø
Cirkulær kø
Cirkulær kø

Implementering af cirkulær kø ved hjælp af 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)>

Produktion:

Cirkulær kø