Stivuiți C++ STL cu Exemplu

Ce este std::stack?

O stivă este o structură de date care funcționează pe baza tehnicii LIFO (Last In First Out). Std::stack permite adăugarea și eliminarea elementelor doar de la un capăt.

Clasa std::stack este un adaptor de containere. Obiectele container conțin date de tip similar. Puteți crea o stivă din diverse containere de secvență. Dacă nu este furnizat niciun container, containerul deque va fi utilizat în mod implicit. Adaptoarele de containere nu acceptă iteratoare, deci nu pot fi utilizate pentru manipularea datelor.

Sintaxa stivei

Pentru a crea o stivă, trebuie să includem fișier antet în codul nostru. Apoi folosim această sintaxă pentru a defini std::stack:

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

• Tip – este Tipul de element conținut în std::stack. Poate fi orice valabil C++ tip sau chiar un tip definit de utilizator.
• Recipient – este tipul obiectului container subiacent.

Tipuri de membri

Iată tipurile de membri ai stivei:

• tipul valorii– Primul parametru al șablonului, T. Acesta denotă tipurile de elemente.
• tip_container– Al doilea parametru al șablonului, Container. Acesta indică tipul de container subiacent.
• tip_dimensiune– Tip integral fără semn.

Operaîn Stiva

A C++ stack acceptă următoarele operații de bază:

• împinge – Adaugă/împinge un element în stivă.
• pop – Elimină/scoate un element din stivă.
• arunca o privire – Returnează elementul de sus din stivă fără a-l elimina.
• estePlin – Verifică dacă o stivă este plină.
• este gol – Verifică dacă o stivă este goală.

Implementarea stivei

Următorii pași arată cum se schimbă partea de sus a stivei pe măsură ce obiectele sunt împinse și apoi scoase:

Pasul 1) Inițial avem o stivă goală. Valoarea superioară a unei stive goale este setată la -1.

Pasul 2) În continuare, am introdus elementul 5 în stivă. Partea de sus a stivei va indica elementul 5.

Pasul 3) În continuare, am introdus elementul 50 în stivă. Partea superioară a stivei se deplasează și indică elementul 50.

Pasul 4) Am efectuat apoi o operație de extragere, eliminând elementul de sus din stivă. Elementul 50 este extras din stivă. Vârful stivei indică acum elementul 5.

push() și pop()

Funcția stack::push() adaugă un element nou în partea de sus a stivei. Dimensiunea stivei este mărită cu 1 după inserare. Funcția adoptă următoarea sintaxă:

stack.push(value)

Valoarea este elementul de inserat în stivă.

Funcția stack::pop() elimină elementul de sus al stivei. Acesta este cel mai nou element al stivei. Dimensiunea stivei este redusă cu 1 după eliminare. Iată sintaxa funcției:

stack.pop()

Funcția nu acceptă parametri.

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

ieșire:

Iată o captură de ecran a codului:

Code Explicaţie:

1. Includeți fișierul antet iostream în codul nostru pentru a utiliza funcțiile acestuia.
2. Includeți fișierul antet stivei în codul nostru pentru a-i folosi funcțiile.
3. Includeți spațiul de nume std în codul nostru pentru a-i folosi clasele fără a-l apela.
4. Apelați funcția main(). Logica programului ar trebui adăugată în această funcție.
5. Creați o stivă st pentru a stoca valori întregi.
6. Utilizați funcția push() pentru a introduce valoarea 10 în stivă.
7. Utilizați funcția push() pentru a introduce valoarea 20 în stivă.
8. Utilizați funcția push() pentru a introduce valoarea 30 în stivă.
9. Utilizați funcția push() pentru a introduce valoarea 40 în stivă.
10. Utilizați funcția pop() pentru a elimina elementul de sus din stivă, adică 40. Elementul de sus devine acum 30.
11. Utilizați funcția pop() pentru a elimina elementul de sus din stivă, adică 30. Elementul de sus devine acum 20.
12. Utilizați o buclă while și funcția empty() pentru a verifica dacă stiva NU este goală. Cel! este operatorul NOT.
13. Imprimarea conținutului curent al stivei pe consolă.
14. Apelați funcția pop() din stivă.
15. Sfârșitul corpului buclei while.
16. Sfârșitul corpului funcției main().

gol(), dimensiune(), sus()

Stivele au funcții încorporate pe care le puteți folosi pentru a vă juca cu stiva și valorile sale. Acestea includ:

• gol()– verifică dacă o stivă este goală sau nu.
• mărimea()– returnează dimensiunea stivei, adică numărul de elemente dintr-o stivă.
• top()– accesează elementul stivei din partea de sus.

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

ieșire:

Iată o captură de ecran a codului:

Code Explicaţie:

