Stack in C++ STL mit Beispiel

Was ist std::stack?

Ein Stack ist eine Datenstruktur, die auf der Grundlage der LIFO-Technik (Last In First Out) arbeitet. Der std::stack erlaubt das Hinzufügen und Entfernen von Elementen nur an einem Ende.

Die Klasse std::stack ist ein Containeradapter. Containerobjekte enthalten Daten eines ähnlichen Datentyps. Sie können einen Stack aus verschiedenen Sequenzcontainern erstellen. Wenn kein Container bereitgestellt wird, wird standardmäßig der Deque-Container verwendet. Container-Adapter unterstützen keine Iteratoren, sodass sie nicht zur Manipulation von Daten verwendet werden können.

In diesem C++-Tutorial lernen Sie

• Was ist std::stack?
• Stack-Syntax
• Mitgliedstypen
• Operationen im Stack
• Stack-Implementierung
• push() und pop()
• leer(), size(), top()
• emplace() und swap()
• In STL stapeln

Stack-Syntax

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

zu definieren

template <class Type, class Container = deque<Type> > class stack;

• Typ – ist der Typ des Elements, das im std::stack enthalten ist. Es kann jeder gültige C++-Typ oder sogar ein benutzerdefinierter Typ sein.
• Behälter – ist der Typ des zugrunde liegenden Containerobjekts.

Mitgliedstypen

Hier sind Stack-Member-Typen:

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

Operationen im Stack

Ein C++ Stack unterstützt die folgenden grundlegenden Operationen:

• push – Es fügt ein Element hinzu/schiebt es in den Stapel.
• pop – Es entfernt/knallt ein Element aus dem Stapel.
• peek – Gibt das oberste Element des Stapels zurück, ohne es zu entfernen.
• isFull – Überprüft, ob ein Stack voll ist.
• isEmpty – Prüft, ob ein Stack leer ist.

Stack-Implementierung

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

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

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

Schritt 4) Wir haben dann eine Pop-Operation durchgeführt und das oberste Element aus dem Stapel entfernt. Das Element 50 wird aus dem Stapel gezogen. Die Spitze des Stapels zeigt jetzt auf das Element 5.

push() und pop()

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

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 Stacks. 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 übernimmt keine Parameter.

Beispiel 1:

#include <iostream> 
#include <stack> 
using namespace std;
int main() {
	stack<int> 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-Erklärung:

1. Fügen Sie die iostream-Header-Datei in unseren Code ein, um ihre Funktionen zu nutzen.
2. Schließen Sie die Stack-Header-Datei in unseren Code ein, um ihre Funktionen zu verwenden.
3. Fügen Sie den std-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 Stack st, um ganzzahlige Werte zu speichern.
6. Verwenden Sie die Funktion push(), um den Wert 10 in den Stack einzufügen.
7. Verwenden Sie die Funktion push(), um den Wert 20 in den Stack einzufügen.
8. Verwenden Sie die Funktion push(), um den Wert 30 in den Stack einzufügen.
9. Verwenden Sie die Funktion push(), um den Wert 40 in den Stack einzufügen.
10. Verwenden Sie die pop()-Funktion, um das oberste Element aus dem Stapel zu entfernen, also 40. Das oberste Element wird jetzt 30.
11. Verwenden Sie die pop()-Funktion, um das oberste Element aus dem Stapel zu entfernen, also 30. Das oberste Element wird jetzt 20.
12. Verwenden Sie eine while-Schleife und eine empty()-Funktion, um zu prüfen, ob der Stack NICHT leer ist. Das ! ist der NOT-Operator.
13. Ausgeben des aktuellen Inhalts des Stacks auf der Konsole.
14. Rufen Sie die Funktion pop() auf dem Stack auf.
15. Ende des Körpers der While-Schleife.
16. Ende des Hauptteils der main()-Funktion.

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

Stapel haben eingebaute Funktionen, die Sie verwenden können, um mit dem Stapel und seinen Werten herumzuspielen. Dazu gehören:

• empty()- überprüft, ob ein Stack 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 ganz oben zu.

Beispiel 2:

#include <iostream> 
#include <stack>  
using namespace std;
void createStack(stack <int> mystack)
{
	stack <int> ms = mystack;
	while (!ms.empty())
	{
		cout << '\t' << ms.top();
		ms.pop();
	}
	cout << '\n';
}
int main()
{
	stack <int> 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-Erklärung:

1. Fügen Sie die iostream-Header-Datei in unseren Code ein, um ihre Funktionen zu nutzen.
2. Schließen Sie die Stack-Header-Datei in unseren Code ein, um ihre Funktionen zu nutzen.
3. Nehmen Sie den std-Namensraum in unser Programm auf, um seine Klassen zu verwenden, ohne ihn aufzurufen.
4. Erstellen Sie die Funktion createStack, mit der wir den Stack mystack erstellen können. Der Stapel enthält eine Reihe von ganzen Zahlen.
5. Der Anfang des Hauptteils der createStack-Funktion.
6. Erstellen Sie eine Instanz des mystack-Datentyps und geben Sie ihr den Namen ms.
7. Verwenden Sie die While-Schleife und die Funktion empty(), um zu prüfen, ob der Stack leer ist.
8. Der Beginn des Hauptteils der While-Schleife.
9. Verwenden Sie die top()-Funktion, die oben im Stack gespeichert ist. Das Zeichen \t erstellt einen neuen Tab.
10. Verwenden Sie die pop()-Funktion, um das Element an der Spitze des Stapels zu löschen.
11. Ende des Körpers der While-Schleife.
12. Drucken Sie eine Leerzeile auf der Konsole.
13. Ende des Bodys der createStack-Funktion.
14. Rufen Sie die Funktion main() auf. Die Programmlogik sollte innerhalb des Hauptteils der main()-Funktion hinzugefügt werden.
15. Der Beginn des Hauptteils der Funktion main().
16. Erstelle ein Stapelobjekt st.
17. Verwenden Sie die Funktion push(), um das Element 32 in den Stack einzufügen.
18. Verwenden Sie die Funktion push(), um das Element 21 in den Stack einzufügen.
19. Verwenden Sie die Funktion push(), um das Element 39 in den Stack einzufügen.
20. Verwenden Sie die Funktion push(), um das Element 89 in den Stack einzufügen.
21. Verwenden Sie die Funktion push(), um das Element 25 in den Stack einzufügen.
22. Drucken Sie etwas Text auf der Konsole.
23. Rufen Sie die createStack-Funktion auf, um die obigen Einfügeoperationen in den Stack auszuführen.
24. Drucken Sie die Größe des Stapels auf der Konsole zusammen mit anderem Text.
25. Drucken Sie das Element am Anfang des Stapels auf der Konsole.
26. Drucken Sie etwas Text auf der Konsole.
27. Löschen Sie das Element ganz oben im Stapel. Anschließend werden die im Stack verbleibenden Elemente zurückgegeben.
28. Rufen Sie die createStack-Funktion auf, um die obigen Operationen auszuführen.
29. Das Programm muss nach erfolgreichem Abschluss einen Wert zurückgeben.
30. Ende des Hauptteils der Funktion main().

emplace() und swap()

Dies sind andere eingebaute Stack-Funktionen:

• emplace()- konstruiert dann ein neues Element am Anfang des Stapels.
• swap()- tauscht Stack-Inhalte mit den Inhalten eines anderen Stacks aus.

Beispiel 3:

#include <iostream>    
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st1;
	stack<int> 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-Erklärung:

1. Fügen Sie die iostream-Header-Datei in unseren Code ein, um ihre Funktionen zu nutzen.
2. Schließen Sie die Stack-Header-Datei in unseren Code ein, um ihre Funktionen zu verwenden.
3. Schließen Sie die cstdlib-Header-Datei in unseren Code ein, um ihre Funktionen zu nutzen.
4. Fügen Sie den std-Namespace in unseren Code ein, um seine Klassen zu verwenden, ohne ihn aufzurufen.
5. Rufen Sie die Funktion main() auf. Die Programmlogik wird innerhalb des Hauptteils dieser Funktion hinzugefügt.
6. Deklarieren Sie einen Stack namens st1, um Integer-Werte zu speichern.
7. Deklarieren Sie einen Stack namens st2, um Integer-Werte zu speichern.
8. Verwenden Sie die Funktion emplace(), um die Ganzzahl 12 in den Stack namens st1 einzufügen.
9. Verwenden Sie die Funktion emplace(), um die Ganzzahl 19 in den Stack namens st1 einzufügen.
10. Verwenden Sie die Funktion emplace(), um die Ganzzahl 20 in den Stack namens st2 einzufügen.
11. Verwenden Sie die Funktion emplace(), um die Ganzzahl 23 in den Stack namens st2 einzufügen.
12. Verwenden Sie die Funktion swap(), um den Inhalt der beiden Stacks, st1 und st2, auszutauschen. Der Inhalt des Stacks st1 soll auf den Stack st2 verschoben werden. Der Inhalt des Stacks st2 soll auf den Stack st1 verschoben werden.
13. Drucken Sie etwas Text auf der Konsole.
14. Prüfen Sie mit der while-Anweisung und der empty()-Funktion, ob der Stack st1 nicht leer ist.
15. Den Inhalt des Stapels st1 auf der Konsole ausgeben. Das „ “ fügt Platz zwischen den Stack-Elementen hinzu, wenn sie auf der Konsole gedruckt werden.
16. Führen Sie die Funktion pop() auf dem Stack st1 aus, um das oberste Element zu entfernen.
17. Ende des Hauptteils der while-Anweisung.
18. Drucken Sie etwas Text auf der Konsole. endl ist ein C++-Schlüsselwort für die Endzeile. Es bewegt den Mauszeiger zur nächsten Zeile, um von dort aus mit dem Drucken zu beginnen.
19. Prüfen Sie mit der while-Anweisung und der empty()-Funktion, ob der Stack st2 nicht leer ist.
20. Den Inhalt des Stapels st2 auf der Konsole ausgeben. Das „ “ fügt Platz zwischen den Stack-Elementen hinzu, wenn sie auf der Konsole gedruckt werden.
21. Führen Sie die Funktion pop() auf dem Stack st2 aus, um das oberste Element zu entfernen.
22. Ende des Hauptteils der while-Anweisung.
23. Ende des Hauptteils der Funktion main().

In STL stapeln

Die STL (Standard Template Library) enthält Vorlagenklassen, die allgemeine C++-Datenstrukturen bereitstellen. Daher kann ein Stack auch in STL implementiert werden. Wir binden diese Bibliothek einfach in unseren Code ein und verwenden sie, um einen Stack zu definieren.

stack<T> st; 

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

Beispiel 3:

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

Ausgabe:

Hier ist ein Screenshot des Codes:

Code-Erklärung:

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

Zusammenfassung:

• Ein Stack ist eine Datenstruktur, die auf der Grundlage der LIFO-Technik (Last In First Out) arbeitet.
• Der std::stack erlaubt nur das Hinzufügen und Entfernen von Elementen von einem Ende.
• Die Klasse std::stack ist ein Container-Adapter, der Elemente eines ähnlichen Datentyps enthält.
• Ein Stack kann aus verschiedenen Sequenzcontainern erstellt werden.
• Wenn Sie keinen Container angeben, wird standardmäßig der Deque-Container verwendet.
• Die Funktion push() dient zum Einfügen von Elementen in den Stack.
• Die Funktion pop() dient zum Entfernen des obersten Elements aus dem Schritt.
• Die Funktion empty() dient zum Prüfen, ob ein Stack leer ist oder nicht.