Meny

Kodatastruktur i C ++ med illustration

queue data structure c with illustration

Prova Vårt Instrument För Att Eliminera Problem

En kort introduktion till kö i C ++ med illustration.

Kön är en grundläggande datastruktur precis som en stack. Till skillnad från stack som använder LIFO-metoden använder kön FIFO-metoden (först in, först ut). Med detta tillvägagångssätt är det första objektet som läggs till i kön det första objektet som tas bort från kön. Precis som Stack är kön också en linjär datastruktur.

hur man öppnar en apk-fil på Android

I en verklig analogi kan vi föreställa oss en busskö där passagerarna väntar på bussen i en kö eller en linje. Den första passageraren i linjen går in i bussen först eftersom den passageraren råkar vara den som hade kommit först.

=> Läs igenom den populära C ++ träningsserien här.

Kö i C ++

Vad du kommer att lära dig:

Kö i C ++

När det gäller programvara kan kön ses som en uppsättning eller samling av element som visas nedan. Elementen är ordnade linjärt.

kö

Vi har två ändar, dvs 'främre' och 'bakre' kön. När kön är tom är båda pekarna inställda på -1.

Den 'bakre' ändpekaren är den plats från vilken elementen sätts in i kön. Funktionen för att lägga till / infoga element i kön kallas 'enqueue'.

Den 'främre' ändpekaren är den plats från vilken elementen tas bort från kön. Åtgärden för att ta bort / ta bort element från kön kallas 'dequeue'.

När det bakre pekervärdet är storlek 1, säger vi att kön är full. När fronten är noll är kön tom.

Grundläggande funktioner

Kodatastrukturen innehåller följande operationer:

  • EnQueue: Lägger till ett objekt i kön. Att lägga till ett objekt i kön görs alltid längst bak i kön.
  • DeQueue: Tar bort ett objekt från kön. Ett objekt tas alltid bort eller köas från köns framsida.
  • är tom: Kontrollerar om kön är tom.
  • är full: Kontrollerar om kön är full.
  • titt: Får ett element framför kön utan att ta bort det.

Enqueue

I denna process utförs följande steg:

  • Kontrollera om kön är full.
  • Om det är fullt, skapa överflödsfel och avsluta.
  • Annars ökas 'bak'.
  • Lägg till ett element till den plats som pekas av 'bak'.
  • Återvänd framgång.

Dequeue

Dequeue-operation består av följande steg:

  • Kontrollera om kön är tom.
  • Om det är tomt, visa ett underflödesfel och avsluta.
  • Annars påpekas åtkomstelementet med 'front'.
  • Öka 'fronten' för att peka på nästa tillgängliga data.
  • Återvänd framgång.

Därefter ser vi en detaljerad illustration av insättnings- och borttagningsoperationer i kö.

Illustration

illustration av infogning och radering i kö

Detta är en tom kö och därmed har vi bak och tom satt till -1.

Därefter lägger vi till 1 i kön och som ett resultat går den bakre pekaren framåt med en plats.

EnQueue-funktion

I nästa figur lägger vi till element 2 i kön genom att flytta den bakre pekaren framåt med ytterligare ett steg.

lägg till element 2 i kön

I följande bild lägger vi till element 3 och flyttar den bakre pekaren med 1.

lägg till element 3

Vid den här tiden har den bakre pekaren värde 2 medan den främre pekaren är vid 0thplats.

Därefter tar vi bort elementet som pekas av den främre pekaren. Eftersom den främre pekaren är på 0 är elementet som raderas 1.

DeQueue-drift

Således råkar det första elementet som matas in i kön, dvs. 1, vara det första elementet som tas bort från kön. Som ett resultat kommer den främre pekaren att flyttas framåt till nästa position som är 1 efter den första dequeue.

Array Implementation For Queue

Låt oss implementera ködatastrukturen med 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ön är tom !!
Kö skapad:
10 20 30 40 50
Kön är full !!
Fram = 0
Köelement: 10 20 30 40 50
Bakre = 4

Borttagen => 10 från myqueue
Fram = 1
Köelement: 20 30 40 50
Bakre = 4

Ovanstående implementering visar kön representerad som en matris. Vi anger max_size för arrayen. Vi definierar också enqueue- och dequeue-operationerna samt isFull- och isEmpty-operationerna.

Nedan följer 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()); } }

Produktion:

Kö skapad som:
10 20 30 40
Element 10 avskaffat från kö

Främre artikeln är 20
Bakre artikeln är 40

Ovanstående implementering liknar C ++ implementeringen.

Låt oss sedan implementera kön i C ++ med hjälp av en länkad lista.

Länkad implementering för 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ö skapad:
10 20 30 40 50
Element raderat från kön är: 10
Kö efter en radering:
20 30 40 50

för att generera ett slumpmässigt tal kan du använda funktionen rand i rubrikfilen

Stack Vs. Kö

Staplar och köer är sekundära datastrukturer som kan användas för att lagra data. De kan programmeras med de primära datastrukturerna som arrays och länkade listor. Efter att ha diskuterat båda datastrukturerna i detalj är det dags att diskutera de viktigaste skillnaderna mellan dessa två datastrukturer.

TravarKöer
Använder LIFO (Last in, First out) -strategi.Använder FIFO (First in, First out) -strategi.
Objekt läggs till eller raderas från endast en ände som kallas ”Topp” i stacken.Objekt läggs till från 'bakre' ände av kön och tas bort från 'framsidan' av kön.
De grundläggande funktionerna för stacken är 'push' och 'Pop'.De grundläggande åtgärderna för en kö är 'enqueue' och 'dequeue'.
Vi kan utföra alla operationer på stacken genom att bara hålla en pekare för att komma åt toppen av stacken.I köer behöver vi behålla två pekare, en för att komma åt kön och den andra för att komma åt baksidan av kön.
Stapeln används mest för att lösa rekursiva problem.Köer används för att lösa problem relaterade till beställd bearbetning.

Applications Of Queue

Låt oss diskutera de olika tillämpningarna av ködatastrukturen nedan.

  • Kodatastrukturen används vid olika schemaläggningar av CPU och disk. Här har vi flera uppgifter som kräver CPU eller disk samtidigt. CPU- eller disktiden är schemalagd för varje uppgift med hjälp av en kö.
  • Kön kan också användas för utskriftsspolning där antalet utskriftsjobb placeras i en kö.
  • Hantering av avbrott i realtidssystem görs med hjälp av en ködatastruktur. Avbrotten hanteras i den ordning de anländer.
  • Bredd-först-sökning där närliggande noder i ett träd passeras innan de går vidare till nästa nivå använder en kö för implementering.
  • Telefonsystem för callcenter använder köer för att hålla samtalen tills de besvaras av servicerepresentanterna.

Generellt kan vi säga att ködatastrukturen används när vi kräver att resurserna eller artiklarna ska servas i den ordning de anländer, dvs. första in, först ut.

Slutsats

Kön är en FIFO (First In, First Out) datastruktur som oftast används i resurser där schemaläggning krävs. Den har två pekare bak och fram i två ändar och dessa används för att infoga ett element och ta bort ett element till / från kön.

I vår nästa handledning lär vi oss om några av tilläggen i kön som prioritetskö och cirkulär kö.

=> Se här för att utforska listan med fullständiga C ++ -studier.

Rekommenderad läsning

^