Meny

Kødatastruktur i C ++ med illustrasjon

  • Hoved
  • Annen
  • Kødatastruktur i C ++ med illustrasjon

queue data structure c with illustration

Prøv Instrumentet Vårt For Å Eliminere Problemer

En kort introduksjon til kø i C ++ med illustrasjon.

Køen er en grunnleggende datastruktur akkurat som en stabel. I motsetning til stabelen som bruker LIFO-tilnærmingen, bruker kø FIFO-tilnærmingen (først inn, først ut). Med denne tilnærmingen er det første elementet som legges til køen det første elementet som fjernes fra køen. Akkurat som Stack er køen også en lineær datastruktur.

implementering av hash-tabell c ++

I en virkelig analogi kan vi forestille oss en busskø der passasjerene venter på bussen i en kø eller en linje. Den første passasjeren i linjen går inn i bussen først, siden passasjeren tilfeldigvis er den som hadde kommet først.

=> Les gjennom den populære C ++ treningsserien her.

Kø i C ++

Hva du vil lære:

Kø i C ++

I programvarebetingelser kan køen sees på som et sett eller samling av elementer som vist nedenfor. Elementene er ordnet lineært.

kø

Vi har to ender, dvs. 'foran' og 'bak' i køen. Når køen er tom, er begge pekerne satt til -1.

Den 'bakre' endepekeren er stedet der elementene settes inn i køen. Operasjonen med å legge til / sette inn elementer i køen kalles “enqueue”.

'Front' -pekeren er stedet der elementene fjernes fra køen. Operasjonen for å fjerne / slette elementer fra køen kalles “dequeue”.

Når den bakre pekerverdien er størrelse 1, så sier vi at køen er full. Når fronten er null, er køen tom.

Grunnleggende operasjoner

Kødatastrukturen inkluderer følgende operasjoner:

  • EnQueue: Legger til et element i køen. Tillegg av et element i køen gjøres alltid på baksiden av køen.
  • DeQueue: Fjerner et element fra køen. Et element fjernes eller avkjøres alltid fra forsiden av køen.
  • er tom: Sjekker om køen er tom.
  • er full: Sjekker om køen er full.
  • titte: Får et element foran i køen uten å fjerne det.

Enqueue

I denne prosessen utføres følgende trinn:

  • Sjekk om køen er full.
  • Hvis den er full, produser overløpsfeil og avslutt.
  • Ellers øker du 'bak'.
  • Legg til et element på stedet som er pekt av 'bak'.
  • Returner suksess.

Dequeue

Dequeue-operasjonen består av følgende trinn:

  • Sjekk om køen er tom.
  • Hvis den er tom, viser du en feil med understrømmen og avslutt.
  • Ellers er tilgangselementet påpekt av ‘front’.
  • Øk 'fronten' for å peke på de neste tilgjengelige dataene.
  • Returner suksess.

Deretter vil vi se en detaljert illustrasjon av innsettings- og slettingsoperasjoner i kø.

Illustrasjon

illustrasjon av innsetting og sletting i kø

Dette er en tom kø, og dermed har vi bak og tom satt til -1.

Deretter legger vi til 1 i køen, og som et resultat beveger den bakre pekeren seg frem ett sted.

EnQueue-drift

I neste figur legger vi til element 2 i køen ved å flytte den bakre pekeren fremover med et nytt trinn.

legg til element 2 i køen

I den følgende figuren legger vi til element 3 og beveger den bakre pekeren med 1.

legg til element 3

På dette punktet har den bakre pekeren verdi 2 mens den fremre pekeren er på 0thplassering.

Deretter sletter vi elementet pekt av frontpekeren. Siden frontpekeren er på 0, er elementet som slettes 1.

DeQueue-drift

Dermed er det første elementet som er angitt i køen, dvs. 1, tilfeldigvis det første elementet fjernet fra køen. Som et resultat, etter første dequeue, vil frontpekeren nå flyttes fremover til neste plassering som er 1.

Array Implementation For Queue

La oss implementere kødatastrukturen ved hjelp av C ++.

#include #define MAX_SIZE 5 using namespace std; class Queue { private: int myqueue(MAX_SIZE), front, rear; public: Queue(){ front = -1; rear = -1; } boolisFull(){ if(front == 0 && rear == MAX_SIZE - 1){ return true; } return false; } boolisEmpty(){ if(front == -1) return true; else return false; } void enQueue(int value){ if(isFull()){ cout << endl<< 'Queue is full!!'; } else { if(front == -1) front = 0; rear++; myqueue(rear) = value; cout << value << ' '; } } int deQueue(){ int value; if(isEmpty()){ cout << 'Queue is empty!!' <= rear){ //only one element in queue front = -1; rear = -1; } else { front++; } cout << endl < ' << value << ' from myqueue'; return(value); } } /* Function to display elements of Queue */ void displayQueue() { int i; if(isEmpty()) { cout << endl << 'Queue is Empty!!' << endl; } else { cout << endl << 'Front = ' << front; cout << endl << 'Queue elements : '; for(i=front; i<=rear; i++) cout << myqueue(i) << ' '; cout << endl << 'Rear = ' << rear << endl; } } }; int main() { Queue myq; myq.deQueue(); //deQueue cout<<'Queue created:'< queue is full myq.enQueue(60); myq.displayQueue(); //deQueue =>removes 10 myq.deQueue(); //queue after dequeue myq.displayQueue(); return 0; }

