Stapel in C ++ STL mit Beispiel

Inhaltsverzeichnis:

Anonim

Was ist std :: stack?

Ein Stapel ist eine Datenstruktur, die auf der LIFO-Technik (Last In First Out) basiert. Mit dem std :: stack können Elemente nur an einem Ende hinzugefügt und entfernt werden.

Die std :: stack-Klasse ist ein Containeradapter. Containerobjekte enthalten Daten eines ähnlichen Datentyps. Sie können einen Stapel aus verschiedenen Sequenzcontainern erstellen. Wenn kein Container bereitgestellt wird, wird standardmäßig das Deque-Contain verwendet. Containeradapter unterstützen keine Iteratoren und können daher nicht zum Bearbeiten von Daten verwendet werden.

In diesem C ++ - Tutorial lernen Sie

  • Was ist std :: stack?
  • Stapelsyntax
  • Mitgliedertypen
  • Operationen im Stapel
  • Stapelimplementierung
  • push () und pop ()
  • leer (), Größe (), oben ()
  • emplace () und swap ()
  • Stapel in STL

Stapelsyntax

Um einen Stapel zu erstellen, müssen wir die -Headerdatei in unseren Code aufnehmen. Wir verwenden dann diese Syntax, um den std :: stack zu definieren:

template  > class stack;
  • Typ - ist der Typ des Elements, das im std :: stack enthalten ist. Es kann sich um einen beliebigen gültigen C ++ - Typ oder sogar um einen benutzerdefinierten Typ handeln.
  • Container - ist der Typ des zugrunde liegenden Containerobjekts.

Mitgliedertypen

Hier sind Stapelelementtypen:

  • value_type- Der erste Vorlagenparameter T. Er bezeichnet die Elementtypen.
  • container_type- Der zweite Vorlagenparameter, Container. Es bezeichnet den zugrunde liegenden Containertyp.
  • size_type- Integrierter Typ ohne Vorzeichen.

Operationen im Stapel

Ein C ++ - Stapel unterstützt die folgenden grundlegenden Operationen:

  • push - Fügt einen Gegenstand hinzu / schiebt ihn in den Stapel.
  • pop - Entfernt / entfernt ein Element vom Stapel.
  • peek - Gibt das oberste Element des Stapels zurück, ohne es zu entfernen.
  • isFull - Überprüft, ob ein Stapel voll ist.
  • isEmpty - Überprüft, ob ein Stapel leer ist.

Stapelimplementierung

Schritt 1) Wir haben zunächst einen leeren Stapel. Die Oberseite eines leeren Stapels wird auf -1 gesetzt.

Schritt 2) Als nächstes haben wir das Element 5 in den Stapel geschoben. Die Oberseite des Stapels zeigt auf das Element 5.

Schritt 3) Als nächstes haben wir das Element 50 in den Stapel geschoben. Die Oberseite des Stapels verschiebt sich und zeigt auf das Element 50.

Schritt 4) Wir haben dann eine Pop-Operation durchgeführt, bei der das oberste Element vom Stapel entfernt wurde. Das Element 50 wird vom Stapel genommen. Die Oberseite des Stapels zeigt jetzt auf das Element 5.

push () und pop ()

Die Funktionen stack :: push () fügen ein neues Element oben im Stapel hinzu. Die Stapelgröße wird nach dem Einfügen um eine 1 erhöht. Die Funktion verwendet diese Syntax:

stack.push(value)

Der Wert ist das Element, das in den Stapel eingefügt werden soll.

Die Funktion stack :: pop () entfernt das oberste Element des Stapels. Dies ist das neueste Element des Stapels. Die Stapelgröße wird nach dem Entfernen um 1 reduziert. Hier ist die Funktionssyntax:

stack.pop()

Die Funktion akzeptiert keine Parameter.

Beispiel 1:

#include #include using namespace std;int main() {stack st;st.push(10);st.push(20);st.push(30);st.push(40);st.pop();st.pop();while (!st.empty()) {cout << ' ' << st.top();st.pop();}}

Ausgabe:

Hier ist ein Screenshot des Codes:

Code Erläuterung:

  1. Fügen Sie die iostream-Headerdatei in unseren Code ein, um ihre Funktionen zu nutzen.
  2. Fügen Sie die Stack-Header-Datei in unseren Code ein, um ihre Funktionen zu nutzen.
  3. Fügen Sie den Standard-Namespace in unseren Code ein, um seine Klassen zu verwenden, ohne ihn aufzurufen.
  4. Rufen Sie die Funktion main () auf. Die Programmlogik sollte innerhalb dieser Funktion hinzugefügt werden.
  5. Erstellen Sie einen Stapel st, um ganzzahlige Werte zu speichern.
  6. Verwenden Sie die Funktion push (), um den Wert 10 in den Stapel einzufügen.
  7. Verwenden Sie die Funktion push (), um den Wert 20 in den Stapel einzufügen.
  8. Verwenden Sie die Funktion push (), um den Wert 30 in den Stapel einzufügen.
  9. Verwenden Sie die push () -Funktion, um den Wert 40 in den Stapel einzufügen.
  10. Verwenden Sie die Funktion pop (), um das oberste Element vom Stapel zu entfernen, d. H. 40. Das oberste Element wird jetzt 30.
  11. Verwenden Sie die Funktion pop (), um das oberste Element vom Stapel zu entfernen, dh 30. Das oberste Element wird jetzt zu 20.
  12. Verwenden Sie eine while-Schleife und die Funktion empty (), um zu überprüfen, ob der Stapel NICHT leer ist. Das ! ist der NOT-Operator.
  13. Drucken des aktuellen Inhalts des Stapels auf der Konsole.
  14. Rufen Sie die Funktion pop () auf dem Stapel auf.
  15. Ende des Körpers der while-Schleife.
  16. Ende des Hauptfunktionskörpers ().

leer (), Größe (), oben ()

Stapel haben eingebaute Funktionen, mit denen Sie mit dem Stapel und seinen Werten herumspielen können. Diese schließen ein:

  • empty () - prüft, ob ein Stapel leer ist oder nicht.
  • size () - Gibt die Größe des Stapels zurück, dh die Anzahl der Elemente in einem Stapel.
  • top () - greift auf das Stapelelement oben zu.

Beispiel 2:

#include #include using namespace std;void createStack(stack  mystack){stack  ms = mystack;while (!ms.empty()){cout << '\t' << ms.top();ms.pop();}cout << '\n';}int main(){stack  st;st.push(32);st.push(21);st.push(39);st.push(89);st.push(25);cout << "The stack st is: ";createStack(st);cout << "\n st.size() : " << st.size();cout << "\n st.top() : " << st.top();cout << "\n st.pop() : ";st.pop();createStack(st);return 0;}

Ausgabe:

Hier ist ein Screenshot des Codes:

