Stapla in C++ STL med Exempel

Vad är std::stack?

En stack är en datastruktur som fungerar baserat på LIFO-tekniken (Last In First Out). Med std::stack kan element läggas till och tas bort endast från ena änden.

Klassen std::stack är en containeradapter. Containerobjekt innehåller data av en liknande datatyp. Du kan skapa en stack från olika sekvensbehållare. Om ingen container anges kommer deque-behållaren att användas som standard. Containeradaptrar stöder inte iteratorer, så de kan inte användas för att manipulera data.

Stack syntax

För att skapa en stack måste vi inkludera header-fil i vår kod. Vi använder sedan denna syntax för att definiera std::stack:

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

• Typ – är den typ av element som finns i std::stacken. Den kan vara vilken som helst giltig C++ typ eller till och med en användardefinierad typ.
• Behållare – är typen av underliggande containerobjekt.

Medlemstyper

Här är stackmedlemstyper:

• värdetyp– Den första mallparametern, T. Den anger elementtyperna.
• containertyp– Den andra mallparametern, Container. Den anger den underliggande containertypen.
• storlekstyp– Osignerad integraltyp.

Operationer i Stack

A C++ stack stöder följande grundläggande operationer:

• tryck – Den lägger till/skjuter in ett objekt i stapeln.
• pop – Den tar bort/poppar upp ett föremål från högen.
• titt – Returnerar det översta objektet i stacken utan att ta bort det.
• ärFull – Kontrollerar om en stapel är full.
• är tom – Kontrollerar om en stapel är tom.

Stackimplementering

Följande steg visar hur toppen av stapeln förskjuts när föremål trycks och sedan poppas upp:

Steg 1) Vi har initialt en tom stack. Toppen av en tom stack sätts till -1.

Steg 2) Sedan har vi tryckt in element 5 i stacken. Toppen av stacken kommer att peka mot element 5.

Steg 3) Härnäst har vi tryckt in element 50 i stacken. Toppen av stacken förskjuts och pekar mot element 50.

Steg 4) Vi har sedan utfört en pop-operation, där vi tar bort det översta elementet från stacken. Element 50 poppas upp från stacken. Toppen av stacken pekar nu mot element 5.

push() och pop()

Funktionen stack::push() lägger till ett nytt objekt högst upp i stacken. Stackstorleken ökas med 1 efter infogningen. Funktionen använder följande syntax:

stack.push(value)

Värdet är objektet som ska infogas i stapeln.

Funktionen stack::pop() tar bort det översta elementet i stacken. Detta är det nyaste elementet i stacken. Stackstorleken minskas med 1 efter borttagningen. Här är funktionens syntax:

stack.pop()

Funktionen tar inga parametrar.

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

Produktion:

Här är en skärmdump av koden:

Code Förklaring:

1. Inkludera iostream-huvudfilen i vår kod för att använda dess funktioner.
2. Inkludera stackhuvudfilen i vår kod för att använda dess funktioner.
3. Inkludera std-namnområdet i vår kod för att använda dess klasser utan att anropa det.
4. Anropa main()-funktionen. Programlogiken bör läggas till i denna funktion.
5. Skapa en stackst för att lagra heltalsvärden.
6. Använd push()-funktionen för att infoga värdet 10 i stacken.
7. Använd push()-funktionen för att infoga värdet 20 i stacken.
8. Använd push()-funktionen för att infoga värdet 30 i stacken.
9. Använd push()-funktionen för att infoga värdet 40 i stacken.
10. Använd pop()-funktionen för att ta bort det översta elementet från stacken, det vill säga 40. Det översta elementet blir nu 30.
11. Använd pop()-funktionen för att ta bort det översta elementet från stacken, det vill säga 30. Det översta elementet blir nu 20.
12. Använd en while loop och empty() funktion för att kontrollera om stacken INTE är tom. Den ! är NOT-operatören.
13. Skriver ut det aktuella innehållet i stapeln på konsolen.
14. Anropa pop()-funktionen i stacken.
15. Slutet på while-loopens kropp.
16. Slutet på huvuddelen () funktion.

tomma(), storlek(), topp()

Stackar har inbyggda funktioner som du kan använda för att leka med stacken och dess värden. Dessa inkluderar:

• tömma()– kontrollerar om en stapel är tom eller inte.
• storlek()– returnerar stackens storlek, det vill säga antalet element i en stack.
• bästa()– öppnar stackelementet högst upp.

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

Produktion:

Här är en skärmdump av koden:

Code Förklaring:

