c circular queue data structure
Denne vejledning om C ++ cirkulær kø Datastruktur forklarer, hvad der er cirkulær kø, hvad er de grundlæggende operationer sammen med implementering og applikationer:
En cirkulær kø er en udvidelse af den grundlæggende kø, som vi har diskuteret tidligere. Det er også kendt som “Ringbuffer”.
Hvad er cirkulær kø i C ++?
En cirkulær kø er en lineær datastruktur, der bruges til at gemme dataelementer. Den udfører operationer ved at følge FIFO-tilgangen (First In, First Out), og den sidste position i køen forbindes tilbage til den første position for at danne en cirkel.
=> Se efter hele C ++ træningsserien her
Hvad du vil lære:
Cirkulær kø i C ++
Følgende diagram viser en cirkulær kø.
Ovenstående billede viser en cirkulær datastruktur af størrelse 10. De første seks elementer er allerede i køen, og vi ser, at den første position og den sidste position er forbundet. På grund af dette arrangement spildes ikke plads, da det sker i en lineær kø.
c ++ interviewspørgsmål og svar til erfarne
I en lineær kø, når køen er fuld, sletter vi elementerne fra en anden ende, og status for køen vises stadig som fuld, og vi kan ikke indsætte flere elementer.
I den cirkulære kø, når køen er fuld, og når vi fjerner elementer fra fronten, siden sidste og første position er forbundet, kan vi indsætte elementerne bagpå, som blev fjernet ved at slette elementet.
I det næste afsnit lærer vi om de grundlæggende operationer i den cirkulære kø.
Grundlæggende funktioner
Nogle af de grundlæggende operationer i den cirkulære kø er som følger:
Foran: Returnerer frontpositionen i den cirkulære kø.
Bag: Returnerer den bageste position i den cirkulære kø.
Enqueue: Enqueue (værdi) bruges til at indsætte et element i den cirkulære kø. Elementet indsættes altid i den bageste ende af køen.
Vi følger følgende rækkefølge for at indsætte et nyt element i den cirkulære kø.
# 1) Kontroller, om den cirkulære kø er fuld: test ((bageste == STØRRELSE-1 && front == 0) || (bageste == front-1)), hvor 'STØRRELSE' er størrelsen på den cirkulære kø.
#to) Hvis den cirkulære kø er fuld, vises en meddelelse som 'Kø er fuld'. Hvis køen ikke er fuld, skal du kontrollere, om (bageste == STØRRELSE - 1 && front! = 0). Hvis det er sandt, skal du indstille bageste = 0 og indsætte elementet.
Dequeue: Dequeue-funktionen bruges til at slette et element fra køen. I den cirkulære kø slettes elementet altid fra frontenden. Nedenfor er sekvensen for dequeue-drift i en cirkulær kø.
Trin:
# 1) Kontroller, om den cirkulære kø er tom: Kontroller, om (front == - 1).
hvordan man skriver automatiske testsager
#to) Hvis den er tom, vises meddelelsen 'Kø er tom'. Hvis køen ikke er tom, skal du udføre trin 3.
# 3) Kontroller, om (foran == bageste). Hvis det er sandt, skal du indstille front = bag = -1 ellers kontrollere, om (front == størrelse-1), hvis det er sandt, skal du indstille front = 0 og returnere elementet.
Illustration
I dette afsnit gennemgår vi en detaljeret illustration af tilføjelse / fjernelse af elementer i den cirkulære kø.
Overvej følgende cirkulære kø på 5 elementer som vist nedenfor:
Derefter indsætter vi punkt 1 i køen.
Derefter indsætter vi et element med værdi 3.
Når vi indsætter elementerne for at gøre en kø fuld, vil repræsentationen være som vist nedenfor.
Nu sletter vi de to elementer, dvs. element 1 og element 3 fra køen som vist nedenfor.
Derefter indsætter eller indkapsler vi element 11 i den cirkulære kø som vist nedenfor.
Lad os igen indsætte element 13 i den cirkulære kø. Køen ser ud som vist nedenfor.
Vi ser, at vi i den cirkulære kø flytter eller indsætter elementer i en cirkel. Derfor kan vi forbruge hele pladsen i køen, indtil den bliver fuld.
Implementering
Lad os implementere den cirkulære kø ved hjælp af 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 output fra cirkulære køoperationer. Først tilføjer vi elementerne og fjerner eller fjerner to elementer. Derefter indsætter eller indkapsler vi tre yderligere elementer i den cirkulære kø. Vi ser, at i modsætning til lineær kø tilføjes elementerne i slutningen af køen.
Implementering af sammenkædet liste
Lad os diskutere implementeringen af den linkede liste over en cirkulær kø nu. Nedenfor er den linkede implementering af den cirkulære kø i C ++. Bemærk, at vi bruger struct til at repræsentere hver node. Operationerne er de samme som diskuteret før, bortset fra at vi i dette tilfælde er nødt til at udføre dem med hensyn til de sammenkædede listenoder.
Outputtet viser den cirkulære kø efter enqueue-operation, dequeue og også efter den anden enqueue-operation.
#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æste implementering er et Java-program til at demonstrere cirkulær kø ved hjælp af den linkede liste.
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:
Outputtet fra ovenstående program svarer til det forrige program.
Ansøgninger
Lad os diskutere nogle af applikationerne i den cirkulære kø.
- CPU-planlægning: Operativsystemproces, der kræver, at en begivenhed skal forekomme, eller for at andre processer skal gennemføres til udførelse, opretholdes ofte i en cirkulær kø, så de udføres efter hinanden, når alle betingelser er opfyldt, eller når alle begivenheder opstår.
- Hukommelsesstyring: Brug af almindelige køer spilder hukommelsesplads som allerede nævnt i vores ovenstående diskussion. Brug af en cirkulær kø til hukommelsesstyring er gavnlig for optimal hukommelsesforbrug.
- Computerstyret trafiksignalsystem: Computeriserede trafiksignaler føjes ofte til en cirkulær kø, så de gentager sig selv efter det angivne tidsinterval er udløbet.
Konklusion
Cirkulære køer løser den største ulempe ved en normal kø, hvor vi ikke kan indsætte elementer, når den bageste markør er i slutningen af køen, selv når vi sletter elementerne, og pladsen tømmes. I en cirkulær kø er elementer arrangeret på en cirkulær måde, så plads slet ikke spildes.
Vi har også set de store operationer i den cirkulære kø. Cirkulære køer er for det meste nyttige til planlægningsformål og applikationer som trafiksignalsystemer, hvor signalerne lyser i sving.
hvordan man laver en penetrationstest
I vores næste tutorial lærer vi om køerne med dobbelt ende, der simpelthen kaldes 'deque'.
=> Besøg her for at lære C ++ fra bunden
Anbefalet læsning
- Kø Datastruktur i C ++ med illustration
- Prioriteret kødatastruktur i C ++ med illustration
- Cirkulær sammenkædet liste Datastruktur i C ++ med illustration
- Data Mart Tutorial - Typer, eksempler og implementering af Data Mart
- Stak datastruktur i C ++ med illustration
- Eksempler på data minedrift: De mest almindelige anvendelser af Data Mining 2021
- Datastruktur for binært træ i C ++
- Prioritetskø i STL