Code Erläuterung:

  1. Fügen Sie die iostream-Header-Datei in unseren Code ein, um ihre Funktionen nutzen zu können.
  2. Fügen Sie die Stack-Header-Datei in unseren Code ein, um ihre Funktionen nutzen zu können.
  3. Nehmen Sie den Standard-Namespace in unser Programm auf, um seine Klassen zu verwenden, ohne ihn aufzurufen.
  4. Erstellen Sie die Funktion createStack, mit der wir das Stack-Mystack erstellen können. Der Stapel enthält eine Reihe von Ganzzahlen.
  5. Der Anfang des Hauptteils der Funktion createStack.
  6. Erstellen Sie eine Instanz des Mystack-Datentyps und geben Sie ihm den Namen ms.
  7. Verwenden Sie die while-Schleife und die Funktion empty (), um zu überprüfen, ob der Stapel leer ist.
  8. Der Beginn des Körpers der while-Schleife.
  9. Verwenden Sie die Funktion top (), die oben im Stapel gespeichert ist. Das Zeichen \ t erstellt eine neue Registerkarte.
  10. Verwenden Sie die Funktion pop (), um das Element oben im Stapel zu löschen.
  11. Ende des Körpers der while-Schleife.
  12. Drucken Sie eine leere Zeile auf der Konsole.
  13. Ende des Hauptteils der Funktion createStack.
  14. Rufen Sie die Funktion main () auf. Die Programmlogik sollte im Hauptteil der Funktion main () hinzugefügt werden.
  15. Der Beginn des Funktionskörpers main ().
  16. Erstellen Sie ein Stapelobjekt st.
  17. Verwenden Sie die Funktion push (), um das Element 32 in den Stapel einzufügen.
  18. Verwenden Sie die push () -Funktion, um das Element 21 in den Stapel einzufügen.
  19. Verwenden Sie die Funktion push (), um das Element 39 in den Stapel einzufügen.
  20. Verwenden Sie die Funktion push (), um das Element 89 in den Stapel einzufügen.
  21. Verwenden Sie die push () -Funktion, um das Element 25 in den Stapel einzufügen.
  22. Drucken Sie Text auf der Konsole.
  23. Rufen Sie die Funktion createStack auf, um die obigen Einfügevorgänge in den Stapel auszuführen.
  24. Drucken Sie die Größe des Stapels neben anderem Text auf der Konsole.
  25. Drucken Sie das Element oben auf dem Stapel auf der Konsole.
  26. Drucken Sie Text auf der Konsole.
  27. Löschen Sie das Element oben im Stapel. Anschließend werden die im Stapel verbleibenden Elemente zurückgegeben.
  28. Rufen Sie die Funktion createStack auf, um die oben genannten Vorgänge auszuführen.
  29. Das Programm muss nach erfolgreichem Abschluss einen Wert zurückgeben.
  30. Ende des Funktionskörpers main ().

emplace () und swap ()

Dies sind andere eingebaute Stapelfunktionen:

  • emplace () - Konstrukte fügen dann ein neues Element oben in den Stapel ein.
  • swap () - tauscht Stapelinhalte mit den Inhalten eines anderen Stapels aus.

Beispiel 3:

#include #include #include using namespace std;int main() {stack st1;stack st2;st1.emplace(12);st1.emplace(19);st2.emplace(20);st2.emplace(23);st1.swap(st2);cout << "st1 = ";while (!st1.empty()) {cout << st1.top() << " ";st1.pop();}cout << endl << "st2 = ";while (!st2.empty()) {cout << st2.top() << " ";st2.pop();}}

Ausgabe:

Hier ist ein Screenshot des Codes:

Code Erläuterung:

  1. Fügen Sie die iostream-Headerdatei in unseren Code ein, um ihre Funktionen zu nutzen.
  2. Fügen Sie die Stack-Header-Datei in unseren Code ein, um ihre Funktionen zu nutzen.
  3. Fügen Sie die cstdlib-Headerdatei in unseren Code ein, um ihre Funktionen zu nutzen.
  4. Fügen Sie den Standard-Namespace in unseren Code ein, um seine Klassen zu verwenden, ohne ihn aufzurufen.
  5. Rufen Sie die Funktion main () auf. Die Programmlogik wird im Hauptteil dieser Funktion hinzugefügt.
  6. Deklarieren Sie einen Stapel mit dem Namen st1, um ganzzahlige Werte zu speichern.
  7. Deklarieren Sie einen Stapel mit dem Namen st2, um ganzzahlige Werte zu speichern.
  8. Verwenden Sie die Funktion emplace (), um die Ganzzahl 12 in den Stapel mit dem Namen st1 einzufügen.
  9. Verwenden Sie die Funktion emplace (), um die Ganzzahl 19 in den Stapel mit dem Namen st1 einzufügen.
  10. Verwenden Sie die Funktion emplace (), um die Ganzzahl 20 in den Stapel mit dem Namen st2 einzufügen.
  11. Verwenden Sie die Funktion emplace (), um die Ganzzahl 23 in den Stapel mit dem Namen st2 einzufügen.
  12. Verwenden Sie die Funktion swap (), um den Inhalt der beiden Stapel st1 und st2 auszutauschen. Der Inhalt des Stapels st1 sollte in den Stapel st2 verschoben werden. Der Inhalt des Stapels st2 sollte in den Stapel st1 verschoben werden.
  13. Drucken Sie Text auf der Konsole.
  14. Verwenden Sie die while-Anweisung und die Funktion empty (), um zu überprüfen, ob der Stapel st1 nicht leer ist.
  15. Drucken Sie den Inhalt des Stapels st1 auf der Konsole. Das "" fügt beim Drucken auf der Konsole Platz zwischen den Stapelelementen hinzu.
  16. Führen Sie die Funktion pop () auf dem Stapel st1 aus, um das oberste Element zu entfernen.
  17. Ende des Textes der while-Anweisung.
  18. Drucken Sie Text auf der Konsole. Das endl ist ein C ++ - Schlüsselwort für die Endzeile. Der Mauszeiger bewegt sich zur nächsten Zeile, um von dort aus mit dem Drucken zu beginnen.
  19. Verwenden Sie die while-Anweisung und die Funktion empty (), um zu überprüfen, ob der Stapel st2 nicht leer ist.
  20. Drucken Sie den Inhalt des Stapels st2 auf der Konsole. Das "" fügt beim Drucken auf der Konsole Platz zwischen den Stapelelementen hinzu.
  21. Führen Sie die Funktion pop () auf dem Stapel st2 aus, um das oberste Element zu entfernen.
  22. Ende des Textes der while-Anweisung.
  23. Ende des Körpers der main () - Funktion.

