C++ · Kontenery STL · Stos

Stos (stack) w C++

Poznaj kontener stack — strukturę danych działającą na zasadzie LIFO (Last In, First Out). Jak stos talerzy: odkładasz i zdejmujesz zawsze z wierzchu.

Czym jest stos?

stack to kontener działający na zasadzie LIFO (Last In, First Out) — "kto ostatni wszedł, ten pierwszy wyjdzie". Dokładnie jak stos talerzy: talerz odkładamy na wierzch i zdejmujemy też zawsze ten, który jest na wierzchu. Do środka stosu nie da się zajrzeć — mamy dostęp tylko do elementu na samej górze.

skladnia.cpp
#include <stack>

stack<typ> nazwa;

// przykład:
stack<string> stosTalerzy;

push, top, pop, empty, size

Pięć operacji wystarczy, żeby swobodnie posługiwać się stosem. Każda z nich dotyczy zawsze tylko elementu na wierzchu.

⬆️

push(x)

Dodaje nowy element na wierzch stosu. Po dodaniu to on staje się elementem widocznym dla top().

👁️

top()

Pokazuje element na wierzchu stosu, nie usuwając go. To jedyne miejsce, do którego mamy dostęp.

⬇️

pop()

Usuwa element z wierzchu stosu. Uwaga: pop() nic nie zwraca — element trzeba najpierw odczytać przez top().

🧮

empty() / size()

empty() sprawdza, czy stos jest pusty (przed top()/pop() warto to zrobić), a size() zwraca liczbę elementów.

stos_talerzy.cpp
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    stack<string> stosTalerzy;

    stosTalerzy.push("Talerz 1");
    stosTalerzy.push("Talerz 2");
    stosTalerzy.push("Talerz 3");

    cout << "Na wierzchu: " << stosTalerzy.top();

    stosTalerzy.pop(); // zdejmuje "Talerz 3"

    return 0;
}
▶ Wyjście programu
Na wierzchu: Talerz 3

Opróżnianie stosu i sprawdzanie nawiasów

Typowy schemat pracy ze stosem: dopóki nie jest pusty, patrzymy na top(), robimy z nim coś, a potem wywołujemy pop(). Ten schemat idealnie nadaje się do sprawdzania, czy nawiasy w wyrażeniu są poprawnie dopasowane.

oproznianie.cpp
while (!stosTalerzy.empty()) {
    cout << stosTalerzy.top();
    stosTalerzy.pop();
}
▶ Kolejność zdejmowania
Odwrotna do kolejności dodawania — ostatni push() jest pierwszym pop().
nawiasy.cpp
stack<char> s;
bool poprawne = true;

for (char znak : wyrazenie) {
    if (znak == '(') s.push(znak);
    else if (s.empty()) poprawne = false;
    else s.pop();
}
▶ Pomysł
Nawias otwierający -> push. Nawias zamykający -> musi pasować do wierzchu stosu.

Wszystko, co robi się ze stosem

Stos jest jeszcze skromniejszy niż kolejka — ma dokładnie pięć operacji i każda kosztuje O(1). Cała jego siła bierze się z tego ograniczenia: skoro widać tylko wierzch, to nie da się niczego pomylić.

MetodaCo robiUwaga
s.push(x) Kładzie element na wierzch stosu. Jak dołożenie talerza
s.top() Podgląda element z wierzchu. Nie usuwa
s.pop() Zdejmuje wierzch. Nic nie zwraca — najpierw top()
s.size() / s.empty() Liczba elementów i test pustości. Sprawdzaj przed top()
szukanie elementu Niemożliwe — widać tylko wierzch. To cena za prostotę
s[i] Też niemożliwe. Potrzebujesz tego → weź vector
opróżnienie stosu Pętla while (!s.empty()) z pop(). Wychodzi w odwrotnej kolejności
vector jako stos push_back, back, pop_back. To samo, ale z dostępem do środka

Ostatni wiersz warto zapamiętać: rekurencja to też stos, tyle że zarządzany przez kompilator. Każde wywołanie funkcji odkłada na nim swoje zmienne lokalne, a powrót je zdejmuje. Dlatego zbyt głęboka rekurencja kończy się komunikatem stack overflow — i dlatego czasem opłaca się zamienić ją na własny stack, którym da się sterować.

Poniżej pięć sytuacji, w których stos jest właściwym narzędziem. Pierwsze trzy spotkasz od razu; dwie ostatnie pokazują, że stos działa też tam, gdzie go nie widać.

ZastosowanieNa czym polegaGdzie się pojawia
dopasowanie nawiasów Otwierający na stos, zamykający zdejmuje i sprawdza parę. Sprawdzanie poprawności wyrażeń
cofanie akcji Każda operacja ląduje na stosie, cofnięcie ją zdejmuje. Edytory tekstu, gry
odwracanie kolejności Włóż wszystko, potem zdejmij — wyjdzie od tyłu. Najprostsze zastosowanie stosu
obliczanie wyrażeń Liczby na stos, znak działania zdejmuje dwie i odkłada wynik. Kalkulatory
rekurencja pod spodem Komputer sam używa stosu, gdy funkcja woła samą siebie. Dlatego zbyt głęboka rekurencja się wysypuje

