Stapel in C++ STL met voorbeeld

Wat is std::stack?

Een stapel is een datastructuur die werkt op basis van de LIFO-techniek (Last In First Out). Met de std::stack kunnen elementen slechts vanaf één kant worden toegevoegd en verwijderd.

De std::stack-klasse is een containeradapter. Containerobjecten bevatten gegevens van een vergelijkbaar gegevenstype. U kunt een stapel maken van verschillende reekscontainers. Als er geen container is opgegeven, wordt standaard de deque containe gebruikt. Containeradapters ondersteunen geen iterators en kunnen dus 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 elk geldig C++-type zijn of zelfs een door de gebruiker gedefinieerd type.
  • Containers – is het type onderliggend containerobject.

Lidtypen

Hier zijn de typen stapelleden:

  • value_type- De eerste sjabloonparameter, T. Deze geeft de elementtypen aan.
  • container_type- De tweede sjabloonparameter, Container. Het geeft het onderliggende containertype aan.
  • size_type- Niet-ondertekend integraaltype.

Bewerkingen in stapel

A C + + stapel ondersteunt de following basisbewerkingen:

  • push – Het voegt een item toe/duwt het in de stapel.
  • pop – Het verwijdert/popt een item van de stapel.
  • peek – Geeft het bovenste item van de stapel terug zonder het te verwijderen.
  • isFull – Controleert of een stapel vol is.
  • isEmpty – Controleert of een stapel leeg is.

Stack-implementatie

Stack-implementatie

Stap 1) We hebben in eerste instantie een lege stapel. De bovenkant van een lege stapel wordt ingesteld op -1.

Stap 2) Vervolgens hebben we element 5 in de stapel geschoven. De bovenkant van de stapel wijst naar element 5.

Stap 3) Vervolgens hebben we het element 50 in de stapel geschoven. De bovenkant van de stapel verschuift en wijst naar het element 50.

Stap 4) Vervolgens hebben we een pop-operatie uitgevoerd, waarbij we het bovenste element van de stapel hebben verwijderd. Het element 50 wordt van de stapel geplukt. De bovenkant van de stapel wijst nu naar element 5.

push() en pop()

De functies stack::push() voegen een nieuw item bovenaan de stapel toe. De stapelgrootte wordt na het invoegen met een 1 vergroot. De functie heeft deze 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 item van de stapel. Na het verwijderen wordt de stapelgrootte met 1 verkleind. 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:

push() en pop()

Hier is een screenshot van de code:

push() en pop()

Code Verklaring:

  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 de functie empty() om te controleren of de stapel 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:

  • empty()- controleert of een stapel leeg is of niet.
  • size()- retourneert de grootte van de stapel, dat wil zeggen het aantal elementen in een stapel.
  • top() - geeft toegang tot het stapelelement bovenaan.

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:

leeg(),grootte(),top()

Hier is een screenshot van de code:

leeg(),grootte(),top()

Code Verklaring:

  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 createStack-functie 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 createStack-functie 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 bovenaan de stapel in.
  • swap()- wisselt stapelinhoud 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:

plaats()&wissel()

Hier is een screenshot van de code:

plaats()&wissel()

Code Verklaring:

  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. De endl is een C++-sleutelwoord 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 algemene C++-datastructuren bieden. 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 declares een stapel 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:

Stapel in STL

Hier is een screenshot van de code:

Stapel in STL

Code Verklaring:

  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().

Samengevat

  • Een stapel is een datastructuur die werkt op basis van de LIFO-techniek (Last In First Out).
  • De std::stack staat alleen toe dat items vanaf één kant worden toegevoegd en verwijderd.
  • De klasse std::stack is een containeradapter die items van een vergelijkbaar gegevenstype bevat.
  • Van verschillende sequentiecontainers kan een stapel worden gemaakt.
  • Als u geen container opgeeft, wordt standaard de deque-container gebruikt.
  • De push() functie is voor het invoegen van items in de stapel.
  • De functie pop() is bedoeld om het bovenste item uit de stap te verwijderen.
  • De functie empty() is bedoeld om te controleren of een stapel leeg is of niet.