1. Includeți fișierul antet iostream în codul nostru pentru a utiliza funcțiile acestuia.
2. Includeți fișierul antet stivei în codul nostru pentru a utiliza funcțiile acestuia.
3. Includeți spațiul de nume std în programul nostru pentru a utiliza clasele sale fără a-l apela.
4. Creați funcția createStack pe care o putem folosi pentru a crea stiva mystack. Stiva va conține un set de numere întregi.
5. Începutul corpului funcției createStack.
6. Creați o instanță a tipului de date mystack și dându-i numele ms.
7. Utilizați bucla while și funcția empty() pentru a verifica dacă stiva este goală.
8. Începutul corpului buclei while.
9. Utilizați funcția top() stocată în partea de sus a stivei. Caracterul \t va crea o filă nouă.
10. Utilizați funcția pop() pentru a șterge elementul din partea de sus a stivei.
11. Sfârșitul corpului buclei while.
12. Tipăriți o linie goală pe consolă.
13. Sfârșitul corpului funcției createStack.
14. Apelați funcția main(). Logica programului ar trebui adăugată în corpul funcției main().
15. Începutul corpului funcției main().
16. Creați un obiect de stivă st.
17. Utilizați funcția push() pentru a introduce elementul 32 în stivă.
18. Utilizați funcția push() pentru a introduce elementul 21 în stivă.
19. Utilizați funcția push() pentru a introduce elementul 39 în stivă.
20. Utilizați funcția push() pentru a introduce elementul 89 în stivă.
21. Utilizați funcția push() pentru a introduce elementul 25 în stivă.
22. Tipăriți ceva text pe consolă.
23. Apelați funcția createStack pentru a executa operațiunile de inserare de mai sus în stivă.
24. Imprimați dimensiunea stivei pe consolă alături de alt text.
25. Imprimați elementul din partea de sus a stivei pe consolă.
26. Tipăriți ceva text pe consolă.
27. Ștergeți elementul din partea de sus a stivei. Apoi va returna elementele rămase în stivă.
28. Apelați funcția createStack pentru a executa operațiunile de mai sus.
29. Programul trebuie să returneze valoare după finalizarea cu succes.
30. Sfârșitul corpului funcției main().

emplace() și swap()

Acestea sunt alte funcții de stivă încorporate:

• amplasare()– construcțiile inserează apoi un element nou în partea de sus a stivei.
• swap()– schimbă conținutul stivei cu conținutul altei stive.

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

ieșire:

Iată o captură de ecran a codului:

Code Explicaţie:

1. Includeți fișierul antet iostream în codul nostru pentru a utiliza funcțiile acestuia.
2. Includeți fișierul antet stivei în codul nostru pentru a-i folosi funcțiile.
3. Includeți fișierul antet cstdlib în codul nostru pentru a utiliza funcțiile acestuia.
4. Includeți spațiul de nume std în codul nostru pentru a-i folosi clasele fără a-l apela.
5. Apelați funcția main(). Logica programului va fi adăugată în corpul acestei funcții.
6. Declarați o stivă numită st1 pentru a stoca valori întregi.
7. Declarați o stivă numită st2 pentru a stoca valori întregi.
8. Utilizați funcția emplace() pentru a insera întregul 12 în stiva numită st1.
9. Utilizați funcția emplace() pentru a insera întregul 19 în stiva numită st1.
10. Utilizați funcția emplace() pentru a insera întregul 20 în stiva numită st2.
11. Utilizați funcția emplace() pentru a insera întregul 23 în stiva numită st2.
12. Utilizați funcția swap() pentru a schimba conținutul celor două stive, st1 și st2. Conținutul stivei st1 ar trebui mutat în stiva st2. Conținutul stivei st2 ar trebui mutat în stiva st1.
13. Tipăriți ceva text pe consolă.
14. Utilizați instrucțiunea while și funcția empty() pentru a verifica dacă stiva st1 nu este goală.
15. Imprimați conținutul stivei st1 pe consolă. „ ” adaugă spațiu între elementele stivei atunci când le imprimați pe consolă.
16. Executați funcția pop() pe stiva st1 pentru a elimina elementul de sus.
17. Sfârșitul corpului declarației while.
18. Imprimați ceva text pe consolă. Sfârșitul este a C++ cuvânt cheie pentru linia finală. Mută ​​cursorul mouse-ului pe linia următoare pentru a începe imprimarea de acolo.
19. Utilizați instrucțiunea while și funcția empty() pentru a verifica dacă stiva st2 nu este goală.
20. Imprimați conținutul stivei st2 pe consolă. „ ” adaugă spațiu între elementele stivei atunci când le imprimați pe consolă.
21. Executați funcția pop() pe stiva st2 pentru a elimina elementul de sus.
22. Sfârșitul corpului declarației while.
23. Sfârșitul corpului funcției main().

Stack în STL

STL (Bibliotecă de șabloane standard) vine cu clase de șabloane care oferă comun C++ structuri de date. Prin urmare, o stivă poate fi implementată și în STL. Pur și simplu includem această bibliotecă în codul nostru și o folosim pentru a defini o stivă.

stack<T> st; 

Sintaxa de mai sus declară o stivă st la elementele de tipul de date T.

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

ieșire:

Iată o captură de ecran a codului:

Code Explicaţie:

1. Includeți fișierul antet iostream în codul nostru pentru a utiliza funcțiile acestuia.
2. Includeți fișierul antet stivei în codul nostru pentru a-i folosi funcțiile.
3. Includeți fișierul antet cstdlib în codul nostru pentru a utiliza funcțiile acestuia.
4. Includeți spațiul de nume std în codul nostru pentru a-i folosi clasele fără a-l apela.
5. Apelați funcția main(). Logica programului ar trebui adăugată în corpul acestei funcții.
6. Declarați o stivă st pentru a stoca date întregi.
7. Adăugați elementul 12 în stivă.
8. Adăugați elementul 19 în stivă.
9. Adăugați elementul 20 în stivă.
10. Imprimați elementul din partea de sus a stivei pe consolă.
11. Imprimați dimensiunea stivei pe consolă.
12. Sfârșitul corpului funcției main().

Întrebări frecvente