c circular queue data structure
Denna handledning om C ++ cirkulär ködatastruktur förklarar vad som är cirkulär kö, vad är de grundläggande funktionerna tillsammans med implementering och applikationer:
En cirkulär kö är en förlängning av baskön som vi har diskuterat tidigare. Det är också känt som “Ringbuffert”.
Vad är cirkulär kö i C ++?
En cirkulär kö är en linjär datastruktur som används för att lagra dataobjekt. Den utför operationer genom att följa FIFO (First In, First Out) -metoden och den sista positionen i kön är ansluten tillbaka till den första positionen för att bilda en cirkel.
=> Leta efter hela C ++ träningsserien här
Vad du kommer att lära dig:
Cirkulär kö i C ++
Följande diagram visar en cirkulär kö.
Ovanstående bild visar en cirkulär datastruktur av storlek 10. De första sex elementen finns redan i kön och vi ser att den första positionen och den sista positionen är sammanfogade. På grund av detta arrangemang går inte utrymme till spillo eftersom det händer i en linjär kö.
vilket etl-verktyg som är bäst på marknaden
I en linjär kö efter att kön är full raderar vi elementen från en annan ände, och status för kön visas fortfarande som full och vi kan inte infoga fler element.
I den cirkulära kön, när kön är full och när vi tar bort element från framsidan sedan de sista och första positionerna är anslutna, kan vi infoga elementen på baksidan som lämnades genom att ta bort elementet.
I nästa avsnitt lär vi oss om de grundläggande funktionerna i den cirkulära köen.
Grundläggande funktioner
Några av de grundläggande funktionerna i den cirkulära kön är följande:
Främre: Returnerar främre position i den cirkulära köen.
Bak: Returnerar den bakre positionen i den cirkulära kön.
Enqueue: Enqueue (värde) används för att infoga ett element i den cirkulära kön. Elementet sätts alltid in i den bakre änden av kön.
Vi följer följande sekvens av steg för att infoga ett nytt element i den cirkulära kön.
# 1) Kontrollera om den cirkulära kön är full: test ((bakre == STORLEK-1 && front == 0) || (bakre == front-1)), där ”STORLEK” är storleken på den cirkulära kön.
#två) Om den cirkulära kön är full visas ett meddelande som ”Kön är full”. Om kön inte är full, kontrollera om (bakre == STORLEK - 1 && front! = 0). Om det är sant, ställ in bakre = 0 och sätt in elementet.
hur man öppnar .jar-filer
Dequeue: Dequeue-funktionen används för att radera ett element från kön. I den cirkulära kön raderas alltid elementet från fronten. Nedan följer sekvensen för dequeue-drift i en cirkulär kö.
Steg:
# 1) Kontrollera om den cirkulära kön är tom: kontrollera om (front == - 1).
#två) Om den är tom, visa meddelandet 'Kön är tom'. Om kön inte är tom utför du steg 3.
# 3) Kontrollera om (fram = = bak). Om det är sant, ställ in front = bak = -1 annars kontrollera om (front == storlek-1), om det är sant, ställ in front = 0 och returnera elementet.
Illustration
I det här avsnittet går vi igenom en detaljerad illustration av hur du lägger till / tar bort element i den cirkulära kön.
Tänk på följande cirkulära kö med 5 element som visas nedan:
Därefter infogar vi objekt 1 i kön.
Därefter infogar vi ett objekt med värde 3.
När vi sätter in elementen för att göra en kö full, kommer representationen att visas som nedan.
Nu tar vi bort de två elementen, dvs artikel 1 och artikel 3 från kön enligt nedan.
Därefter infogar eller förser vi element 11 i den cirkulära kön som visas nedan.
Låt oss åter infoga element 13 i den cirkulära kön. Kön ser ut som visas nedan.
Vi ser att vi i den cirkulära kön flyttar eller infogar element i en cirkel. Därför kan vi konsumera hela utrymmet i kön tills den blir full.
Genomförande
Låt oss implementera den cirkulära kön med C ++.
#include using namespace std; class Queue { public: // Initialize front and rear int rear, front; // Circular Queue int size; int *circular_queue; Queue(int sz) { front = rear = -1; size = sz; circular_queue = new int(sz); } void enQueue(int elem); int deQueue(); void displayQueue(); }; /* Function to create Circular queue */ void Queue::enQueue(int elem) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { cout<<'
Queue is Full'; return; } else if (front == -1) { /* Insert First Element */ front = rear = 0; circular_queue(rear) = elem; } else if (rear == size-1 && front != 0) { rear = 0; circular_queue(rear) = elem; } else { rear++; circular_queue(rear) = elem; } } // Function to delete element from Circular Queue int Queue::deQueue() { if (front == -1) { cout<<'
Queue is Empty'; return -1; } int data = circular_queue(front); circular_queue(front) = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } //display elements of Circular Queue void Queue::displayQueue() { if (front == -1) { cout<<'
Queue is Empty'<= front) { for (int i = front; i <= rear; i++) cout< Ovan visas visningen av cirkulär köoperationer. Först lägger vi till elementen och sedan dequeue eller ta bort två element. Därefter infogar eller förslår vi ytterligare tre element i den cirkulära kön. Vi ser att till skillnad från linjär kö läggs elementen till i slutet av kön.
Länkad implementering
Låt oss diskutera den länkade implementeringen av en cirkulär kö nu. Nedan visas implementeringen av den länkade listan för den cirkulära köen i C ++. Observera att vi använder struct för att representera varje nod. Operationerna är desamma som diskuterats tidigare förutom att vi i det här fallet måste utföra dem med avseende på de länkade listnoderna.
Utgången visar den cirkulära köen efter enqueue-operation, dequeue och även efter den andra enqueue-operationen.
#include using namespace std; struct Node { int data; struct Node* link; }; struct PQueue { struct Node *front, *rear; }; /* this functions performs enqueue operation for circular queue */ void enQueue(PQueue *pq,int elem) { struct Node *temp = new Node; temp->data = elem; if (pq->front == NULL) pq->front = temp; else pq->rear->link = temp; pq->rear = temp; pq->rear->link = pq->front; } // This function performs dequeue operation for Circular Queue int deQueue(PQueue *pq) { if (pq->front == NULL) { cout<<'Queue is empty!!'; return -1; } int elem; // item to be dequeued // item is the last node to be deleted if (pq->front == pq->rear) { elem = pq->front->data; free(pq->front); pq->front = NULL; pq->rear = NULL; } else //more than one nodes { struct Node *temp = pq->front; elem = temp->data; pq->front = pq->front->link; pq->rear->link= pq->front; free(temp); } return elem ; } //display elements of Circular Queue void displayQueue(struct PQueue *pq) { struct Node *temp = pq->front; while (temp->link != pq->front) { cout<data<<' '; temp = temp->link; } cout<data; } //main program int main() { // Create a circular queue and initialize front and rear PQueue *pq = new PQueue; pq->front = pq->rear = NULL; // Insert/enqueue elements in Circular Queue enQueue(pq, 1); enQueue(pq, 3); enQueue(pq, 5); cout<<'
Circular Queue elements after enqueue operation: '; // Display elements in Circular Queue displayQueue(pq); // Delete/dequeue elements from Circular Queue cout<<'
Dequeued Item: '< Produktion:
Nästa implementering är ett Java-program för att visa cirkulär kö med den länkade listan.
import java.util.* ; class Main { // Node structure static class Node { int data; Node link; } static class CQueue { Node front, rear; } // Enqueue operation for circular queue static void enQueue(CQueue cq, int value) { Node temp = new Node(); temp .data = value; if (cq .front == null) cq .front = temp; else cq .rear .link = temp; cq .rear = temp; cq .rear .link = cq .front; } // Dequeue operation for Circular Queue static int deQueue(CQueue cq) { if (cq .front == null) { System.out.printf ('Queue is empty!!'); return Integer.MIN_VALUE; } int value; // Value to be dequeued // the last node to be deleted if (cq.front == cq.rear) { value = cq.front.data; cq.front = null; cq.rear = null; } else { // There are more than one nodes Node temp = cq.front; value = temp.data; cq.front = cq.front.link; cq.rear.link= cq.front; } return value ; } // display the elements of Circular Queue static void displayQueue( CQueue cq) { Node temp = cq.front; while (temp.link != cq.front) { System.out.printf('%d ', temp.data); temp = temp.link; } System.out.printf('%d', temp.data); } /* main program */ public static void main(String args()) { // Create a queue and initialize front and rear CQueue cq = new CQueue(); cq.front = cq.rear = null; // Insert/enqueue elements in Circular Queue enQueue(cq, 2); enQueue(cq, 4); enQueue(cq, 6); System.out.print('
Circular Queue elements after Enqueue Operation:'); // Display elements in Circular Queue displayQueue(cq); // Delete/dequeue elements from Circular Queue System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.print('
Circular Queue elements after Dequeue Operation:'); displayQueue(cq); enQueue(cq, 8); enQueue(cq, 10); System.out.print('
Circular Queue elements after second Enqueue Operation:'); displayQueue(cq); } } Produktion:
Resultatet från ovanstående program liknar det tidigare programmet.
Applikationer
Låt oss diskutera några av applikationerna i den cirkulära köen.
- CPU-schemaläggning: Operativsystemsprocess som kräver att någon händelse inträffar eller att andra processer ska slutföras för körning hålls ofta i en cirkulär kö så att de körs efter varandra när alla villkor är uppfyllda eller när alla händelser inträffar.
- Minneshantering: Användning av vanliga köer slösar bort minnesutrymme som redan nämnts i vår diskussion ovan. Att använda en cirkulär kö för minneshantering är fördelaktig för optimal minnesanvändning.
- Datorstyrd trafiksignalsystem: Datoriserade trafiksignaler läggs ofta till i en cirkulär kö så att de upprepar sig efter det angivna tidsintervallet har gått.
Slutsats
Cirkulära köer fixar den största nackdelen med en normal kö där vi inte kan infoga element när den bakre pekaren är i slutet av kön även när vi tar bort elementen och utrymmet töms. I en cirkulär kö är element ordnade på ett cirkulärt sätt så att utrymme inte slösas bort alls.
Vi har också sett de stora operationerna i den cirkulära köen. Cirkulära köer är mest användbara för schemaläggningsändamål och applikationer som trafiksignalsystem där signalerna lyser i varv.
förklara en strängmatris i Java
I vår nästa handledning lär vi oss om de dubbla köerna som helt enkelt kallas 'deque'.
=> Besök här för att lära dig C ++ från Scratch
Rekommenderad läsning
- Kodatastruktur i C ++ med illustration
- Prioriterad ködatastruktur i C ++ med illustration
- Cirkulär länkad datastruktur i C ++ med illustration
- Data Mart Tutorial - Typer, exempel och implementering av Data Mart
- Stack datastruktur i C ++ med illustration
- Exempel på datautvinning: De vanligaste tillämpningarna av datautvinning 2021
- Datastruktur för binärt träd i C ++
- Prioritetskö i STL