Sztuczka ze stosem

Tej sekcji nie musisz jeszcze rozumieć. Pokazujemy ją, bo to najładniejsza sztuczka, jaką da się zrobić stosem — wróć tu, gdy będziesz gotowy.

Zadanie brzmi: dla każdej liczby w tablicy znajdź pierwszą większą liczbę na prawo od niej. Najprościej byłoby dla każdej liczby przejrzeć całą resztę tablicy — ale to pętla w pętli, a przy milionie liczb, jak wiesz z tematu o szybkości, program by nie zdążył.

Sztuczka polega na zauważeniu, że większość porównań jest zbędna. Idąc od końca tablicy trzymamy na stosie tylko tych „kandydatów”, którzy mogą jeszcze komuś posłużyć za odpowiedź. Gdy napotkamy liczbę większą od tych ze stosu, te mniejsze możemy wyrzucić raz na zawsze — dla każdej kolejnej liczby z lewej lepszym kandydatem będzie właśnie ta większa.

monotoniczny.cpp
// stos trzyma kandydatów w kolejności malejącej od dołu
stack<int> s;

for (int i = n - 1; i >= 0; i--) {
    // wyrzuć wszystkich, którzy przegrywają z bieżącym
    while (!s.empty() && s.top() <= t[i])
        s.pop();

    wynik[i] = s.empty() ? -1 : s.top();
    s.push(t[i]);
}

// Dlaczego to jest O(n), skoro w środku jest while?
// Bo każdy element trafia na stos DOKŁADNIE RAZ
// i schodzi z niego co najwyżej raz. Razem 2n operacji.

Na pierwszy rzut oka wygląda to na pętlę w pętli — a przecież właśnie tego chcieliśmy uniknąć. To złudzenie: każda liczba wchodzi na stos dokładnie raz i schodzi z niego co najwyżej raz. Niezależnie od tego, jak długo kręci się wewnętrzny while, w sumie wykona się najwyżej dwa razy tyle kroków, ile jest liczb. Czyli jedno przejście, tylko zapisane nietypowo.

Ten sam schemat rozwiązuje całą rodzinę zadań: najbliższy mniejszy element, największy prostokąt w histogramie, ile dni do cieplejszej pogody, zbieranie wody deszczowej między słupkami. Za każdym razem zmienia się tylko warunek w while i kierunek przejścia.

Sprawdź się na zadaniach

Sześć zadań od najprostszego. Pierwsze trzy sprawdzają, czy rozumiesz zasadę „ostatni wszedł, pierwszy wychodzi”; dalsze to klasyki, w których stos naprawdę błyszczy. Rozwiązania są schowane — najpierw spróbuj sam.

Łatwe Odwróć kolejność
Wczytaj n liczb, wrzuć je na stos i wypisz. Sprawdź, co się stało z kolejnością.
Jak to ugryźć: Zadanie na rozgrzewkę i jednocześnie pokaz najprostszej własności stosu: ostatni włożony wychodzi pierwszy, więc wynik jest odwrócony. Pamiętaj — najpierw top(), potem pop().
Pokaż rozwiązanie
odwroc.cpp
#include <iostream>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;

    stack<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.push(x);
    }

    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }

    return 0;
}
Łatwe Czy nawiasy się zgadzają
Wczytaj napis złożony ze znaków ( i ) i sprawdź, czy nawiasy są poprawnie sparowane. Wypisz TAK albo NIE.
Jak to ugryźć: Otwierający nawias kładź na stos, zamykający — zdejmuj. Dwie rzeczy mogą pójść nie tak: zamykający trafia na pusty stos albo na końcu coś zostaje na stosie. Sprawdź oba przypadki.
Pokaż rozwiązanie
nawiasy.cpp
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;

    stack<char> st;

    for (char c : s) {
        if (c == '(') {
            st.push(c);
        } else {
            if (st.empty()) {          // zamykajacy bez pary
                cout << "NIE";
                return 0;
            }
            st.pop();
        }
    }

    // cos zostalo niezamkniete?
    if (st.empty()) cout << "TAK";
    else            cout << "NIE";

    return 0;
}
Łatwe Historia przeglądarki
Wczytuj polecenia: IDZ adres otwiera stronę, WSTECZ wraca do poprzedniej i ją wypisuje, GDZIE wypisuje aktualną stronę. Dane kończy KONIEC.
Jak to ugryźć: Stos idealnie modeluje przycisk „wstecz” — ostatnia odwiedzona strona wychodzi pierwsza. Pamiętaj o zabezpieczeniu, gdy ktoś wciśnie WSTECZ przy pustej historii.
Pokaż rozwiązanie
historia.cpp
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    stack<string> historia;
    string polecenie;

    while (cin >> polecenie && polecenie != "KONIEC") {
        if (polecenie == "IDZ") {
            string adres;
            cin >> adres;
            historia.push(adres);
        }
        else if (polecenie == "WSTECZ") {
            if (historia.empty()) {
                cout << "brak historii\n";
            } else {
                historia.pop();
                if (historia.empty()) cout << "pusto\n";
                else                  cout << historia.top() << "\n";
            }
        }
        else if (polecenie == "GDZIE") {
            if (historia.empty()) cout << "pusto\n";
            else                  cout << historia.top() << "\n";
        }
    }

    return 0;
}
Średnie Nawiasy trzech rodzajów
To samo co wcześniej, ale w napisie mogą wystąpić trzy rodzaje nawiasów: (), [] i {}. Sprawdź, czy są poprawnie zagnieżdżone — ([)] jest błędne.
Jak to ugryźć: Teraz nie wystarczy liczyć — trzeba pamiętać, co położyłeś na stos. Przy zamykającym nawiasie zdejmij wierzch i sprawdź, czy pasuje do pary. Najprościej napisać małą funkcję zwracającą pasujący nawias otwierający.
Pokaż rozwiązanie
nawiasy3.cpp
#include <iostream>
#include <stack>
#include <string>
using namespace std;

