Menü

Warteschlangendatenstruktur in C ++ mit Illustration

  • Haupt
  • Andere
  • Warteschlangendatenstruktur in C ++ mit Illustration

queue data structure c with illustration

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Eine kurze Einführung in die Warteschlange in C ++ mit Illustration.

Die Warteschlange ist eine grundlegende Datenstruktur wie ein Stapel. Im Gegensatz zu Stacks, die den LIFO-Ansatz verwenden, verwendet die Warteschlange den FIFO-Ansatz (First In, First Out). Bei diesem Ansatz ist das erste Element, das der Warteschlange hinzugefügt wird, das erste Element, das aus der Warteschlange entfernt wird. Genau wie Stack ist auch die Warteschlange eine lineare Datenstruktur.

freie software zum rippen von dvd auf mp4

In einer realen Analogie können wir uns eine Buswarteschlange vorstellen, in der die Passagiere in einer Warteschlange oder einer Linie auf den Bus warten. Der erste Passagier in der Linie steigt zuerst in den Bus ein, da dieser Passagier derjenige ist, der zuerst gekommen ist.

=> Lesen Sie hier die beliebte C ++ - Schulungsserie.

Warteschlange in C ++

Was du lernen wirst:

Warteschlange in C ++

In Bezug auf die Software kann die Warteschlange als Satz oder Sammlung von Elementen angezeigt werden, wie unten gezeigt. Die Elemente sind linear angeordnet.

Warteschlange

Wir haben zwei Enden, d. H. 'Vorne' und 'Rückseite' der Warteschlange. Wenn die Warteschlange leer ist, werden beide Zeiger auf -1 gesetzt.

Der hintere Zeiger ist die Stelle, an der die Elemente in die Warteschlange eingefügt werden. Das Hinzufügen / Einfügen von Elementen in die Warteschlange wird als 'Enqueue' bezeichnet.

Der 'Front' -Endzeiger ist die Stelle, an der die Elemente aus der Warteschlange entfernt werden. Der Vorgang zum Entfernen / Löschen von Elementen aus der Warteschlange wird als 'Warteschlange' bezeichnet.

Wenn der hintere Zeigerwert Größe 1 ist, sagen wir, dass die Warteschlange voll ist. Wenn die Front null ist, ist die Warteschlange leer.

Grundoperationen

Die Warteschlangendatenstruktur enthält die folgenden Operationen:

  • EnQueue: Fügt der Warteschlange ein Element hinzu. Das Hinzufügen eines Elements zur Warteschlange erfolgt immer am Ende der Warteschlange.
  • DeQueue: Entfernt ein Element aus der Warteschlange. Ein Element wird immer von der Vorderseite der Warteschlange entfernt oder aus der Warteschlange entfernt.
  • ist leer: Überprüft, ob die Warteschlange leer ist.
  • ist voll: Überprüft, ob die Warteschlange voll ist.
  • spähen: Ruft ein Element an der Vorderseite der Warteschlange ab, ohne es zu entfernen.

Enqueue

In diesem Prozess werden die folgenden Schritte ausgeführt:

  • Überprüfen Sie, ob die Warteschlange voll ist.
  • Wenn voll, einen Überlauffehler erzeugen und beenden.
  • Andernfalls erhöhen Sie 'hinten'.
  • Fügen Sie der Position, auf die 'hinten' zeigt, ein Element hinzu.
  • Erfolg zurückgeben.

Dequeue

Der Warteschlangenvorgang besteht aus den folgenden Schritten:

  • Überprüfen Sie, ob die Warteschlange leer ist.
  • Wenn leer, wird ein Unterlauffehler angezeigt und beendet.
  • Andernfalls wird das Zugriffselement durch 'vorne' gekennzeichnet.
  • Erhöhen Sie die Front, um auf die nächsten zugänglichen Daten zu verweisen.
  • Erfolg zurückgeben.

Als nächstes sehen wir eine detaillierte Darstellung der Einfüge- und Löschvorgänge in der Warteschlange.

Illustration

Abbildung des Einfügens und Löschens in die Warteschlange

Dies ist eine leere Warteschlange und daher haben wir hinten und leer auf -1 gesetzt.

Als nächstes fügen wir 1 zur Warteschlange hinzu und als Ergebnis bewegt sich der hintere Zeiger um eine Stelle vorwärts.

EnQueue-Operation

In der nächsten Abbildung fügen wir Element 2 zur Warteschlange hinzu, indem wir den hinteren Zeiger um ein weiteres Inkrement nach vorne bewegen.

Fügen Sie der Warteschlange Element 2 hinzu

In der folgenden Abbildung fügen wir Element 3 hinzu und bewegen den hinteren Zeiger um 1.

Element 3 hinzufügen

Zu diesem Zeitpunkt hat der hintere Zeiger den Wert 2, während der vordere Zeiger auf 0 stehtthStandort.

Als nächstes löschen wir das Element, auf das der vordere Zeiger zeigt. Da der vordere Zeiger auf 0 steht, ist das gelöschte Element 1.

DeQueue-Operation

Somit ist das erste in die Warteschlange eingegebene Element, d. H. 1, zufällig das erste Element, das aus der Warteschlange entfernt wurde. Infolgedessen wird nach der ersten Warteschlange der vordere Zeiger jetzt vor die nächste Position bewegt, die 1 ist.

