Stable inn C++ STL med Eksempel

Hva er std::stack?

En stack er en datastruktur som opererer basert på LIFO (Last In First Out) teknikk. Std::-stakken lar elementer legges til og fjernes kun fra den ene enden.

std::stack-klassen er en containeradapter. Containerobjekter inneholder data av en lignende datatype. Du kan opprette en stakk fra forskjellige sekvenscontainere. Hvis ingen container er oppgitt, vil deque-containeren brukes som standard. Containeradaptere støtter ikke iteratorer, så de kan ikke brukes til å manipulere data.

Stabelsyntaks

For å lage en stabel må vi inkludere header-fil i koden vår. Vi bruker deretter denne syntaksen til å definere std::stack:

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

• typen – er typen element som finnes i std::-stakken. Den kan være hvilken som helst gyldig C++ type eller til og med en brukerdefinert type.
• Container – er typen underliggende beholderobjekt.

Medlemstyper

Her er stabelmedlemstyper:

• verditype– Den første malparameteren, T. Den angir elementtypene.
• beholdertype– Den andre malparameteren, Container. Den angir den underliggende containertypen.
• størrelsestype– Usignert integraltype.

Operasjoner i Stack

A C++ stack støtter følgende grunnleggende operasjoner:

• skyv – Den legger til/skyver et element i stabelen.
• pop – Den fjerner/popper opp et element fra stabelen.
• titt – Returnerer det øverste elementet i stabelen uten å fjerne det.
• er Full – Sjekker om en stabel er full.
• er tom – Sjekker om en stabel er tom.

Stackimplementering

Følgende trinn viser hvordan toppen av stabelen forskyves når elementer skyves og deretter poppes:

Trinn 1) Vi har i utgangspunktet en tom stabel. Toppen av en tom stabel settes til -1.

Trinn 2) Deretter har vi dyttet element 5 inn i stakken. Toppen av stakken vil peke mot element 5.

Trinn 3) Deretter har vi dyttet element 50 inn i stakken. Toppen av stakken forskyves og peker mot element 50.

Trinn 4) Vi har deretter utført en pop-operasjon, der vi fjerner det øverste elementet fra stakken. Element 50 poppes ut av stakken. Toppen av stakken peker nå mot element 5.

push() og pop()

Funksjonen stack::push() legger til et nytt element øverst i stakken. Størrelsen på stakken økes med 1 etter innsettingen. Funksjonen bruker denne syntaksen:

stack.push(value)

Verdien er elementet som skal settes inn i stabelen.

Funksjonen stack::pop() fjerner det øverste elementet i stakken. Dette er det nyeste elementet i stakken. Størrelsen på stakken reduseres med 1 etter fjerningen. Her er funksjonens syntaks:

stack.pop()

Funksjonen tar ingen parametere.

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

Utgang:

Her er et skjermbilde av koden:

Code Forklaring:

1. Inkluder iostream-headerfilen i koden vår for å bruke funksjonene.
2. Inkluder stabelhodefilen i koden vår for å bruke funksjonene.
3. Inkluder std-navneområdet i koden vår for å bruke klassene uten å kalle det.
4. Kalle hoved()-funksjonen. Programlogikken bør legges til i denne funksjonen.
5. Lag en stabel for å lagre heltallsverdier.
6. Bruk push()-funksjonen for å sette inn verdien 10 i stabelen.
7. Bruk push()-funksjonen for å sette inn verdien 20 i stabelen.
8. Bruk push()-funksjonen for å sette inn verdien 30 i stabelen.
9. Bruk push()-funksjonen for å sette inn verdien 40 i stabelen.
10. Bruk pop()-funksjonen for å fjerne toppelementet fra stabelen, det vil si 40. Toppelementet blir nå 30.
11. Bruk pop()-funksjonen for å fjerne toppelementet fra stabelen, det vil si 30. Toppelementet blir nå 20.
12. Bruk en while loop og empty() funksjon for å sjekke om stabelen IKKE er tom. Den ! er NOT-operatøren.
13. Skriver ut gjeldende innhold i stabelen på konsollen.
14. Kall opp pop()-funksjonen på stabelen.
15. Slutten av kroppen av while-løkken.
16. Slutten av hoved()-funksjonens hoveddel.

tomme(), størrelse(), topp()

Stabler har innebygde funksjoner som du kan bruke til å leke med stabelen og dens verdier. Disse inkluderer:

• tømme()– sjekker om en stabel er tom eller ikke.
• størrelse()– returnerer størrelsen på stakken, det vil si antall elementer i en stabel.
• topp()– åpner stakkelementet øverst.

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

Utgang:

Her er et skjermbilde av koden:

Code Forklaring:

1. Inkluder iostream-headerfilen i koden vår for å bruke funksjonene.
2. Inkluder stabelhodefilen i koden vår for å bruke funksjonene.
3. Inkluder std-navneområdet i programmet vårt for å bruke klassene uten å kalle det.
4. Lag funksjonen createStack som vi kan bruke til å lage stack mystack. Stabelen vil inneholde et sett med heltall.
5. Begynnelsen av kroppen til createStack-funksjonen.
6. Opprett en forekomst av mystack-datatypen og gi den navnet ms.
7. Bruk while-løkken og empty()-funksjonen for å sjekke om stabelen er tom.
8. Starten på kroppen til while-løkken.
9. Bruk top()-funksjonen som er lagret på toppen av stabelen. Tegnet \t vil lage en ny fane.
10. Bruk pop()-funksjonen for å slette elementet øverst i stabelen.
11. Slutten av kroppen av while-løkken.
12. Skriv ut en tom linje på konsollen.
13. Slutten av brødteksten til createStack-funksjonen.
14. Kalle hoved()-funksjonen. Programlogikken skal legges til i hoveddelen av hoved()-funksjonen.
15. Starten på hoveddelen av funksjonen main().
16. Lag et stabelobjekt st.
17. Bruk push()-funksjonen for å sette inn elementet 32 ​​i stabelen.
18. Bruk push()-funksjonen for å sette inn elementet 21 ​​i stabelen.
19. Bruk push()-funksjonen for å sette inn elementet 39 ​​i stabelen.
20. Bruk push()-funksjonen for å sette inn elementet 89 ​​i stabelen.
21. Bruk push()-funksjonen for å sette inn elementet 25 ​​i stabelen.
22. Skriv ut litt tekst på konsollen.
23. Kall createStack-funksjonen for å utføre innsettingsoperasjonene ovenfor i stabelen.
24. Skriv ut størrelsen på stabelen på konsollen sammen med annen tekst.
25. Skriv ut elementet på toppen av stabelen på konsollen.
26. Skriv ut litt tekst på konsollen.
27. Slett elementet på toppen av stabelen. Den vil da returnere elementene som er igjen i stabelen.
28. Kall createStack-funksjonen for å utføre operasjonene ovenfor.
29. Programmet må returnere verdi ved vellykket gjennomføring.
30. Slutten av hoveddelen av funksjonen main().

emplace() og swap()

Dette er andre innebygde stabelfunksjoner:

• plassere()– konstruerer og setter deretter inn et nytt element øverst i stakken.
• bytte()– utveksler stabelinnhold med innholdet i en annen stabel.

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

Utgang:

Her er et skjermbilde av koden:

Code Forklaring:

1. Inkluder iostream-headerfilen i koden vår for å bruke funksjonene.
2. Inkluder stabelhodefilen i koden vår for å bruke funksjonene.
3. Inkluder cstdlib-headerfilen i koden vår for å bruke funksjonene.
4. Inkluder std-navneområdet i koden vår for å bruke klassene uten å kalle det.
5. Kalle hoved()-funksjonen. Programlogikken vil bli lagt til i hoveddelen av denne funksjonen.
6. Deklarer en stabel som heter st1 for å lagre heltallsverdier.
7. Deklarer en stabel som heter st2 for å lagre heltallsverdier.
8. Bruk emplace()-funksjonen til å sette inn hele tallet 12 i stabelen som heter st1.
9. Bruk emplace()-funksjonen til å sette inn hele tallet 19 i stabelen som heter st1.
10. Bruk emplace()-funksjonen til å sette inn hele tallet 20 i stabelen som heter st2.
11. Bruk emplace()-funksjonen til å sette inn hele tallet 23 i stabelen som heter st2.
12. Bruk swap()-funksjonen til å bytte innholdet i de to stablene, st1 og st2. Innholdet i stabelen st1 skal flyttes til stabelen st2. Innholdet i stabelen st2 skal flyttes til stabelen st1.
13. Skriv ut litt tekst på konsollen.
14. Bruk while-setningen og funksjonen empty() for å sjekke om stabelen st1 ikke er tom.
15. Skriv ut innholdet i stabelen st1 på konsollen. " " legger til mellomrom mellom stabelelementene når de skrives ut på konsollen.
16. Utfør pop()-funksjonen på stabelen st1 for å fjerne toppelementet.
17. Slutten av brødteksten til while-utsagnet.
18. Skriv ut litt tekst på konsollen. Endl er en C++ nøkkelord for sluttlinje. Den flytter musepekeren til neste linje for å begynne utskriften derfra.
19. Bruk while-setningen og funksjonen empty() for å sjekke om stabelen st2 ikke er tom.
20. Skriv ut innholdet i stabelen st2 på konsollen. " " legger til mellomrom mellom stabelelementene når de skrives ut på konsollen.
21. Utfør pop()-funksjonen på stabelen st2 for å fjerne toppelementet.
22. Slutten av brødteksten til while-utsagnet.
23. Slutten av hoveddelen av hoved()-funksjonen.

Stable i STL

STL (Standard Template Library) kommer med malklasser som gir felles C++ datastrukturer. Derfor kan en stack også implementeres i STL. Vi inkluderer ganske enkelt dette biblioteket i koden vår og bruker det til å definere en stabel.

stack<T> st; 

Syntaksen ovenfor erklærer en stack st til elementer av datatype T.

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

Utgang:

Her er et skjermbilde av koden:

Code Forklaring:

1. Inkluder iostream-headerfilen i koden vår for å bruke funksjonene.
2. Inkluder stabelhodefilen i koden vår for å bruke funksjonene.
3. Inkluder cstdlib-headerfilen i koden vår for å bruke funksjonene.
4. Inkluder std-navneområdet i koden vår for å bruke klassene uten å kalle det.
5. Kalle hoved()-funksjonen. Programlogikken skal legges til i hoveddelen av denne funksjonen.
6. Deklarer en stabelst for å lagre heltallsdata.
7. Legg elementet 12 til stabelen.
8. Legg elementet 19 til stabelen.
9. Legg elementet 20 til stabelen.
10. Skriv ut elementet på toppen av stabelen på konsollen.
11. Skriv ut størrelsen på stabelen på konsollen.
12. Slutten av brødteksten til funksjonen main().

Spørsmål og svar