Układaj C++ STL z przykładem

Co to jest std::stack?

Stos to struktura danych, która działa w oparciu o technikę LIFO (Last In First Out). Std::stack pozwala na dodawanie i usuwanie elementów tylko z jednego końca.

Klasa std::stack jest adapterem kontenera. Obiekty kontenerowe przechowują dane o podobnym typie danych. Możesz utworzyć stos z różnych kontenerów sekwencji. Jeśli nie podano kontenera, domyślnie zostanie użyty kontener deque. Adaptery kontenerów nie obsługują iteratorów, więc nie można ich używać do manipulowania danymi.

Składnia stosu

Aby utworzyć stos, musimy dołączyć plik plik nagłówkowy w naszym kodzie. Następnie używamy tej składni do zdefiniowania std::stack:

template <class Type, class Container = deque<Type> > class stack;
  • Typ – jest typem elementu zawartym w std::stack. Może być dowolny C++ typ lub nawet typ zdefiniowany przez użytkownika.
  • Pojemnik – jest typem bazowego obiektu kontenera.

Typy członków

Oto typy elementów stosu:

  • typ_wartości – Pierwszy parametr szablonu, T. Oznacza typ elementu.
  • typ_kontenera — drugi parametr szablonu, Kontener. Oznacza podstawowy typ kontenera.
  • size_type — typ całkowity bez znaku.

Operaw stosie

A C++ stos obsługuje następujące podstawowe operacje:

  • push – dodaje/umieszcza przedmiot na stosie.
  • pop – Usuwa/wyskakuje przedmiot ze stosu.
  • peek – Zwraca najwyższy element stosu bez jego usuwania.
  • isFull – sprawdza, czy stos jest pełny.
  • isEmpty – sprawdza, czy stos jest pusty.

Implementacja stosu

Implementacja stosu

Krok 1) Początkowo mamy pusty stos. Szczyt pustego stosu jest ustawiony na -1.

Krok 2) Następnie wepchnęliśmy element 5 na stos. Wierzchołek stosu będzie wskazywał element 5.

Krok 3) Następnie wsunęliśmy element 50 do stosu. Wierzchołek stosu przesuwa się i wskazuje na element 50.

Krok 4) Następnie wykonaliśmy operację pop, usuwając górny element ze stosu. Element 50 został usunięty ze stosu. Górna część stosu wskazuje teraz na element 5.

push() i pop()

Funkcje stack::push() dodają nowy element na górę stosu. Po włożeniu rozmiar stosu zwiększa się o 1. Funkcja przyjmuje następującą składnię:

stack.push(value)

Wartość to element, który należy wstawić do stosu.

Funkcja stos:: pop() usuwa górny element stosu. To najnowszy element stosu. Po usunięciu wielkość stosu zmniejsza się o 1. Oto składnia funkcji:

stack.pop()

Funkcja nie przyjmuje parametrów.

1 przykład:

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

Wyjście:

push() i pop()

Oto zrzut ekranu kodu:

push() i pop()

Wyjaśnienie kodu:

  1. Dołącz plik nagłówkowy iostream do naszego kodu, aby móc korzystać z jego funkcji.
  2. Dołącz plik nagłówkowy stosu do naszego kodu, aby móc korzystać z jego funkcji.
  3. Dołącz przestrzeń nazw std do naszego kodu, aby używać jej klas bez wywoływania jej.
  4. Wywołaj funkcję main(). W ramach tej funkcji należy dodać logikę programu.
  5. Utwórz stos do przechowywania wartości całkowitych.
  6. Użyj funkcji push(), aby wstawić wartość 10 do stosu.
  7. Użyj funkcji push(), aby wstawić wartość 20 do stosu.
  8. Użyj funkcji push(), aby wstawić wartość 30 do stosu.
  9. Użyj funkcji push(), aby wstawić wartość 40 do stosu.
  10. Użyj funkcji pop(), aby usunąć górny element ze stosu, czyli 40. Górny element ma teraz wartość 30.
  11. Użyj funkcji pop(), aby usunąć górny element ze stosu, czyli 30. Górny element ma teraz wartość 20.
  12. Użyj pętli while i funkcji empty(), aby sprawdzić, czy stos NIE jest pusty. ! to operator NOT.
  13. Drukowanie bieżącej zawartości stosu na konsoli.
  14. Wywołaj funkcję pop() na stosie.
  15. Koniec treści pętli while.
  16. Koniec treści funkcji main().

