Menu
Coddy logo textTech

Stos (stack)

Ostatnia aktualizacja

Stos to kolekcja z dokładnie jednym otwartym końcem. Wartość dodajesz, odkładając ją na szczyt (push), a usuwasz, zdejmując ten sam szczyt (pop), więc ostatnia wartość, która weszła, zawsze wychodzi pierwsza. To właśnie oznacza LIFO i to jest cała zasada: nie da się sięgnąć do środka bez zdjęcia najpierw tego, co leży wyżej. Naciśnij Odtwórz powyżej i zobacz, jak kolumna rośnie z każdym push i maleje od tego samego końca z każdym pop.

Całe sedno tkwi w tym ograniczeniu. Obie operacje dotykają tylko szczytu, więc każda z nich ma złożoność O(1) bez względu na to, jak wysoki jest stos, a ta przewidywalność sprawia, że stosy leżą u podstaw ogromnej części informatyki: stos wywołań, na którym działa rekurencja, historia cofania w edytorze, dopasowywanie nawiasów w parserze i jawny stos, który zamienia rekurencyjne przeszukiwanie w głąb w pętlę. Zmień koniec, z którego usuwasz, a dostaniesz kolejkę.

Złożoność czasowa i pamięciowa

Dla standardowego stosu opartego na tablicy lub liście wiązanej:

OperacjaZłożonośćUwagi
PushO(1)Zamortyzowane O(1) w tablicy dynamicznej, która co jakiś czas zmienia rozmiar.
PopO(1)Zawsze element ze szczytu, więc nie trzeba niczego przesuwać.
Peek (szczyt)O(1)Odczyt szczytu bez jego usuwania.
WyszukiwanieO(n)Stos nie służy do tego: trzeba zdejmować elementy aż do szukanego.
PamięćO(n)Jedno miejsce na każdą przechowywaną wartość.

Krok po kroku

KrokCo się dzieje
1Stos zaczyna pusty, a szczyt nie wskazuje na nic.
2Push zapisuje wartość na pozycji szczytu i przesuwa szczyt o jedno miejsce w górę.
3Każdy kolejny push ląduje bezpośrednio nad poprzednią wartością.
4Pop odczytuje wartość ze szczytu, a potem przesuwa szczyt o jedno miejsce w dół.
5Zwrócona wartość to zawsze ta, która została odłożona najpóźniej.
6Zdjęcie elementu z pustego stosu to błąd zwany niedopełnieniem stosu (stack underflow), dlatego prawdziwy kod najpierw sprawdza is_empty().

Przykład krok po kroku

Odkładamy 3, 7, 5, a potem opróżniamy stos:

OperacjaStos (od dołu do góry)Zwraca
push(3)[3]nic
push(7)[3, 7]nic
push(5)[3, 7, 5]nic
pop()[3, 7]5, najnowszą wartość
pop()[3]7
pop()[]3, najstarszą wartość, na końcu

Kiedy używać stosu

Używaj, gdyUnikaj, gdy
Potrzebujesz najpierw najnowszego elementu: cofanie, przycisk Wstecz, dopasowywanie nawiasówPotrzebujesz najpierw najstarszego elementu, do tego służy kolejka
Zamieniasz algorytm rekurencyjny na iteracyjnyMusisz przeszukiwać dane lub sięgać po indeksie do ich środka
Parsujesz zagnieżdżone struktury, takie jak wyrażenia, JSON lub HTMLWielu odbiorców potrzebuje dowolnego dostępu, wtedy lepiej sprawdzi się tablica lub mapa
Chcesz mieć gwarantowane wstawianie i usuwanie w O(1) bez równoważeniaDane muszą być posortowane, co zapewnia kopiec lub drzewo

Stack: kod

Przejrzysta, gotowa do uruchomienia implementacja algorytmu Stack w językach: Python, JavaScript, Java, C++, C. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.

Stack: kod (Python)

Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5    stack.append(value)6    print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10    value = stack.pop()11    print(f"pop  {value} -> {stack}")12
13print("empty:", len(stack) == 0)
Uruchom ten kod w edytorze Python online

Stos: najczęstsze pytania

Co oznacza LIFO?
Last in, first out, czyli ostatni na wejściu, pierwszy na wyjściu: wartość odłożona najpóźniej jest zdejmowana jako pierwsza. Typowy obraz to stos talerzy: bierzesz talerz, który właśnie trafił na górę, a nie ten na samym dole. Kolejka działa odwrotnie, według zasady FIFO.
Czym różni się stos od kolejki?
Tylko końcem, z którego usuwasz elementy. Obie struktury dodają na jednym końcu w O(1); stos usuwa z tego samego końca (LIFO), a kolejka z przeciwnego (FIFO). Cała reszta, łącznie z tabelą złożoności powyżej, jest identyczna.
Jakie są podstawowe operacje na stosie?
push dodaje wartość na szczyt, pop usuwa i zwraca wartość ze szczytu, peek (czasem top) odczytuje szczyt bez usuwania, a is_empty sprawdza, czy coś jeszcze zostało. Wszystkie cztery mają złożoność O(1).
Co to jest przepełnienie stosu (stack overflow)?
Próba odłożenia elementu na stos, na którym nie ma już miejsca. Najsłynniejszy przypadek to stos wywołań: każde wywołanie funkcji odkłada ramkę, więc rekurencja, która nigdy nie dochodzi do przypadku bazowego, odkłada kolejne ramki, aż przekroczy limit stosu środowiska uruchomieniowego i program się wysypie. Błąd lustrzany, czyli zdejmowanie z pustego stosu, to niedopełnienie stosu (stack underflow).
Jak implementuje się stos?
Na dwa popularne sposoby. Tablica dynamiczna odkłada i zdejmuje elementy na końcu, co daje zamortyzowane O(1) i dobrze współpracuje z pamięcią podręczną: tak działają list w Pythonie i ArrayDeque w Javie. Lista wiązana odkłada i zdejmuje na początku, co daje O(1) w najgorszym przypadku bez zmiany rozmiaru, ale kosztuje jeden wskaźnik na element. std::stack w C++ to adapter, który domyślnie działa na std::deque, czyli tablicy segmentowanej, i przyjmuje inny kontener, jeśli go przekażesz.
Gdzie w prawdziwych programach używa się stosów?
Stos wywołań obsługujący wywołania funkcji i rekurencję, historia cofania i ponawiania, nawigacja wstecz w przeglądarce, obliczanie wyrażeń i dopasowywanie nawiasów w parserach oraz jawny stos, który zamienia rekurencyjne przeszukiwanie w głąb w iteracyjną pętlę.
Ilustracja języków programowania w Coddy

Opanuj algorytmy z Coddy

ZACZNIJ