Array-Implementierung für Warteschlange

Lassen Sie uns die Warteschlangendatenstruktur mit C ++ implementieren.

#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; }

Ausgabe:

Warteschlange ist leer !!
Warteschlange erstellt:
10 20 30 40 50
Warteschlange ist voll !!
Front = 0
Warteschlangenelemente: 10 20 30 40 50
Hinten = 4

Gelöscht => 10 aus myqueue
Vorderseite = 1
Warteschlangenelemente: 20 30 40 50
Hinten = 4

Die obige Implementierung zeigt die als Array dargestellte Warteschlange. Wir geben die max_size für das Array an. Wir definieren auch die Enqueue- und Dequeue-Operationen sowie die isFull- und isEmpty-Operationen.

Im Folgenden wird die Java-Implementierung der Warteschlangendatenstruktur angegeben.

// 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()); } }

Ausgabe:

Warteschlange erstellt als:
10 20 30 40
Element 10 aus der Warteschlange entfernt

Frontartikel ist 20
Hinterer Artikel ist 40

Die obige Implementierung ähnelt der C ++ - Implementierung.

Als nächstes implementieren wir die Warteschlange in C ++ mithilfe einer verknüpften Liste.

Implementierung einer verknüpften Liste für die Warteschlange:

#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 : '

Ausgabe:

Warteschlange erstellt:
10 20 30 40 50
Aus der Warteschlange gelöschtes Element ist: 10
Warteschlange nach einem Löschvorgang:
20 30 40 50

bester kostenloser E-Mail-Tracker für Google Mail

Stack Vs. Warteschlange

Stapel und Warteschlangen sind sekundäre Datenstrukturen, in denen Daten gespeichert werden können. Sie können mithilfe der primären Datenstrukturen wie Arrays und verknüpften Listen programmiert werden. Nachdem Sie beide Datenstrukturen ausführlich besprochen haben, ist es an der Zeit, die Hauptunterschiede zwischen diesen beiden Datenstrukturen zu erörtern.

StapelWarteschlangen
Verwendet den LIFO-Ansatz (Last in, First out).Verwendet den FIFO-Ansatz (First In, First Out).
Elemente werden nur an einem Ende hinzugefügt oder gelöscht, das als 'Oben' des Stapels bezeichnet wird.Elemente werden am hinteren Ende der Warteschlange hinzugefügt und am vorderen Ende der Warteschlange entfernt.
Die Grundoperationen für den Stapel sind 'Push' und 'Pop'.Die grundlegenden Operationen für eine Warteschlange sind 'Enqueue' und 'Dequeue'.
Wir können alle Operationen auf dem Stapel ausführen, indem wir nur einen Zeiger beibehalten, um auf die Oberseite des Stapels zuzugreifen.In Warteschlangen müssen zwei Zeiger verwaltet werden, einer für den Zugriff auf die Vorderseite der Warteschlange und der zweite für den Zugriff auf die Rückseite der Warteschlange.
Der Stapel wird hauptsächlich zur Lösung rekursiver Probleme verwendet.Warteschlangen werden verwendet, um Probleme im Zusammenhang mit der bestellten Verarbeitung zu lösen.

Anwendungen der Warteschlange

Lassen Sie uns die verschiedenen Anwendungen der Warteschlangendatenstruktur unten diskutieren.

  • Die Warteschlangendatenstruktur wird in verschiedenen CPU- und Festplattenplanungen verwendet. Hier haben wir mehrere Aufgaben, die gleichzeitig CPU oder Festplatte erfordern. Die CPU- oder Festplattenzeit wird für jede Aufgabe mithilfe einer Warteschlange geplant.
  • Die Warteschlange kann auch zum Druckspoolen verwendet werden, wobei die Anzahl der Druckaufträge in eine Warteschlange gestellt wird.
  • Die Behandlung von Interrupts in Echtzeitsystemen erfolgt mithilfe einer Warteschlangendatenstruktur. Die Interrupts werden in der Reihenfolge ihres Eintreffens behandelt.
  • Bei der Breitensuche, bei der die benachbarten Knoten eines Baums durchlaufen werden, bevor zur nächsten Ebene übergegangen wird, wird eine Warteschlange für die Implementierung verwendet.
  • Call-Center-Telefonsysteme verwenden Warteschlangen, um die Anrufe zu halten, bis sie von den Servicemitarbeitern beantwortet werden.

Im Allgemeinen können wir sagen, dass die Warteschlangendatenstruktur immer dann verwendet wird, wenn die Ressourcen oder Elemente in der Reihenfolge gewartet werden müssen, in der sie ankommen, d. H. First in, First Out.

Fazit

Die Warteschlange ist eine FIFO-Datenstruktur (First In, First Out), die hauptsächlich in Ressourcen verwendet wird, in denen eine Planung erforderlich ist. Es hat zwei Zeiger hinten und vorne an zwei Enden und diese werden verwendet, um ein Element einzufügen und ein Element in die / aus der Warteschlange zu entfernen.

In unserem nächsten Tutorial lernen wir einige der Erweiterungen der Warteschlange wie Prioritätswarteschlange und zirkuläre Warteschlange kennen.

=> Hier finden Sie Informationen zur vollständigen Liste der C ++ - Tutorials.

Literatur-Empfehlungen

^