pusty(), rozmiar(), górny()

Stosy mają wbudowane funkcje, których możesz używać do zabawy ze stosem i jego wartościami. Obejmują one:

  • pusty() – sprawdza, czy stos jest pusty, czy nie.
  • size() - zwraca rozmiar stosu, czyli liczbę elementów w stosie.
  • top() - uzyskuje dostęp do elementu stosu na górze.

2 przykład:

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

Wyjście:

pusty(),rozmiar(),górny()

Oto zrzut ekranu kodu:

pusty(),rozmiar(),górny()

Wyjaśnienie kodu:

  1. Dołącz plik nagłówkowy iostream do naszego kodu, aby móc korzystać z jego funkcji.
  2. Dołącz plik nagłówkowy stosu do naszego kodu, aby móc korzystać z jego funkcji.
  3. Dołącz przestrzeń nazw std do naszego programu, aby móc korzystać z jej klas bez wywoływania jej.
  4. Utwórz funkcję createStack, której możemy użyć do utworzenia stosu mystack. Stos będzie zawierał zbiór liczb całkowitych.
  5. Początek treści funkcji createStack.
  6. Utwórz instancję typu danych mystack i nadaj jej nazwę ms.
  7. Użyj pętli while i funkcji pusty(), aby sprawdzić, czy stos jest pusty.
  8. Początek treści pętli while.
  9. Użyj funkcji top() przechowywanej na górze stosu. Znak \t utworzy nową kartę.
  10. Użyj funkcji pop(), aby usunąć element na górze stosu.
  11. Koniec treści pętli while.
  12. Wydrukuj pustą linię na konsoli.
  13. Koniec treści funkcji createStack.
  14. Wywołaj funkcję main(). Logikę programu należy dodać w treści funkcji main().
  15. Początek treści funkcji main().
  16. Utwórz obiekt stosu st.
  17. Użyj funkcji push(), aby wstawić element 32 do stosu.
  18. Użyj funkcji push(), aby wstawić element 21 do stosu.
  19. Użyj funkcji push(), aby wstawić element 39 do stosu.
  20. Użyj funkcji push(), aby wstawić element 89 do stosu.
  21. Użyj funkcji push(), aby wstawić element 25 do stosu.
  22. Wydrukuj tekst na konsoli.
  23. Wywołaj funkcję createStack, aby wykonać powyższe operacje wstawiania do stosu.
  24. Wydrukuj rozmiar stosu na konsoli wraz z innym tekstem.
  25. Wydrukuj element na górze stosu na konsoli.
  26. Wydrukuj tekst na konsoli.
  27. Usuń element na górze stosu. Następnie zwróci elementy pozostałe na stosie.
  28. Wywołaj funkcję createStack, aby wykonać powyższe operacje.
  29. Program musi zwrócić wartość po pomyślnym zakończeniu.
  30. Koniec treści funkcji main().

emplace() i swap()

Oto inne wbudowane funkcje stosu:

  • emplace() - konstruuje, a następnie wstawia nowy element na górę stosu.
  • swap() - wymienia zawartość stosu z zawartością innego stosu.

3 przykład:

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

Wyjście:

umieszczanie() i zamiana()

Oto zrzut ekranu kodu:

umieszczanie() i zamiana()