Produksjon:

Køen er tom !!
Kø opprettet:
10 20 30 40 50
Køen er full !!
Front = 0
Køelementer: 10 20 30 40 50
Bak = 4

Slettet => 10 fra myqueue
Front = 1
Køelementer: 20 30 40 50
Bak = 4

Ovennevnte implementering viser køen representert som en matrise. Vi spesifiserer maks_størrelse for matrisen. Vi definerer også enqueue- og dequeue-operasjonene, så vel som isFull og isEmpty-operasjonene.

Nedenfor er Java-implementeringen av kødatastrukturen.

// A class representing a queue class Queue { int front, rear, size; int max_size; int myqueue(); public Queue(int max_size) { this.max_size = max_size; front = this.size = 0; rear = max_size - 1; myqueue = new int(this.max_size); } //if size = max_size , queue is full boolean isFull(Queue queue) { return (queue.size == queue.max_size); } // size = 0, queue is empty boolean isEmpty(Queue queue) { return (queue.size == 0); } // enqueue - add an element to the queue void enqueue( int item) { if (isFull(this)) return; this.rear = (this.rear + 1)%this.max_size; this.myqueue(this.rear) = item; this.size = this.size + 1; System.out.print(item + ' ' ); } // dequeue - remove an elment from the queue int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.myqueue(this.front); this.front = (this.front + 1)%this.max_size; this.size = this.size - 1; return item; } // move to front of the queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.front); } // move to the rear of the queue int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.rear); } } // main class class Main { public static void main(String() args) { Queue queue = new Queue(1000); System.out.println('Queue created as:'); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println(' Element ' + queue.dequeue() + ' dequeued from queue '); System.out.println('Front item is ' + queue.front()); System.out.println('Rear item is ' + queue.rear()); } }

Produksjon:

Kø opprettet som:
10 20 30 40
Element 10 utskilt fra køen

Fremre vare er 20
Bakre element er 40

Ovenfor er implementeringen lik C ++ implementeringen.

La oss deretter implementere køen i C ++ ved hjelp av en koblet liste.

Koblet listeimplementering for kø:

#include using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert(int val) { if (rear == NULL) { rear = new node; rear->next = NULL; rear->data = val; front = rear; } else { temp=new node; rear->next = temp; temp->data = val; temp->next = NULL; rear = temp; } } void Delete() { temp = front; if (front == NULL) { cout<<'Queue is empty!!'next; cout<<'Element deleted from queue is : '

Produksjon:

Kø opprettet:
10 20 30 40 50
Element slettet fra kø er: 10
Kø etter en sletting:
20 30 40 50

beste gratis video nedlasting for Windows

Stack vs. Kø

Stabler og køer er sekundære datastrukturer som kan brukes til å lagre data. De kan programmeres ved hjelp av primære datastrukturer som matriser og koblede lister. Etter å ha diskutert begge datastrukturene i detalj, er det på tide å diskutere hovedforskjellene mellom disse to datastrukturene.

StablerKøer
Bruker LIFO (Last in, First out) tilnærming.Bruker FIFO (First in, First out) tilnærming.
Elementer blir lagt til eller slettet fra bare den ene enden kalt “Topp” i bunken.Elementer legges til fra 'bakre' ende av køen og fjernes fra 'forsiden' av køen.
De grunnleggende operasjonene for stakken er 'push' og 'Pop'.De grunnleggende operasjonene for en kø er 'enqueue' og 'dequeue'.
Vi kan utføre alle operasjoner på bunken ved å holde bare én peker for å få tilgang til toppen av bunken.I køer må vi opprettholde to pekere, en for å få tilgang til forsiden av køen og den andre for å få tilgang til baksiden av køen.
Stakken brukes mest til å løse rekursive problemer.Kø brukes til å løse problemer relatert til bestilt behandling.

Applications Of Queue

La oss diskutere de forskjellige applikasjonene i kødatastrukturen nedenfor.

  • Kø-datastrukturen brukes i forskjellige CPU- og diskplanlegginger. Her har vi flere oppgaver som krever CPU eller disk samtidig. CPU- eller disktiden er planlagt for hver oppgave ved hjelp av en kø.
  • Køen kan også brukes til utskriftsspoling hvor antall utskriftsjobber plasseres i en kø.
  • Håndtering av avbrudd i sanntidssystemer gjøres ved å bruke en kø-datastruktur. Avbruddene håndteres i den rekkefølgen de ankommer.
  • Bredde-første-søk der nabolandene til et tre krysses før de går videre til neste nivå, bruker en kø for implementering.
  • Telefonsystemer for call center bruker køer for å holde samtalene til de blir besvart av servicerepresentantene.

Generelt kan vi si at kødatastrukturen brukes når vi trenger at ressursene eller elementene skal betjenes i den rekkefølgen de ankommer, dvs. først inn, først ut.

Konklusjon

Køen er en FIFO (First In, First Out) datastruktur som mest brukes i ressurser der planlegging er nødvendig. Den har to pekere bak og foran i to ender, og disse brukes til å sette inn et element og fjerne et element til / fra køen.

I vår neste opplæring vil vi lære om noen av utvidelsene i køen som prioritetskø og sirkulær kø.

=> Se her for å utforske hele C ++ opplæringslisten.

Anbefalt lesing

^