Menu

Kø Datastruktur i C ++ med illustration

queue data structure c with illustration

Prøv Vores Instrument Til At Fjerne Problemer

En kort introduktion til kø i C ++ med illustration.

Køen er en grundlæggende datastruktur ligesom en stak. I modsætning til stakken, der bruger LIFO-tilgangen, bruger køen FIFO-tilgangen (først ind, først ud). Med denne tilgang er det første element, der føjes til køen, det første element, der fjernes fra køen. Ligesom Stack er køen også en lineær datastruktur.

unix kommandoer interviewspørgsmål og svar til erfarne

I en reel analogi kan vi forestille os en buskø, hvor passagererne venter på bussen i en kø eller en linje. Den første passager i linjen går først ind i bussen, da denne passager tilfældigvis er den, der var kommet først.

=> Læs gennem den populære C ++ træningsserie her.

Kø i C ++

Hvad du lærer:

Kø i C ++

I software termer kan køen ses som et sæt eller en samling af elementer som vist nedenfor. Elementerne er arrangeret lineært.

kø

Vi har to ender, dvs. 'for' og 'bag' i køen. Når køen er tom, sættes begge markører til -1.

Den 'bageste' endemarkør er det sted, hvorfra elementerne indsættes i køen. Handlingen med at tilføje / indsætte elementer i køen kaldes “enqueue”.

'Front' -endemarkøren er det sted, hvorfra elementerne fjernes fra køen. Handlingen til at fjerne / slette elementer fra køen kaldes “dequeue”.

Når den bageste markørværdi er størrelse 1, så siger vi, at køen er fuld. Når fronten er nul, er køen tom.

Grundlæggende funktioner

Kødatastrukturen inkluderer følgende operationer:

  • EnQueue: Føjer et element til køen. Tilføjelse af et element i køen sker altid bagest i køen.
  • DeQueue: Fjerner et element fra køen. En vare fjernes eller afkøles altid fra køens forside.
  • er tom: Kontrollerer, om køen er tom.
  • er fuld: Kontrollerer, om køen er fuld.
  • kigge: Får et element forrest i køen uden at fjerne det.

Enqueue

I denne proces udføres følgende trin:

  • Kontroller, om køen er fuld.
  • Hvis den er fuld, skal du producere overløbsfejl og afslutte.
  • Ellers øges 'bageste'.
  • Føj et element til det sted, der er peget med 'bagpå'.
  • Returner succes.

Dequeue

Dequeue-drift består af følgende trin:

  • Kontroller, om køen er tom.
  • Hvis den er tom, skal du vise en understrømsfejl og afslutte.
  • Ellers påpeges adgangselementet med 'front'.
  • Forøg 'fronten' for at pege på de næste tilgængelige data.
  • Returner succes.

Dernæst vil vi se en detaljeret illustration af indsættelses- og sletningsoperationer i kø.

Illustration

illustration af indsættelse og sletning i kø

Dette er en tom kø, og derfor har vi bag og tom sat til -1.

Derefter føjer vi 1 til køen, og som et resultat bevæger den bageste markør sig fremad med en placering.

EnQueue-drift

I den næste figur føjer vi element 2 til køen ved at flytte den bageste markør fremad med endnu et trin.

tilføj element 2 til køen

I den følgende figur tilføjer vi element 3 og flytter den bageste markør med 1.

tilføj element 3

På dette tidspunkt har den bageste markør værdi 2, mens den forreste markør er ved 0thBeliggenhed.

Dernæst sletter vi elementet peget af den forreste markør. Da frontmarkøren er på 0, er elementet, der slettes, 1.

DeQueue-drift

Således er det første element indtastet i køen, dvs. 1 tilfældigvis det første element fjernet fra køen. Som et resultat flyttes den forreste markør nu efter den første dequeue fremad til den næste placering, som er 1.

Array Implementation For Queue

Lad os implementere kødatastrukturen ved hjælp af 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; }

Produktion:

Køen er tom !!
Kø oprettet:
10 20 30 40 50
Køen er fuld !!
Front = 0
Køelementer: 10 20 30 40 50
Bageste = 4

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

Ovenstående implementering viser køen repræsenteret som en matrix. Vi specificerer max_size for arrayet. Vi definerer også enqueue- og dequeue-operationer såvel som isFull og isEmpty-operationer.

Nedenfor er Java-implementeringen af ​​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()); } }

Produktion:

Kø oprettet som:
10 20 30 40
Element 10 udskilt fra køen

Frontgenstand er 20
Bageste genstand er 40

Ovenstående implementering svarer til C ++ implementeringen.

Lad os derefter implementere køen i C ++ ved hjælp af en linket liste.

Implementering af sammenkædet liste til 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 : '

Produktion:

Kø oprettet:
10 20 30 40 50
Element slettet fra kø er: 10
Kø efter en sletning:
20 30 40 50

hvordan man bruger en .torrent-fil

Stack Vs. Kø

Stakke og køer er sekundære datastrukturer, som kan bruges til at gemme data. De kan programmeres ved hjælp af de primære datastrukturer som arrays og sammenkædede lister. Efter at have diskuteret begge datastrukturer i detaljer, er det tid til at diskutere de største forskelle mellem disse to datastrukturer.

StakkeKøer
Bruger LIFO (Last in, First out) tilgang.Bruger FIFO (First in, First out) tilgang.
Elementer tilføjes eller slettes fra kun den ene ende kaldet “Top” af stakken.Elementer tilføjes fra 'bageste' ende af køen og fjernes fra 'front' i køen.
De grundlæggende operationer for stakken er “push” og “Pop”.De grundlæggende operationer for en kø er “enqueue” og “dequeue”.
Vi kan udføre alle operationer på stakken ved kun at opretholde en markør for at få adgang til toppen af ​​stakken.I køer skal vi vedligeholde to markører, en for at få adgang til køens forreste og den anden for at få adgang til den bageste del af køen.
Stakken bruges mest til at løse rekursive problemer.Køer bruges til at løse problemer i forbindelse med bestilt behandling.

Anvendelser i kø

Lad os diskutere de forskellige anvendelser af kødatastrukturen nedenfor.

  • Kø-datastrukturen bruges i forskellige CPU- og diskplanlægninger. Her har vi flere opgaver, der kræver CPU eller disk på samme tid. CPU- eller disktiden er planlagt for hver opgave ved hjælp af en kø.
  • Køen kan også bruges til udskriftsspoling, hvor antallet af udskriftsjob placeres i en kø.
  • Håndtering af afbrydelser i realtidssystemer sker ved hjælp af en kø-datastruktur. Afbrydelserne håndteres i den rækkefølge, de ankommer.
  • Bredde-første søgning, hvor de nærliggende knudepunkter i et træ krydses, inden de går videre til næste niveau, bruger en kø til implementering.
  • Call-center-telefonsystemer bruger køer til at afholde opkaldene, indtil de besvares af servicerepræsentanterne.

Generelt kan vi sige, at kødatastrukturen bruges, når vi kræver, at ressourcerne eller elementerne skal serviceres i den rækkefølge, de ankommer, dvs. først ind, først ud.

Konklusion

Køen er en FIFO (First In, First Out) datastruktur, der mest bruges i ressourcer, hvor der kræves planlægning. Den har to markører bag og foran i to ender, og disse bruges til at indsætte et element og fjerne et element til / fra henholdsvis køen.

I vores næste tutorial lærer vi om nogle af udvidelserne i køen som prioritetskø og cirkulær kø.

=> Se her for at udforske den komplette C ++ tutorials-liste.

Anbefalet læsning

^