Stos
Lekcja 10 z 23 w kursie C++ – Standardowa biblioteka szablonów w Coddy.
W tym rozdziale poznasz adaptery kontenerów. Będą to stos, kolejka i kolejka priorytetowa.
Stos w C++ to struktura danych oparta na zasadzie LIFO (Last in-First out — ostatni na wejściu, pierwszy na wyjściu). Oznacza to, że elementy dodane do stosu jako ostatnie zostaną usunięte jako pierwsze, a dostęp do pierwszego elementu dodanego na stosie uzyskamy na końcu (jest to bardzo podobne do układania talerzy lub naleśników w stos. Gdy układasz talerze w stos, nie możesz sięgnąć po talerz znajdujący się na samym dole, dodany jako pierwszy — musisz zdjąć ostatni talerz z góry).
stack<dataType> stackName;Aby utworzyć stos w C++, najpierw musimy dołączyć plik nagłówkowy stack na początku pliku C++ za pomocą #include <stack>.
Następnie możemy zadeklarować zmienną stosową, jak pokazano poniżej.
stack<int> number_stack = {1, 2, 3};Jak więc dodawać elementy do stosu? — Używamy metody push().
stack<int> number_stack;
number_stack.push(1);
number_stack.push(2);
...W ten sposób możemy dodawać nowe elementy do stosu.
Musimy też wyświetlać elementy na ekranie. Robimy to za pomocą metody top(), która zwraca ostatnią wartość znajdującą się na szczycie stosu.
cout << number_stack.top();Output:
2Jeśli jednak będziemy dalej wyświetlać na ekranie wynik top(), będziemy wciąż otrzymywać ostatni element — w tym przypadku 2. Potrzebujemy więc metody, która pozwoli usunąć element ze szczytu. W tym celu używamy metody pop(), która usuwa ostatni element ze szczytu stosu.
cout << number_stack.top() << endl;
number_stack.pop();
cout << number_stack.top();Output:
2
1Podsumowując, struktura danych stos jest bardzo przydatna w C++, programowaniu i programowaniu konkursowym. Jej kluczową cechą jest wykorzystywanie zasady Last in-First out.
Metody stosu
| Metoda | Działanie |
size() | Zwraca liczbę elementów na stosie |
empty() | Zwraca true, jeśli stos jest pusty, a w przeciwnym razie false |
swap() | Zamienia zawartość jednego stosu z zawartością innego |
Wyzwanie
ŁatwyOtrzymujesz liczbę N z wejścia. W kolejnych N wierszach znajduje się po jednej liczbie.
Używając stosu, wypisz każdą wprowadzoną liczbę, zaczynając od ostatniej i cofając się.
Input
5
1
2
3
4
5Output
5
4
3
2
1Spróbuj swoich sił
#include <stack>
#include <iostream>
using namespace std;
int main()
{
// Enter your code here
return 0;
}Wszystkie lekcje w sekcji C++ – Standardowa biblioteka szablonów
Poćwicz samodzielnie: Kompilator C++ online