Stapel in STL

Die STL (Standard Template Library) enthält Vorlagenklassen, die allgemeine C ++ - Datenstrukturen bereitstellen. Daher kann ein Stapel auch in STL implementiert werden. Wir nehmen diese Bibliothek einfach in unseren Code auf und definieren damit einen Stapel.

stack st;

Die obige Syntax deklariert einen Stapel st für Elemente vom Datentyp T.

Beispiel 3:

#include #include #include using namespace std;int main() {stack st;st.push(12);st.push(19);st.push(20);cout << st.top();cout << st.size();}

Ausgabe:

Hier ist ein Screenshot des Codes:

Code Erläuterung:

  1. Fügen Sie die iostream-Headerdatei in unseren Code ein, um ihre Funktionen zu nutzen.
  2. Fügen Sie die Stack-Header-Datei in unseren Code ein, um ihre Funktionen zu nutzen.
  3. Fügen Sie die cstdlib-Headerdatei in unseren Code ein, um ihre Funktionen zu nutzen.
  4. Fügen Sie den Standard-Namespace in unseren Code ein, um seine Klassen zu verwenden, ohne ihn aufzurufen.
  5. Rufen Sie die Funktion main () auf. Die Programmlogik sollte im Hauptteil dieser Funktion hinzugefügt werden.
  6. Deklarieren Sie einen Stapel st, um ganzzahlige Daten zu speichern.
  7. Fügen Sie das Element 12 zum Stapel hinzu.
  8. Fügen Sie das Element 19 zum Stapel hinzu.
  9. Fügen Sie das Element 20 zum Stapel hinzu.
  10. Drucken Sie das Element oben auf dem Stapel auf der Konsole.
  11. Drucken Sie die Größe des Stapels auf der Konsole.
  12. Ende des Hauptteils der Funktion main ().

Zusammenfassung:

  • Ein Stapel ist eine Datenstruktur, die auf der LIFO-Technik (Last In First Out) basiert.
  • Mit dem std :: stack können nur Elemente an einem Ende hinzugefügt und entfernt werden.
  • Die std :: stack-Klasse ist ein Containeradapter, der Elemente eines ähnlichen Datentyps enthält.
  • Ein Stapel kann aus verschiedenen Sequenzcontainern erstellt werden.
  • Wenn Sie keinen Container angeben, wird standardmäßig der Deque-Container verwendet.
  • Die push () -Funktion dient zum Einfügen von Elementen in den Stapel.
  • Die Funktion pop () dient zum Entfernen des obersten Elements aus dem Schritt.
  • Mit der Funktion empty () können Sie überprüfen, ob ein Stapel leer ist oder nicht.