Stapel erin C++ STL met voorbeeld

Wat is std::stack?

Een stack is een datastructuur die werkt op basis van de LIFO (Last In First Out) techniek. De std::stack maakt het mogelijk om elementen toe te voegen en te verwijderen vanaf één kant.

De klasse `std::stack` is een containeradapter. Containerobjecten bevatten gegevens van een vergelijkbaar gegevenstype. Je kunt een stack maken van verschillende sequentiecontainers. Als er geen container wordt opgegeven, wordt standaard de `deque`-container gebruikt. Containeradapters ondersteunen geen iterators, dus ze kunnen niet worden gebruikt om gegevens te manipuleren.

Stapelsyntaxis

Om een ​​stapel te maken, moeten we de header-bestand in onze code. Vervolgens gebruiken we deze syntaxis om de std::stack:

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

• Type – is het type element in de std::stack. Het kan elke geldige waarde zijn C++ type of zelfs een door de gebruiker gedefinieerd type.
• Containers – is het type onderliggend containerobject.

Lidtypen

Hier zijn de typen stapelleden:

• waardetype– De eerste sjabloonparameter, T. Deze geeft de elementtypen aan.
• container_type– De tweede sjabloonparameter, Container. Deze geeft het onderliggende containertype aan.
• grootte_type– Ongetekend integraal type.

Operaties in Stack

A C++ stack ondersteunt de volgende basisbewerkingen:

• duwen – Het voegt een item toe aan de stapel.
• knal – Hiermee wordt een item van de stapel verwijderd.
• kijkje - Geeft het bovenste item van de stapel terug zonder het te verwijderen.
• isVol – Controleert of een stapel vol is.
• is leeg – Controleert of een stapel leeg is.

Stack-implementatie

De volgende stappen laten zien hoe de bovenkant van de stapel verschuift wanneer items erop worden geplaatst en er vervolgens weer vanaf worden gehaald:

Stap 1) We beginnen met een lege stapel. De bovenkant van een lege stapel wordt ingesteld op -1.

Stap 2) Vervolgens hebben we element 5 op de stapel geplaatst. De bovenkant van de stapel zal naar element 5 wijzen.

Stap 3) Vervolgens hebben we element 50 op de stapel geplaatst. De bovenkant van de stapel verschuift en wijst naar element 50.

Stap 4) We hebben vervolgens een pop-bewerking uitgevoerd, waarbij het bovenste element van de stapel is verwijderd. Element 50 is van de stapel verwijderd. De bovenkant van de stapel wijst nu naar element 5.

push() en pop()

De functie `stack::push()` voegt een nieuw item toe aan de bovenkant van de stapel. De grootte van de stapel wordt na de invoeging met 1 verhoogd. De functie gebruikt de volgende syntaxis:

stack.push(value)

De waarde is het item dat in de stapel moet worden ingevoegd.

De functie `stack::pop()` verwijdert het bovenste element van de stapel. Dit is het nieuwste element van de stapel. De grootte van de stapel wordt na de verwijdering met 1 verminderd. Hier is de syntaxis van de functie:

stack.pop()

De functie heeft geen parameters.

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

Output:

Hier is een screenshot van de code:

Code Uitleg:

1. Neem het iostream-headerbestand op in onze code om de functies ervan te gebruiken.
2. Neem het stackheaderbestand op in onze code om de functies ervan te gebruiken.
3. Neem de std-naamruimte op in onze code om de klassen ervan te gebruiken zonder deze aan te roepen.
4. Roep de functie main() aan. Binnen deze functie moet de programmalogica worden toegevoegd.
5. Maak een stapel st om gehele waarden op te slaan.
6. Gebruik de functie push() om de waarde 10 in de stapel in te voegen.
7. Gebruik de functie push() om de waarde 20 in de stapel in te voegen.
8. Gebruik de functie push() om de waarde 30 in de stapel in te voegen.
9. Gebruik de functie push() om de waarde 40 in de stapel in te voegen.
10. Gebruik de functie pop() om het bovenste element van de stapel te verwijderen, dat wil zeggen 40. Het bovenste element wordt nu 30.
11. Gebruik de functie pop() om het bovenste element van de stapel te verwijderen, dat wil zeggen 30. Het bovenste element wordt nu 20.
12. Gebruik een while-lus en empty()-functie om te controleren of de stack NIET leeg is. De ! is de NOT-operator.
13. De huidige inhoud van de stapel op de console afdrukken.
14. Roep de functie pop() op de stapel aan.
15. Einde van de body van de while-lus.
16. Einde van de hoofdtekst van de functie main().

leeg(), grootte(), top()

Stapels hebben ingebouwde functies die u kunt gebruiken om met de stapel en zijn waarden te spelen. Deze omvatten:

• leeg()– controleert of een stapel leeg is of niet.
• grootte()– geeft de grootte van de stapel weer, oftewel het aantal elementen in een stapel.
• bovenkant()– geeft toegang tot het bovenste element van de stapel.

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

Output:

Hier is een screenshot van de code:

Code Uitleg:

1. Neem het iostream-headerbestand op in onze code om de functies ervan te gebruiken.
2. Neem het stackheaderbestand op in onze code om de functies ervan te kunnen gebruiken.
3. Neem de std-naamruimte op in ons programma om de klassen ervan te gebruiken zonder deze aan te roepen.
4. Maak de functie createStack die we kunnen gebruiken om de stapel mystack te maken. De stapel bevat een reeks gehele getallen.
5. Het begin van de hoofdtekst van de createStack-functie.
6. Maak een instance van het datatype mystack en geef deze de naam ms.
7. Gebruik de while-lus en de empty()-functie om te controleren of de stapel leeg is.
8. Het begin van de hoofdtekst van de while-lus.
9. Gebruik de functie top() die bovenaan de stapel is opgeslagen. Het \t-teken maakt een nieuw tabblad aan.
10. Gebruik de functie pop() om het element bovenaan de stapel te verwijderen.
11. Einde van de body van de while-lus.
12. Druk een lege regel af op de console.
13. Einde van de hoofdtekst van de createStack-functie.
14. Roep de functie main() aan. De programmalogica moet worden toegevoegd aan de hoofdtekst van de functie main().
15. Het begin van de hoofdtekst van de functie main().
16. Maak een stapelobject st.
17. Gebruik de functie push() om element 32 in de stapel in te voegen.
18. Gebruik de functie push() om element 21 in de stapel in te voegen.
19. Gebruik de functie push() om element 39 in de stapel in te voegen.
20. Gebruik de functie push() om element 89 in de stapel in te voegen.
21. Gebruik de functie push() om element 25 in de stapel in te voegen.
22. Druk wat tekst af op de console.
23. Roep de functie createStack aan om de bovenstaande invoegbewerkingen in de stapel uit te voeren.
24. Druk de grootte van de stapel af op de console, samen met andere tekst.
25. Druk het element bovenaan de stapel op de console af.
26. Druk wat tekst af op de console.
27. Verwijder het element bovenaan de stapel. Vervolgens worden de resterende elementen in de stapel geretourneerd.
28. Roep de functie createStack aan om de bovenstaande bewerkingen uit te voeren.
29. Het programma moet waarde retourneren na succesvolle voltooiing.
30. Einde van de hoofdtekst van de functie main().

emplace() en swap()

Dit zijn andere ingebouwde stapelfuncties:

• emplace()– construeert en voegt vervolgens een nieuw element toe aan de bovenkant van de stapel.
• ruil()– Wisselt de inhoud van een stapel uit met de inhoud van een andere stapel.

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

Output:

Hier is een screenshot van de code:

Code Uitleg:

1. Neem het iostream-headerbestand op in onze code om de functies ervan te gebruiken.
2. Neem het stackheaderbestand op in onze code om de functies ervan te gebruiken.
3. Neem het cstdlib-headerbestand op in onze code om de functies ervan te gebruiken.
4. Neem de std-naamruimte op in onze code om de klassen ervan te gebruiken zonder deze aan te roepen.
5. Roep de functie main() aan. De programmalogica wordt toegevoegd aan de hoofdtekst van deze functie.
6. Declareer een stapel met de naam st1 om gehele waarden op te slaan.
7. Declareer een stapel met de naam st2 om gehele waarden op te slaan.
8. Gebruik de functie emplace() om het gehele getal 12 in de stapel met de naam st1 in te voegen.
9. Gebruik de functie emplace() om het gehele getal 19 in de stapel met de naam st1 in te voegen.
10. Gebruik de functie emplace() om het gehele getal 20 in de stapel met de naam st2 in te voegen.
11. Gebruik de functie emplace() om het gehele getal 23 in de stapel met de naam st2 in te voegen.
12. Gebruik de functie swap() om de inhoud van de twee stapels, st1 en st2, om te wisselen. De inhoud van de stapel st1 moet naar de stapel st2 worden verplaatst. De inhoud van de stapel st2 moet naar de stapel st1 worden verplaatst.
13. Druk wat tekst af op de console.
14. Gebruik de while-instructie en de empty()-functie om te controleren of de stapel st1 niet leeg is.
15. Druk de inhoud van de stapel st1 af op de console. De ” ” voegt ruimte toe tussen de stapelelementen wanneer deze op de console worden afgedrukt.
16. Voer de functie pop() uit op de stapel st1 om het bovenste element te verwijderen.
17. Einde van de hoofdtekst van de while-instructie.
18. Druk wat tekst af op de console. Het einde is een C++ trefwoord voor eindregel. Het verplaatst de muiscursor naar de volgende regel om vanaf daar te beginnen met afdrukken.
19. Gebruik de while-instructie en de empty()-functie om te controleren of de stapel st2 niet leeg is.
20. Druk de inhoud van de stapel st2 af op de console. De ” ” voegt ruimte toe tussen de stapelelementen wanneer deze op de console worden afgedrukt.
21. Voer de functie pop() uit op de stapel st2 om het bovenste element te verwijderen.
22. Einde van de hoofdtekst van de while-instructie.
23. Einde van de hoofdtekst van de functie main().

Stapel in STL

De STL (Standard Template Library) wordt geleverd met sjabloonklassen die gemeenschappelijke kenmerken bieden C++ datastructuren. Daarom kan een stapel ook in STL worden geïmplementeerd. We nemen deze bibliotheek eenvoudigweg op in onze code en gebruiken deze om een ​​stapel te definiëren.

stack<T> st; 

De bovenstaande syntaxis declareert een stack st naar elementen van gegevenstype T.

Voorbeeld 4:

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

Output:

Hier is een screenshot van de code:

Code Uitleg:

1. Neem het iostream-headerbestand op in onze code om de functies ervan te gebruiken.
2. Neem het stackheaderbestand op in onze code om de functies ervan te gebruiken.
3. Neem het cstdlib-headerbestand op in onze code om de functies ervan te gebruiken.
4. Neem de std-naamruimte op in onze code om de klassen ervan te gebruiken zonder deze aan te roepen.
5. Roep de functie main() aan. De programmalogica moet worden toegevoegd aan de hoofdtekst van deze functie.
6. Declareer een stapel st om gehele gegevens op te slaan.
7. Voeg element 12 toe aan de stapel.
8. Voeg element 19 toe aan de stapel.
9. Voeg element 20 toe aan de stapel.
10. Druk het element bovenaan de stapel op de console af.
11. Druk de grootte van de stapel af op de console.
12. Einde van de hoofdtekst van de functie main().

Veelgestelde vragen