Stos w C ++ STL z przykładem

Co to jest std :: stack?

Stos to struktura danych działająca w oparciu o technikę LIFO (Last In First Out). Std :: stack umożliwia dodawanie i usuwanie elementów tylko z jednego końca.

Klasa std :: stack jest adapterem kontenera. Obiekty kontenerów przechowują dane o podobnym typie danych. Możesz utworzyć stos z różnych kontenerów sekwencji. Jeśli kontener nie zostanie podany, 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.

W tym samouczku C ++ nauczysz się

• Co to jest std :: stack?
• Składnia stosu
• Typy członków
• Operacje w stosie
• Implementacja stosu
• push () i pop ()
• pusty (), rozmiar (), góra ()
• embrace () i swap ()
• Stos w STL

Składnia stosu

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

template  > class stack;

• Type - to typ elementu zawartego w std :: stack. Może to być dowolny prawidłowy typ C ++ lub nawet typ zdefiniowany przez użytkownika.
• Kontener - to typ bazowego obiektu kontenera.

Typy członków

Oto typy elementów stosu:

• typ_wartości - pierwszy parametr szablonu, T. Oznacza typy elementów.
• typ_kontenera - drugi parametr szablonu, kontener. Oznacza podstawowy typ kontenera.
• size_type - typ całkowity bez znaku.

Operacje w stosie

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

• push - dodaje / odkłada element do stosu.
• pop - usuwa / zdejmuje element ze stosu.
• peek - zwraca górny element stosu bez usuwania go.
• isFull - sprawdza, czy stos jest pełny.
• isEmpty - sprawdza, czy stos jest pusty.

Implementacja stosu

Krok 1) Początkowo mamy pusty stos. Wierzchołek pustego stosu jest ustawiany na -1.

Krok 2) Następnie włożyliśmy element 5 do stosu. Wierzchołek stosu będzie wskazywał na element 5.

Krok 3) Następnie włożyliśmy element 50 do stosu. Szczyt stosu przesuwa się i wskazuje element 50.

Krok 4) Następnie wykonaliśmy operację wyskakującą, usuwając górny element ze stosu. Element 50 jest zdejmowany ze stosu. Wierzchołek stosu wskazuje teraz na element 5.

push () i pop ()

Funkcje stack :: push () dodają nowy element na szczyt stosu. Rozmiar stosu jest zwiększany o 1 po włożeniu. Funkcja przyjmuje następującą składnię:

stack.push(value)

Wartość to element, który ma zostać wstawiony do stosu.

Funkcja stack :: pop () usuwa górny element stosu. To najnowszy przedmiot w stosie. Rozmiar stosu zmniejsza się o 1 po usunięciu. Oto składnia funkcji:

stack.pop()

Funkcja nie przyjmuje parametrów.

Przykład 1:

#include #include using namespace std;int main() {stack 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();}}

Wynik:

Oto zrzut ekranu kodu:

Objaśnienie kodu:

1. Dołącz plik nagłówkowy iostream do naszego kodu, aby móc korzystać z jego funkcji.
2. Dołącz plik nagłówka stosu do naszego kodu, aby móc korzystać z jego funkcji.
3. Uwzględnij przestrzeń nazw std w naszym kodzie, 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 st, aby przechowywać wartości całkowite.
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. The! jest operatorem NOT.
13. Drukowanie aktualnej 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óra ()

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

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

Przykład 2:

#include #include using namespace std;void createStack(stack  mystack){stack  ms = mystack;while (!ms.empty()){cout << '\t' << ms.top();ms.pop();}cout << '\n';}int main(){stack  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;}

Wynik:

Oto zrzut ekranu kodu:

Objaśnienie kodu:

1. Dołącz plik nagłówkowy iostream do naszego kodu, aby móc korzystać z jego funkcji.
2. Dołącz plik nagłówka stosu do naszego kodu, aby móc korzystać z jego funkcji.
3. Dołącz przestrzeń nazw std do naszego programu, aby używać jej klas bez wywoływania jej.
4. Utwórz funkcję createStack, której możemy użyć do utworzenia mystack stosu. Stos będzie zawierał zbiór liczb całkowitych.
5. Początek treści funkcji createStack.
6. Utwórz instancję typu mystack i nadaj jej nazwę ms.
7. Użyj pętli while i funkcji empty (), 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 znajdujący się na szczycie stosu.
11. Koniec treści pętli while.
12. Wydrukuj pusty wiersz 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 na stosie.
24. Wydrukuj rozmiar stosu na konsoli obok innego tekstu.
25. Wydrukuj element na szczycie stosu na konsoli.
26. Wydrukuj tekst na konsoli.
27. Usuń element na górze stosu. Następnie zwróci elementy pozostałe w 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 ().

embrace () i swap ()

Oto inne wbudowane funkcje stosu:

• embrace () - konstruuje, a następnie wstawia nowy element na szczyt stosu.
• swap () - zamienia zawartość stosu na zawartość innego stosu.

Przykład 3:

#include #include #include using namespace std;int main() {stack st1;stack 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();}}

Wynik:

Oto zrzut ekranu kodu:

Objaśnienie kodu:

1. Dołącz plik nagłówkowy iostream do naszego kodu, aby móc korzystać z jego funkcji.
2. Dołącz plik nagłówka 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. Uwzględnij przestrzeń nazw std w naszym kodzie, 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 embrace (), aby wstawić liczbę całkowitą 12 do stosu o nazwie st1.
9. Użyj funkcji embrace (), aby wstawić liczbę całkowitą 19 do stosu o nazwie st1.
10. Użyj funkcji embrace (), aby wstawić liczbę całkowitą 20 do stosu o nazwie st2.
11. Użyj funkcji embrace (), 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 empty (), aby sprawdzić, czy stos st1 nie jest pusty.
15. Wydrukuj zawartość stosu st1 na konsoli. "" Dodaje odstęp mię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. Endl jest słowem kluczowym C ++ oznaczającym linię końcową. Przenosi kursor myszy do następnej linii, aby rozpocząć drukowanie od tego miejsca.
19. Użyj instrukcji while i funkcji empty (), aby sprawdzić, czy stos st2 nie jest pusty.
20. Wydrukuj zawartość stosu st2 na konsoli. "" Dodaje odstęp mię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

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

stack st;

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

Przykład 3:

#include #include #include using namespace std;int main() {stack st;st.push(12);st.push(19);st.push(20);cout << st.top();cout << st.size();}

Wynik:

Oto zrzut ekranu kodu:

Objaśnienie kodu:

1. Dołącz plik nagłówkowy iostream do naszego kodu, aby móc korzystać z jego funkcji.
2. Dołącz plik nagłówka 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. Uwzględnij przestrzeń nazw std w naszym kodzie, 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 stosu 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 szczycie 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 umożliwia dodawanie i usuwanie elementów tylko z jednego końca.
• Klasa std :: stack jest adapterem kontenera przechowującym 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 do stosu.
• Funkcja pop () służy do usuwania najwyższego elementu z kroku.
• Funkcja empty () służy do sprawdzania, czy stos jest pusty, czy nie.