char para(char c) {
    if (c == ')') return '(';
    if (c == ']') return '[';
    return '{';
}

int main() {
    string s;
    cin >> s;

    stack<char> st;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty() || st.top() != para(c)) {
                cout << "NIE";
                return 0;
            }
            st.pop();
        }
    }

    cout << (st.empty() ? "TAK" : "NIE");
    return 0;
}
Średnie Kalkulator ONP
Wyrażenie zapisane jest w odwrotnej notacji polskiej, np. 3 4 + 2 * oznacza (3 + 4) * 2. Wczytaj takie wyrażenie i policz jego wartość.
Jak to ugryźć: Liczby kładź na stos. Gdy trafisz na znak działania, zdejmij dwie liczby, wykonaj działanie i odłóż wynik z powrotem. Uwaga na kolejność przy odejmowaniu i dzieleniu — pierwsza zdjęta liczba jest tą drugą w działaniu.
Pokaż rozwiązanie
onp.cpp
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    stack<long long> s;
    string token;

    while (cin >> token) {
        if (token == "+" || token == "-" ||
            token == "*" || token == "/") {

            long long b = s.top(); s.pop();   // druga w dzialaniu!
            long long a = s.top(); s.pop();

            if      (token == "+") s.push(a + b);
            else if (token == "-") s.push(a - b);
            else if (token == "*") s.push(a * b);
            else                   s.push(a / b);
        }
        else {
            s.push(stoll(token));
        }
    }

    cout << s.top();
    return 0;
}
Trudne Najbliższy większy element
Wczytaj n liczb. Dla każdej wypisz pierwszą większą liczbę stojącą na prawo od niej, albo -1, jeśli takiej nie ma.
Jak to ugryźć: To sztuczka z sekcji piątej. Idź od końca tablicy. Przed zapisaniem odpowiedzi zdejmij ze stosu wszystkich kandydatów, którzy są mniejsi lub równi bieżącej liczbie — oni nigdy już nikomu nie posłużą. To, co zostanie na wierzchu, jest odpowiedzią.
Pokaż rozwiązanie
najblizszy_wiekszy.cpp
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];

    vector<int> wynik(n);
    stack<int> s;

    // idziemy OD KONCA
    for (int i = n - 1; i >= 0; i--) {
        // wyrzucamy kandydatow bez szans
        while (!s.empty() && s.top() <= t[i]) {
            s.pop();
        }

        wynik[i] = s.empty() ? -1 : s.top();
        s.push(t[i]);
    }

    for (int i = 0; i < n; i++) cout << wynik[i] << " ";
    return 0;
}

Częste błędy i dobre praktyki

🚫
pop() nic nie zwraca
pop() tylko usuwa element z wierzchu. Jeśli chcesz poznać jego wartość, najpierw wywołaj top(), a dopiero potem pop().
⚠️
Zawsze sprawdzaj empty()
Wywołanie top() lub pop() na pustym stosie to zachowanie niezdefiniowane i częsta przyczyna crasha programu.
🔍
Brak dostępu do środka
Stosu nie da się indeksować ani przeglądać pętlą for jak vector. Jedyny widoczny element to ten na wierzchu.
🪆
Odwrotna kolejność
Elementy schodzą ze stosu w kolejności odwrotnej do tej, w jakiej zostały dodane — to właśnie definicja LIFO.
🧩
Zastosowania
Stos świetnie sprawdza się przy sprawdzaniu nawiasów, cofaniu akcji (undo), obliczaniu wyrażeń ONP i przeszukiwaniu DFS.
📦
Nagłówek <stack>
Żeby korzystać ze stack, trzeba dołączyć nagłówek <stack> — bez niego kompilator nie rozpozna tego typu.

Gotowy na więcej?

Dołącz do T-Olimpians i trenuj z doświadczonymi mentorami. Zbuduj bazę, która prowadzi do finałów OI.