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.
#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.
#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;
}
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.
while (!stosTalerzy.empty()) {
cout << stosTalerzy.top();
stosTalerzy.pop();
}
stack<char> s;
bool poprawne = true;
for (char znak : wyrazenie) {
if (znak == '(') s.push(znak);
else if (s.empty()) poprawne = false;
else s.pop();
}
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ć.
| Metoda | Co robi | Uwaga |
|---|---|---|
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ć.
| Zastosowanie | Na czym polega | Gdzie 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.
// 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.
n liczb, wrzuć je na stos i wypisz. Sprawdź, co się stało z kolejnością.top(), potem pop().Pokaż rozwiązanie
#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;
}
( i ) i sprawdź, czy nawiasy są poprawnie sparowane. Wypisz TAK albo NIE.Pokaż rozwiązanie
#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;
}
IDZ adres otwiera stronę, WSTECZ wraca do poprzedniej i ją wypisuje, GDZIE wypisuje aktualną stronę. Dane kończy KONIEC.WSTECZ przy pustej historii.Pokaż rozwiązanie
#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;
}
(), [] i {}. Sprawdź, czy są poprawnie zagnieżdżone — ([)] jest błędne.Pokaż rozwiązanie
#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;
}
3 4 + 2 * oznacza (3 + 4) * 2. Wczytaj takie wyrażenie i policz jego wartość.Pokaż rozwiązanie
#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;
}
n liczb. Dla każdej wypisz pierwszą większą liczbę stojącą na prawo od niej, albo -1, jeśli takiej nie ma.Pokaż rozwiązanie
#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;
}