1. Inkludera iostream-huvudfilen i vår kod för att kunna använda dess funktioner.
2. Inkludera stackhuvudfilen i vår kod för att kunna använda dess funktioner.
3. Inkludera std-namnområdet i vårt program för att kunna använda dess klasser utan att anropa det.
4. Skapa funktionen createStack som vi kan använda för att skapa stacken mystack. Högen kommer att innehålla en uppsättning heltal.
5. Början av kroppen för createStack-funktionen.
6. Skapa en instans av mystack-datatypen och ge den namnet ms.
7. Använd while-loopen och funktionen empty() för att kontrollera om stacken är tom.
8. Början av while-loopens kropp.
9. Använd top()-funktionen lagrad överst i stacken. Tecknet \t skapar en ny flik.
10. Använd pop()-funktionen för att ta bort elementet överst i stacken.
11. Slutet på while-loopens kropp.
12. Skriv ut en tom rad på konsolen.
13. Slutet på kroppen av createStack-funktionen.
14. Anropa main()-funktionen. Programlogiken bör läggas till i huvuddelen av main()-funktionen.
15. Början av huvuddelen av funktion main().
16. Skapa ett stackobjekt st.
17. Använd push()-funktionen för att infoga elementet 32 ​​i stacken.
18. Använd push()-funktionen för att infoga elementet 21 ​​i stacken.
19. Använd push()-funktionen för att infoga elementet 39 ​​i stacken.
20. Använd push()-funktionen för att infoga elementet 89 ​​i stacken.
21. Använd push()-funktionen för att infoga elementet 25 ​​i stacken.
22. Skriv ut lite text på konsolen.
23. Anropa createStack-funktionen för att utföra ovanstående infogningsoperationer i stacken.
24. Skriv ut stapelns storlek på konsolen tillsammans med annan text.
25. Skriv ut elementet överst i stapeln på konsolen.
26. Skriv ut lite text på konsolen.
27. Ta bort elementet överst i stapeln. Det kommer sedan att returnera de element som finns kvar i stacken.
28. Anropa createStack-funktionen för att utföra ovanstående operationer.
29. Programmet måste returnera värde efter framgångsrikt slutförande.
30. Slutet på huvuddelen av funktion main().

emplace() och swap()

Det här är andra inbyggda stackfunktioner:

• placera()– konstruerar och infogar sedan ett nytt element högst upp i stacken.
• byta()– byter stackinnehåll med en annan stacks innehåll.

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

Produktion:

Här är en skärmdump av koden:

Code Förklaring:

1. Inkludera iostream-huvudfilen i vår kod för att använda dess funktioner.
2. Inkludera stackhuvudfilen i vår kod för att använda dess funktioner.
3. Inkludera cstdlib-huvudfilen i vår kod för att använda dess funktioner.
4. Inkludera std-namnområdet i vår kod för att använda dess klasser utan att anropa det.
5. Anropa main()-funktionen. Programlogiken kommer att läggas till i kroppen av denna funktion.
6. Deklarera en stack med namnet st1 för att lagra heltalsvärden.
7. Deklarera en stack med namnet st2 för att lagra heltalsvärden.
8. Använd funktionen emplace() för att infoga heltal 12 i stacken som heter st1.
9. Använd funktionen emplace() för att infoga heltal 19 i stacken som heter st1.
10. Använd funktionen emplace() för att infoga heltal 20 i stacken som heter st2.
11. Använd funktionen emplace() för att infoga heltal 23 i stacken som heter st2.
12. Använd swap()-funktionen för att byta innehållet i de två stackarna, st1 och st2. Innehållet i stack st1 ska flyttas till stack st2. Innehållet i stack st2 ska flyttas till stack st1.
13. Skriv ut lite text på konsolen.
14. Använd while-satsen och funktionen empty() för att kontrollera om stacken st1 inte är tom.
15. Skriv ut innehållet i stack st1 på konsolen. ” ” lägger till utrymme mellan stapelelementen när du skriver ut dem på konsolen.
16. Kör pop()-funktionen på stacken st1 för att ta bort det översta elementet.
17. Slutet på stundens brödtext.
18. Skriv ut lite text på konsolen. Änden är en C++ nyckelord för slutrad. Den flyttar muspekaren till nästa rad för att börja skriva ut därifrån.
19. Använd while-satsen och funktionen empty() för att kontrollera om stacken st2 inte är tom.
20. Skriv ut innehållet i stack st2 på konsolen. ” ” lägger till utrymme mellan stapelelementen när du skriver ut dem på konsolen.
21. Kör pop()-funktionen på stacken st2 för att ta bort det översta elementet.
22. Slutet på stundens brödtext.
23. Slutet på huvuddelen av funktionen main().

Stapla i STL

STL (Standard Template Library) kommer med mallklasser som ger gemensamma C++ datastrukturer. Därför kan en stack också implementeras i STL. Vi inkluderar helt enkelt detta bibliotek i vår kod och använder det för att definiera en stack.

stack<T> st; 

Ovanstående syntax deklarerar en stack st till element av datatyp T.

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

Produktion:

Här är en skärmdump av koden:

Code Förklaring:

1. Inkludera iostream-huvudfilen i vår kod för att använda dess funktioner.
2. Inkludera stackhuvudfilen i vår kod för att använda dess funktioner.
3. Inkludera cstdlib-huvudfilen i vår kod för att använda dess funktioner.
4. Inkludera std-namnområdet i vår kod för att använda dess klasser utan att anropa det.
5. Anropa main()-funktionen. Programlogiken bör läggas till i kroppen av denna funktion.
6. Deklarera en stack st för att lagra heltalsdata.
7. Lägg till elementet 12 i stapeln.
8. Lägg till elementet 19 i stapeln.
9. Lägg till elementet 20 i stapeln.
10. Skriv ut elementet överst i stapeln på konsolen.
11. Skriv ut stapelns storlek på konsolen.
12. Slutet på kroppen av funktionen main().

Vanliga frågor