Stos (LIFO) - implementacja i przykłady użycia
1. Czym jest stos?
Stos (stack) to abstrakcyjna struktura danych działająca na zasadzie LIFO (Last In, First Out) – ostatni element wchodzi, pierwszy wychodzi.
Analogia ze świata rzeczywistego:
Wyobraź sobie stos talerzy: - Kładziesz nowy talerz na górze - Bierzesz talerz z góry - Nie możesz wyjąć talerza ze środka lub od dołu (bez przewracania stosu)
Wizualizacja:
┌─────┐
│ 9 │ ← TOP (szczyt stosu)
├─────┤
│ 5 │
├─────┤
│ 3 │
├─────┤
│ 1 │
└─────┘
2. Podstawowe operacje
Stos ma trzy główne operacje:
| Operacja | Opis | Złożoność |
|---|---|---|
| push(x) | Dodaje element na szczyt stosu | O(1) |
| pop() | Usuwa i zwraca element ze szczytu | O(1) |
| peek() | Zwraca element ze szczytu (bez usuwania) | O(1) |
| is_empty() | Sprawdza, czy stos jest pusty | O(1) |
| size() | Zwraca liczbę elementów | O(1) |
3. Implementacja z użyciem listy pythonowej
Użycie:
4. Implementacja z użyciem listy jednokierunkowej
Zalety listy jednokierunkowej: - Wszystkie operacje O(1) - Dynamiczny rozmiar - Brak przepełnienia (jak w tablicach stałych)
5. Porównanie implementacji
5.1. Lista pythonowa vs lista jednokierunkowa
| Aspekt | Lista pythonowa | Lista jednokierunkowa |
|---|---|---|
| Prostota | ⭐⭐⭐ | ⭐⭐ |
| Wydajność | ⭐⭐⭐ | ⭐⭐⭐ |
| Zużycie pamięci | ⭐⭐ | ⭐⭐⭐ (więcej) |
| Realokacja | Tak (rzadko) | Nie |
| Cache-friendly | Tak | Nie |
Rekomendacja: Dla większości przypadków używaj listy pythonowej – jest prostsza i szybsza.
6. Praktyczne zastosowania stosu
6.1. Odwracanie łańcucha znaków
6.2. Sprawdzanie poprawności nawiasów
6.3. Ewaluacja wyrażeń w notacji ONP (RPN)
ONP (Odwrotna Notacja Polska) / RPN (Reverse Polish Notation):
- Zamiast: 3 + 4
- Piszemy: 3 4 +
6.4. Konwersja notacji infiksowej na ONP (algorytm shunting yard)
6.5. Historia przeglądarki (Back button)
6.6. Undo/Redo w edytorze tekstu
6.7. Wywołania funkcji (call stack)
Wynik:
→ Wywołanie factorial(4)
→ Wywołanie factorial(3)
→ Wywołanie factorial(2)
→ Wywołanie factorial(1)
← Zwracam 1
← Zwracam 2
← Zwracam 6
← Zwracam 24
Stos wywołań:
factorial(4)
factorial(3)
factorial(2)
factorial(1) ← szczyt stosu
7. Parsowanie HTML/XML (tag matching)
8. Algorytmy wykorzystujące stos
8.1. DFS (Depth-First Search) – przeszukiwanie grafu
8.2. Backtracking – generowanie permutacji
9. Optymalizacje i warianty
9.1. Stos z min/max – O(1)
9.2. Stos z ograniczoną pojemnością
10. Złożoność czasowa i pamięciowa
Złożoność czasowa:
| Operacja | Złożoność |
|---|---|
push(x) |
O(1) |
pop() |
O(1) |
peek() |
O(1) |
is_empty() |
O(1) |
size() |
O(1) |
Złożoność pamięciowa:
- O(n) – gdzie n to liczba elementów na stosie
11. Typowe błędy
Błąd 1: Pop z pustego stosu
Błąd 2: Modyfikacja podczas iteracji
12. Stos w Pythonie (biblioteka standardowa)
Python nie ma dedykowanej klasy Stack, ale możesz użyć:
12.1. Lista pythonowa
12.2. collections.deque
Rekomendacja: Używaj list dla prostych przypadków, deque dla wydajności.
13. Podsumowanie
Stos to fundamentalna struktura danych LIFO:
- Wszystkie operacje O(1)
- Prosta implementacja
- Szeroko wykorzystywana w algorytmach
- Naturalna dla rekurencji i backtrackingu
Kluczowe zastosowania:
- Sprawdzanie nawiasów
- Ewaluacja wyrażeń (ONP, kalkulator)
- DFS (przeszukiwanie grafu)
- Undo/Redo
- Backtracking
- Call stack (wywołania funkcji)
Kiedy używać stosu:
- LIFO (ostatni wchodzi, pierwszy wychodzi)
- Backtracking (przeszukiwanie z nawrotami)
- Parsowanie (nawiasy, tagi)
- Ewaluacja wyrażeń
- Historia operacji (undo)
Co dalej warto poznać:
- Kolejka (FIFO)
- Kolejka priorytetowa
- Deque (kolejka dwustronna)
- Zaawansowane algorytmy (DFS, backtracking)