Wyjaśnienie kodu:

  1. Dołącz plik nagłówkowy iostream do naszego kodu, aby móc korzystać z jego funkcji.
  2. Dołącz plik nagłówkowy stosu do naszego kodu, aby móc korzystać z jego funkcji.
  3. Dołącz plik nagłówkowy cstdlib do naszego kodu, aby móc korzystać z jego funkcji.
  4. Dołącz przestrzeń nazw std do naszego kodu, aby używać jej klas bez wywoływania jej.
  5. Wywołaj funkcję main(). Logika programu zostanie dodana w treści tej funkcji.
  6. Zadeklaruj stos o nazwie st1 do przechowywania wartości całkowitych.
  7. Zadeklaruj stos o nazwie st2 do przechowywania wartości całkowitych.
  8. Użyj funkcji emplace(), aby wstawić liczbę całkowitą 12 do stosu o nazwie st1.
  9. Użyj funkcji emplace(), aby wstawić liczbę całkowitą 19 do stosu o nazwie st1.
  10. Użyj funkcji emplace(), aby wstawić liczbę całkowitą 20 do stosu o nazwie st2.
  11. Użyj funkcji emplace(), aby wstawić liczbę całkowitą 23 do stosu o nazwie st2.
  12. Użyj funkcji swap(), aby zamienić zawartość dwóch stosów, st1 i st2. Zawartość stosu st1 należy przenieść na stos st2. Zawartość stosu st2 należy przenieść na stos st1.
  13. Wydrukuj tekst na konsoli.
  14. Użyj instrukcji while i funkcji pusty(), aby sprawdzić, czy stos st1 nie jest pusty.
  15. Wydrukuj zawartość stosu st1 na konsoli. „ ” dodaje odstęp pomiędzy elementami stosu podczas drukowania ich na konsoli.
  16. Wykonaj funkcję pop() na stosie st1, aby usunąć górny element.
  17. Koniec treści instrukcji while.
  18. Wydrukuj tekst na konsoli. Koniec jest a C++ słowo kluczowe dla linii końcowej. Przesuwa kursor myszy do następnej linii, aby rozpocząć drukowanie od tego miejsca.
  19. Użyj instrukcji while i funkcji pusty(), aby sprawdzić, czy stos st2 nie jest pusty.
  20. Wydrukuj zawartość stosu st2 na konsoli. „ ” dodaje odstęp pomiędzy elementami stosu podczas drukowania ich na konsoli.
  21. Wykonaj funkcję pop() na stosie st2, aby usunąć górny element.
  22. Koniec treści instrukcji while.
  23. Koniec treści funkcji main().

Stos w STL

Biblioteka STL (Standard Template Library) zawiera klasy szablonów, które zapewniają wspólne C++ struktury danych. Dlatego stos można również zaimplementować w STL. Po prostu włączamy tę bibliotekę do naszego kodu i używamy jej do zdefiniowania stosu.

stack<T> st; 

Powyższa składnia deklaruje stos st dla elementów typu danych T.

4 przykład:

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

Wyjście:

Stos w STL

Oto zrzut ekranu kodu:

Stos w STL

Wyjaśnienie kodu:

  1. Dołącz plik nagłówkowy iostream do naszego kodu, aby móc korzystać z jego funkcji.
  2. Dołącz plik nagłówkowy stosu do naszego kodu, aby móc korzystać z jego funkcji.
  3. Dołącz plik nagłówkowy cstdlib do naszego kodu, aby móc korzystać z jego funkcji.
  4. Dołącz przestrzeń nazw std do naszego kodu, aby używać jej klas bez wywoływania jej.
  5. Wywołaj funkcję main(). Logikę programu należy dodać w treści tej funkcji.
  6. Zadeklaruj st stos do przechowywania danych całkowitych.
  7. Dodaj element 12 do stosu.
  8. Dodaj element 19 do stosu.
  9. Dodaj element 20 do stosu.
  10. Wydrukuj element na górze stosu na konsoli.
  11. Wydrukuj rozmiar stosu na konsoli.
  12. Koniec treści funkcji main().

Podsumowanie

  • Stos to struktura danych działająca w oparciu o technikę LIFO (Last In First Out).
  • Std::stack pozwala na dodawanie i usuwanie elementów tylko z jednego końca.
  • Klasa std::stack to adapter kontenera przechowujący elementy o podobnym typie danych.
  • Stos można utworzyć z różnych kontenerów sekwencji.
  • Jeśli nie podasz kontenera, domyślnie zostanie użyty kontener deque.
  • Funkcja push() służy do wstawiania elementów na stos.
  • Funkcja pop() służy do usuwania najwyższego elementu z kroku.
  • Funkcja pusty() służy do sprawdzania, czy stos jest pusty, czy nie.