Verwenden einer Warteschlange zum Umkehren eines Stapels

Einführung

Warteschlange und Stapel sind beides lineare Datenstrukturen, die zum Speichern von Daten verwendet werden. Der Stack nutzt das LIFO-Prinzip zum Einfügen und Löschen von Elementen. Die Warteschlange nutzt das FIFO-Prinzip. In diesem Tutorial erfahren Sie, wie Sie mithilfe von Warteschlangen einen Stapel umkehren. Umkehren bedeutet, dass das letzte Element des Stapels zum ersten wird und so weiter.

Was ist ein Stapel?

Stacks in Datenstrukturen sind von realen Stacks inspiriert. Es verwendet die Last-In-First-Out-Logik (LIFO), was bedeutet, dass das letzte Element, das auf den Stapel gelangt ist, zuerst entfernt wird. Bei einem Stapel werden Elemente von oben eingefügt und können nur von oben entnommen werden. Der Stapel hat nur einen Endpunkt.

Im wirklichen Leben ist das Stapeln von Zeitungen ein Beispiel für einen Stapel. Die Zeitung, die vom Stapel genommen wird, wird als letztes hineingelegt.

Grundlegende Funktionalität des Stacks

• push() − Es wird ein Stapelelement von oben eingefügt.

  Syntax − stack_name.push(element type)

• pop() − Es werden Elemente von der Oberseite des Stapels entfernt.

  Syntax − stack_name.pop()

• size() − Gibt die Größe des Stapels zurück.

  Syntax − stack_name.size()

• top() − Es gibt einen Verweis auf das oberste Element des Stapels zurück.

  Syntax − stack_name.top()

Was ist eine Warteschlange?

Das Konzept der Warteschlange in der Datenstruktur stammt aus Warteschlangen im wirklichen Leben. In der Warteschlange werden Elemente aus dem Backend eingefügt und aus dem Frontend entfernt. Beide Enden der Warteschlange sind offen und funktionieren nach dem First-In-First-Out-Prinzip (FIFO). Dieses Prinzip bedeutet, dass das zuerst eingefügte Element zuerst aus der Warteschlange entfernt wird.

Grundfunktionen der Warteschlange

• push() − Fügt Elemente in das Backend der Warteschlange ein.

  Syntax − queue_name.push(Datentyp)

• pop() − Entfernt ein Element vom Anfang der Warteschlange.

  Syntax − queue_name.pop()

• front() − Rufen Sie einen Verweis auf das erste Element in der Warteschlange ab.

  Syntax − queue_name.front()

• size() − Gibt die Größe der Warteschlange zurück.

  Syntax − queue_name.size()

Stapel mithilfe der Warteschlange umkehren

Lassen Sie uns zunächst anhand eines Beispiels verstehen, was Stapelinversion ist.

Stack before reversing: [2,5,6,7]
Stack Reversed: [7,6,5,2]

Logik – Wir verwenden einen Stapel mit Elementen und einer leeren Warteschlange. Nehmen Sie Elemente nacheinander aus dem Stapel und fügen Sie sie in die Warteschlange ein, bis alle Elemente eingefügt wurden. Nun wird das Queue-Element entfernt und wieder in den leeren Stack eingefügt. Beenden.

Algorithmus

Schritt 1: Elemente in den Stapel einfügen.

Schritt 2: Holen Sie sich eine leere Warteschlange.

Schritt 3: Schieben Sie die Stapelelemente nacheinander in die leere Warteschlange.

Schritt 4: Jetzt ist der Stapel leer.

Schritt 5: Nehmen Sie Elemente nacheinander aus der Warteschlange und schieben Sie sie auf den Stapel.

Schritt 6: Der Stapel wird umgedreht.

Beispiel

Beispiel unten gezeigt.

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
//function to reverse a queue
void reverse(queue<int> &q) {
   
   //Declaring a stack s
   stack<int> s;
   
   //inserting Queue elements into stack
   while (!q.empty()) {
      s.push(q.front());
      q.pop();
   }
   
   //Again pushing the elements into queue from back
   while (!s.empty()) {
      q.push(s.top());
      s.pop();
   }
}

void printQueue(queue<int> q) {
   
   while(!q.empty()) {
      cout<<q.front()<<" ";
      q.pop();
   }
   cout<<endl;
}

int main() {
   queue<int> q;
   //pushing elements into the Queue
   for(int i=1;i<=5;i++) {
      q.push(i);
   }
   cout<<"Initial Queue is: ";
   printQueue(q);
   
   reverse(q);
   
   cout<<"Reversed Queue is: ";
   printQueue(q);
}

Ausgabe

Initial Queue is: 1 2 3 4 5 
Reversed Queue is: 5 4 3 2 1 

Fazit

Wir können einen Stapel einfach umkehren, indem wir Warteschlangen verwenden. Wir fügen das Stapelelement in die Warteschlange ein und fügen das Warteschlangenelement dann erneut in den Stapel ein. Ich hoffe, dass Sie diesen Ansatz leicht verstehen und umsetzen können.

Das obige ist der detaillierte Inhalt vonVerwenden einer Warteschlange zum Umkehren eines Stapels. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!