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:
| Operacja | Złożoność | Uwagi |
|---|---|---|
| Push | O(1) | Zamortyzowane O(1) w tablicy dynamicznej, która co jakiś czas zmienia rozmiar. |
| Pop | O(1) | Zawsze element ze szczytu, więc nie trzeba niczego przesuwać. |
| Peek (szczyt) | O(1) | Odczyt szczytu bez jego usuwania. |
| Wyszukiwanie | O(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
| Krok | Co się dzieje |
|---|---|
| 1 | Stos zaczyna pusty, a szczyt nie wskazuje na nic. |
| 2 | Push zapisuje wartość na pozycji szczytu i przesuwa szczyt o jedno miejsce w górę. |
| 3 | Każdy kolejny push ląduje bezpośrednio nad poprzednią wartością. |
| 4 | Pop odczytuje wartość ze szczytu, a potem przesuwa szczyt o jedno miejsce w dół. |
| 5 | Zwrócona wartość to zawsze ta, która została odłożona najpóźniej. |
| 6 | Zdję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:
| Operacja | Stos (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, gdy | Unikaj, gdy |
|---|---|
| Potrzebujesz najpierw najnowszego elementu: cofanie, przycisk Wstecz, dopasowywanie nawiasów | Potrzebujesz najpierw najstarszego elementu, do tego służy kolejka |
| Zamieniasz algorytm rekurencyjny na iteracyjny | Musisz przeszukiwać dane lub sięgać po indeksie do ich środka |
| Parsujesz zagnieżdżone struktury, takie jak wyrażenia, JSON lub HTML | Wielu 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żenia | Dane 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)
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)Stack: kod (JavaScript)
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Stack: kod (Java)
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}Stack: kod (C++)
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}Stack: kod (C)
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}Stos: najczęstsze pytania
Co oznacza LIFO?
Czym różni się stos od kolejki?
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)?
Jak implementuje się stos?
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.