c circular queue data structure
Denne opplæringen om C ++ sirkulær kødatastruktur forklarer hva som er sirkulær kø, hva er de grunnleggende operasjonene sammen med implementering og applikasjoner:
En sirkulær kø er en utvidelse av grunnkøen som vi har diskutert tidligere. Det er også kjent som “Ringbuffer”.
Hva er sirkulær kø i C ++?
En sirkulær kø er en lineær datastruktur som brukes til å lagre dataelementer. Den utfører operasjoner ved å følge FIFO (First In, First Out) -tilnærmingen, og den siste posisjonen i køen er koblet tilbake til den første posisjonen for å danne en sirkel.
=> Se etter hele C ++ treningsserien her
Hva du vil lære:
Sirkulær kø i C ++
Følgende diagram viser en sirkulær kø.
Ovenstående bilde viser en sirkulær datastruktur av størrelse 10. De seks første elementene er allerede i køen, og vi ser at den første posisjonen og den siste posisjonen er sammenføyd. På grunn av denne ordningen går ikke plass bortkastet, ettersom det skjer i en lineær kø.
hvordan man skriver en prøvesak
I en lineær kø etter at køen er full, sletter vi elementene fra en annen ende, og statusen til køen vises fremdeles som full, og vi kan ikke sette inn flere elementer.
I den sirkulære køen, når køen er full, og når vi fjerner elementer fra fronten siden siste og første posisjon er koblet til, kan vi sette inn elementene bak som ble forlatt ved å slette elementet.
I neste avsnitt vil vi lære om de grunnleggende operasjonene til den sirkulære køen.
Grunnleggende operasjoner
Noen av de grunnleggende operasjonene i den sirkulære køen er som følger:
Front: Returnerer frontposisjon i sirkulær kø.
Bak: Returnerer bakre posisjon i sirkulær kø.
Enqueue: Enqueue (verdi) brukes til å sette inn et element i den sirkulære køen. Elementet settes alltid inn i bakenden av køen.
Vi følger trinnene nedenfor for å sette inn et nytt element i den sirkulære køen.
#1) Sjekk om den sirkulære køen er full: test ((bak == SIZE-1 && front == 0) || (bak == front-1)), der ‘SIZE’ er størrelsen på den sirkulære køen.
#to) Hvis den sirkulære køen er full, vises en melding som 'Køen er full'. Hvis køen ikke er full, sjekk om (bakre == STØRRELSE - 1 && foran! = 0). Hvis det er sant, så sett bak = 0 og sett inn elementet.
Dequeue: Dequeue-funksjonen brukes til å slette et element fra køen. I den sirkulære køen blir elementet alltid slettet fra frontenden. Nedenfor er sekvensen for dequeue-drift i en sirkulær kø.
Fremgangsmåte:
#1) Sjekk om den sirkulære køen er tom: sjekk om (front == - 1).
for å øke sikkerheten i selskapets interne nettverk
#to) Hvis den er tom, vises meldingen 'Køen er tom'. Hvis køen ikke er tom, utfør trinn 3.
# 3) Sjekk om (foran == bak). Hvis det er sant, så sett front = bak = -1 ellers sjekk om (foran == størrelse-1), hvis det er sant, sett front = 0 og returner elementet.
Illustrasjon
I denne delen vil vi gå gjennom en detaljert illustrasjon av å legge til / fjerne elementer i den sirkulære køen.
Vurder følgende sirkulære kø med 5 elementer som vist nedenfor:
Deretter setter vi inn element 1 i køen.
Deretter setter vi inn et element med verdi 3.
Når vi setter inn elementene for å lage en kø full, vil representasjonen være som vist nedenfor.
Nå sletter vi de to elementene, dvs. element 1 og element 3 fra køen som vist nedenfor.
Deretter setter vi inn eller innkasser element 11 i den sirkulære køen som vist nedenfor.
La oss igjen sette inn element 13 i den sirkulære køen. Køen vil se ut som vist nedenfor.
Vi ser at vi i den sirkulære køen flytter eller setter inn elementer i en sirkel. Derfor kan vi konsumere hele køen til den blir full.
Gjennomføring
La oss implementere den sirkulære køen ved hjelp av 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< Ovenfor vises utdataene fra sirkulære køoperasjoner. Først legger vi til elementene og deretter dequeue eller fjerner to elementer. Deretter setter vi inn eller legger inn tre elementer til i den sirkulære køen. Vi ser at i motsetning til lineær kø legges elementene til på slutten av køen.
Koblet listeimplementering
La oss diskutere implementeringen av den koblede listen til en sirkulær kø nå. Nedenfor er implementeringen av den koblede listen for sirkulær kø i C ++. Merk at vi bruker struktur for å representere hver node. Operasjonene er de samme som diskutert før, bortsett fra at i dette tilfellet må vi utføre dem med hensyn til de koblede listenodene.
Utgangen viser den sirkulære køen etter enqueue-drift, dequeue og også etter den andre enqueue-operasjonen.
#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: '< Produksjon:
Neste implementering er et Java-program for å demonstrere sirkulær kø ved hjelp av den koblede listen.
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); } } Produksjon:
Utgangen fra det ovennevnte programmet er lik det forrige programmet.
applikasjoner
La oss diskutere noen av applikasjonene i den sirkulære køen.
- CPU-planlegging: Operativsystemprosess som krever at noen hendelser skal skje eller at andre prosesser skal fullføres for kjøring, opprettholdes ofte i en sirkulær kø slik at de utføres etter hverandre når alle vilkårene er oppfylt eller når alle hendelser inntreffer.
- Minnehåndtering: Bruk av vanlige køer kaster bort minneplass som allerede nevnt i diskusjonen ovenfor. Å bruke en sirkulær kø for minnestyring er gunstig for optimal minnebruk.
- Datamaskinstyrt trafikksignalsystem: Datastyrte trafikksignaler blir ofte lagt til i en sirkulær kø, slik at de gjentar seg etter at det angitte tidsintervallet har gått.
Konklusjon
Sirkulære køer løser den største ulempen med en normal kø der vi ikke kan sette inn elementer når den bakre pekeren er på slutten av køen, selv når vi sletter elementene og plassen tømmes. I en sirkulær kø er elementer ordnet på en sirkulær måte, slik at det ikke blir kastet bort plass i det hele tatt.
Vi har også sett de viktigste operasjonene i den sirkulære køen. Sirkulære køer er stort sett nyttige for planleggingsformål og applikasjoner som trafikksignalsystemer der signalene lyser i svinger.
char til int konvertering c ++
I vår neste opplæring vil vi lære om køene med dobbelt ende som bare kalles 'deque'.
=> Besøk her for å lære C ++ fra grunnen
Anbefalt lesing
- Kødatastruktur i C ++ med illustrasjon
- Prioritert kødatastruktur i C ++ med illustrasjon
- Sirkulær koblet liste Datastruktur i C ++ med illustrasjon
- Data Mart Tutorial - Typer, eksempler og implementering av Data Mart
- Stakk datastruktur i C ++ med illustrasjon
- Data Mining Eksempler: De vanligste applikasjonene av Data Mining 2021
- Datastruktur for binært tre i C ++
- Prioritetskø I STL
