Stosy i kolejki - Organizacja ekwipunku

Witaj z powrotem, @name! Darwin tutaj z ostatnimi strukturami danych przed rekursją.

Wyobraź sobie organizowanie ekspedycji:

• Stos plecaka - pakujesz rzeczy jedna na drugiej. Aby wyciągnąć coś z dna, musisz najpierw wyjąć wszystko z góry (LIFO - Last In, First Out)
• Kolejka do wodopoju - zwierzęta ustawiają się w kolejce. Pierwsze zwierzę w kolejce jest pierwsze obsługiwane (FIFO - First In, First Out)

To są właśnie stosy (stacks) i kolejki (queues) - fundamentalne struktury danych!

Stack (Stos) - LIFO

Stack to struktura danych gdzie ostatni dodany element jest pierwszy do usunięcia (LIFO - Last In, First Out).

Analogia Safari: Stos talerzy - bierzesz talerz z góry (ostatni dodany), nie z dołu.

Operacje na stosie

| Operacja | Złożoność | Opis | |----------|-----------|------| | push(x) | O(1) | Dodaj element na szczyt | | pop() | O(1) | Usuń i zwróć element ze szczytu | | peek() / top() | O(1) | Zobacz element na szczycie (bez usuwania) | | is_empty() | O(1) | Sprawdź czy stos jest pusty | | size() | O(1) | Zwróć liczbę elementów |

Implementacja stosu w Pythonie

1# Sposób 1: Lista Pythona (najprostsze!)
2class Stack:
3    """Implementacja stosu używając listy"""
4
5    def __init__(self):
6        self.items = []
7
8    def push(self, item):
9        """Dodaj element na szczyt - O(1)"""
10        self.items.append(item)
11
12    def pop(self):
13        """Usuń i zwróć element ze szczytu - O(1)"""
14        if self.is_empty():
15            raise IndexError("Stack jest pusty!")
16        return self.items.pop()
17
18    def peek(self):
19        """Zobacz element na szczycie - O(1)"""
20        if self.is_empty():
21            raise IndexError("Stack jest pusty!")
22        return self.items[-1]
23
24    def is_empty(self):
25        """Sprawdź czy stos jest pusty - O(1)"""
26        return len(self.items) == 0
27
28    def size(self):
29        """Zwróć liczbę elementów - O(1)"""
30        return len(self.items)
31
32    def __str__(self):
33        """String representation"""
34        return f"Stack({self.items})"
35
36# Przykład użycia
37equipment_stack = Stack()
38equipment_stack.push("Namiot")
39equipment_stack.push("Śpiwór")
40equipment_stack.push("Latarka")
41equipment_stack.push("Mapa")
42
43print(equipment_stack)  # Stack(['Namiot', 'Śpiwór', 'Latarka', 'Mapa'])
44print(f"Szczyt: {equipment_stack.peek()}")  # Mapa (ostatni dodany)
45print(f"Wyciągam: {equipment_stack.pop()}")  # Mapa
46print(f"Teraz szczyt: {equipment_stack.peek()}")  # Latarka
47print(f"Rozmiar: {equipment_stack.size()}")  # 3

Safari przykład - Śledzenie ścieżki eksploracji:

1def track_exploration_path():
2    """Śledź ścieżkę ekspedycji używając stosu"""
3    path = Stack()
4
5    # Eksploruj dżunglę
6    path.push("Obóz Bazowy")
7    print(f"Wchodzę do: Obóz Bazowy")
8
9    path.push("Las Północny")
10    print(f"Wchodzę do: Las Północny")
11
12    path.push("Rzeka")
13    print(f"Wchodzę do: Rzeka")
14
15    # Wracamy tą samą drogą (cofamy się)
16    print("\nWracam tą samą ścieżką:")
17    while not path.is_empty():
18        location = path.pop()
19        print(f"Wychodzę z: {location}")
20
21# Wyjście:
22# Wchodzę do: Obóz Bazowy
23# Wchodzę do: Las Północny
24# Wchodzę do: Rzeka
25# Wracam tą samą ścieżką:
26# Wychodzę z: Rzeka
27# Wychodzę z: Las Północny
28# Wychodzę z: Obóz Bazowy

Zastosowania stosu

1. Undo/Redo w edytorach - każda akcja na stosie
2. Historia przeglądarki - przycisk "Wstecz"
3. Call stack - wywołania funkcji w programie
4. Parsowanie wyrażeń - sprawdzanie nawiasów, notacja ONP
5. DFS (Depth-First Search) - algorytm przeszukiwania
6. Backtracking - cofanie się w algorytmach

Przykład - Sprawdzanie zbalansowanych nawiasów

1def is_balanced(expression):
2    """
3    Sprawdź czy nawiasy są zbalansowane
4    Przykład: "({[]})" → True, "({[}])" → False
5    """
6    stack = Stack()
7    pairs = {')': '(', ']': '[', '}': '{'}
8
9    for char in expression:
10        if char in '([{':
11            # Otwierający nawias - dodaj na stos
12            stack.push(char)
13        elif char in ')]}':
14            # Zamykający nawias - sprawdź czy pasuje
15            if stack.is_empty():
16                return False  # Brak otwierającego
17            if stack.pop() != pairs[char]:
18                return False  # Nie pasuje
19            # Pasuje - kontynuuj
20
21    # Stack powinien być pusty na końcu
22    return stack.is_empty()
23
24# Testy
25print(is_balanced("({[]})"))  # True
26print(is_balanced("({[}])"))  # False
27print(is_balanced("((()))"))  # True
28print(is_balanced("(()"))     # False
29
30# Safari przykład
31code = "species = {name: 'Python', data: [1, 2, 3]}"
32print(f"Kod: {code}")
33print(f"Zbalansowany: {is_balanced(code)}")  # True

Queue (Kolejka) - FIFO

Queue to struktura danych gdzie pierwszy dodany element jest pierwszy do usunięcia (FIFO - First In, First Out).

Analogia Safari: Kolejka zwierząt do wodopoju - pierwsze w kolejce jest pierwsze napojone.

Operacje na kolejce

| Operacja | Złożoność | Opis | |----------|-----------|------| | enqueue(x) | O(1) | Dodaj element na koniec | | dequeue() | O(1) | Usuń i zwróć element z przodu | | front() / peek() | O(1) | Zobacz element z przodu | | is_empty() | O(1) | Sprawdź czy kolejka jest pusta | | size() | O(1) | Zwróć liczbę elementów |

Implementacja kolejki w Pythonie

1from collections import deque
2
3class Queue:
4    """Implementacja kolejki używając deque"""
5
6    def __init__(self):
7        # deque = double-ended queue - O(1) operacje z obu stron!
8        self.items = deque()
9
10    def enqueue(self, item):
11        """Dodaj element na koniec - O(1)"""
12        self.items.append(item)
13
14    def dequeue(self):
15        """Usuń i zwróć element z przodu - O(1)"""
16        if self.is_empty():
17            raise IndexError("Queue jest pusta!")
18        return self.items.popleft()  # popleft() z deque = O(1)!
19
20    def front(self):
21        """Zobacz element z przodu - O(1)"""
22        if self.is_empty():
23            raise IndexError("Queue jest pusta!")
24        return self.items[0]
25
26    def is_empty(self):
27        """Sprawdź czy kolejka jest pusta - O(1)"""
28        return len(self.items) == 0
29
30    def size(self):
31        """Zwróć liczbę elementów - O(1)"""
32        return len(self.items)
33
34    def __str__(self):
35        """String representation"""
36        return f"Queue({list(self.items)})"
37
38# Przykład użycia
39species_queue = Queue()
40species_queue.enqueue("Python")
41species_queue.enqueue("Leo")
42species_queue.enqueue("Elephas")
43
44print(species_queue)  # Queue(['Python', 'Leo', 'Elephas'])
45print(f"Pierwszy: {species_queue.front()}")  # Python
46print(f"Obsługuję: {species_queue.dequeue()}")  # Python (pierwszy dodany)
47print(f"Teraz pierwszy: {species_queue.front()}")  # Leo

UWAGA: Nie używaj listy Pythona z

pop(0)

deque

1# ❌ ŹLE - pop(0) to O(n)
2queue = []
3queue.append(1)  # O(1)
4queue.pop(0)     # O(n) - musi przesunąć wszystkie elementy!
5
6# ✅ DOBRZE - deque z popleft()
7from collections import deque
8queue = deque()
9queue.append(1)   # O(1)
10queue.popleft()   # O(1) - zoptymalizowane!

Zastosowania kolejki

1. BFS (Breadth-First Search) - algorytm przeszukiwania
2. Print queue - kolejka zadań do drukowania
3. Task scheduling - kolejkowanie zadań
4. Buffering - buforowanie danych (np. strumień wideo)
5. Simulations - symulacje (np. kolejki w sklepie)

Przykład - Symulacja systemu obsługi odkryć

1def process_discoveries():
2    """Symulacja obsługi odkryć w kolejności zgłoszenia"""
3    discovery_queue = Queue()
4
5    # Zgłoszenia odkryć
6    print("=== ZGŁOSZENIA ODKRYĆ ===")
7    discoveries = ["Python regius", "Panthera leo", "Gorilla gorilla", "Elephas maximus"]
8    for species in discoveries:
9        discovery_queue.enqueue(species)
10        print(f"Zgłoszono: {species}")
11
12    print(f"\nW kolejce: {discovery_queue.size()} odkryć\n")
13
14    # Przetwarzanie w kolejności FIFO
15    print("=== PRZETWARZANIE ===")
16    while not discovery_queue.is_empty():
17        current = discovery_queue.dequeue()
18        print(f"Katalogowanie: {current}")
19        # Symulacja przetwarzania
20        import time
21        time.sleep(0.5)
22
23    print("\n✓ Wszystkie odkrycia skatalogowane!")
24
25# Wynik:
26# === ZGŁOSZENIA ODKRYĆ ===
27# Zgłoszono: Python regius
28# Zgłoszono: Panthera leo
29# Zgłoszono: Gorilla gorilla
30# Zgłoszono: Elephas maximus
31#
32# W kolejce: 4 odkryć
33#
34# === PRZETWARZANIE ===
35# Katalogowanie: Python regius (pierwszy zgłoszony)
36# Katalogowanie: Panthera leo
37# Katalogowanie: Gorilla gorilla
38# Katalogowanie: Elephas maximus
39#
40# ✓ Wszystkie odkrycia skatalogowane!

Deque (Double-Ended Queue)

Deque (czyt. "dek") to kolejka z obu końców - możesz dodawać i usuwać z przodu i z tyłu!

1from collections import deque
2
3# Stwórz deque
4dq = deque([1, 2, 3])
5
6# Operacje z prawej strony (jak lista)
7dq.append(4)        # [1, 2, 3, 4]
8dq.pop()            # 4, pozostaje [1, 2, 3]
9
10# Operacje z lewej strony (unikalne dla deque!)
11dq.appendleft(0)    # [0, 1, 2, 3]
12dq.popleft()        # 0, pozostaje [1, 2, 3]
13
14# Inne operacje
15dq.extend([4, 5])           # [1, 2, 3, 4, 5]
16dq.extendleft([0, -1])      # [-1, 0, 1, 2, 3, 4, 5]
17dq.rotate(2)                # [4, 5, -1, 0, 1, 2, 3] (obrót w prawo)

Safari przykład - Recent discoveries tracker

1class RecentDiscoveriesTracker:
2    """Śledź ostatnie N odkryć"""
3
4    def __init__(self, max_size=5):
5        self.discoveries = deque(maxlen=max_size)  # Automatyczne usuwanie starych!
6
7    def add_discovery(self, species):
8        """Dodaj odkrycie (automatycznie usuwa najstarsze jeśli przekroczone max)"""
9        self.discoveries.append(species)
10
11    def get_recent(self):
12        """Zwróć ostatnie odkrycia (najnowsze najpierw)"""
13        return list(reversed(self.discoveries))
14
15    def __str__(self):
16        return f"Ostatnie {len(self.discoveries)} odkryć: {list(self.discoveries)}"
17
18# Użycie
19tracker = RecentDiscoveriesTracker(max_size=3)
20tracker.add_discovery("Python")
21tracker.add_discovery("Leo")
22tracker.add_discovery("Elephas")
23print(tracker)  # ['Python', 'Leo', 'Elephas']
24
25tracker.add_discovery("Gorilla")  # Przekroczy max - usuwa Python!
26print(tracker)  # ['Leo', 'Elephas', 'Gorilla']
27
28print(f"Najnowsze najpierw: {tracker.get_recent()}")
29# ['Gorilla', 'Elephas', 'Leo']

Priority Queue (Kolejka priorytetowa)

Priority Queue to kolejka gdzie elementy są obsługiwane według priorytetu, nie kolejności dodania.

1import heapq
2
3class PriorityQueue:
4    """Kolejka priorytetowa (mniejszy priorytet = wyższy priorytet)"""
5
6    def __init__(self):
7        self.heap = []
8        self.counter = 0  # Dla zachowania kolejności przy równych priorytetach
9
10    def enqueue(self, item, priority):
11        """Dodaj element z priorytetem - O(log n)"""
12        # Heapq używa min-heap (najmniejszy na górze)
13        # Dodajemy counter aby zachować kolejność FIFO dla równych priorytetów
14        heapq.heappush(self.heap, (priority, self.counter, item))
15        self.counter += 1
16
17    def dequeue(self):
18        """Usuń i zwróć element z najwyższym priorytetem - O(log n)"""
19        if self.is_empty():
20            raise IndexError("PriorityQueue jest pusta!")
21        priority, _, item = heapq.heappop(self.heap)
22        return item
23
24    def is_empty(self):
25        """Sprawdź czy pusta - O(1)"""
26        return len(self.heap) == 0
27
28    def size(self):
29        """Zwróć rozmiar - O(1)"""
30        return len(self.heap)
31
32# Safari przykład - Priorytetyzacja badania gatunków
33pq = PriorityQueue()
34
35# Dodaj gatunki z priorytetem (1 = najwyższy, 5 = najniższy)
36pq.enqueue("Crocodylus niloticus", priority=1)  # Niebezpieczny - priorytet!
37pq.enqueue("Python regius", priority=3)          # Normalny priorytet
38pq.enqueue("Panthera leo", priority=1)           # Niebezpieczny - priorytet!
39pq.enqueue("Gorilla gorilla", priority=2)        # Średni priorytet
40pq.enqueue("Elephas maximus", priority=3)        # Normalny priorytet
41
42print("Kolejność badania (priorytet):")
43while not pq.is_empty():
44    species = pq.dequeue()
45    print(f"  Badanie: {species}")
46
47# Wynik:
48# Badanie: Crocodylus niloticus (priorytet 1, pierwszy dodany)
49# Badanie: Panthera leo (priorytet 1, drugi dodany)
50# Badanie: Gorilla gorilla (priorytet 2)
51# Badanie: Python regius (priorytet 3, pierwszy dodany)
52# Badanie: Elephas maximus (priorytet 3, drugi dodany)

Porównanie Stack vs Queue vs Deque

| Struktura | Dodawanie | Usuwanie | Złożoność | Zastosowanie | |-----------|-----------|----------|-----------|--------------| | Stack | push (góra) | pop (góra) | O(1) | Undo, Call stack, DFS | | Queue | enqueue (tył) | dequeue (przód) | O(1) | BFS, Scheduling, Buffering | | Deque | append/appendleft | pop/popleft | O(1) | Sliding window, Recent history | | Priority Queue | enqueue | dequeue (min) | O(log n) | Dijkstra, Task scheduling |

Praktyczny przykład - Expedition Planner

1class ExpeditionPlanner:
2    """System planowania ekspedycji używający różnych struktur danych"""
3
4    def __init__(self):
5        self.path_history = Stack()        # Historia ścieżki (do backtrackingu)
6        self.task_queue = Queue()          # Kolejka zadań do wykonania
7        self.recent_discoveries = deque(maxlen=10)  # 10 ostatnich odkryć
8        self.priority_tasks = PriorityQueue()  # Zadania priorytetowe
9
10    def enter_location(self, location):
11        """Wejdź do lokacji (zapisz w historii)"""
12        self.path_history.push(location)
13        print(f"➡️  Wchodzę do: {location}")
14
15    def backtrack(self):
16        """Wróć do poprzedniej lokacji"""
17        if self.path_history.is_empty():
18            print("⚠️  Już w obozie bazowym!")
19            return None
20        location = self.path_history.pop()
21        print(f"⬅️  Wychodzę z: {location}")
22        return location
23
24    def add_task(self, task, priority=None):
25        """Dodaj zadanie (normalne lub priorytetowe)"""
26        if priority is not None:
27            self.priority_tasks.enqueue(task, priority)
28            print(f"📌 Priorytetowe zadanie: {task} (priorytet {priority})")
29        else:
30            self.task_queue.enqueue(task)
31            print(f"📋 Zadanie: {task}")
32
33    def process_next_task(self):
34        """Przetwórz następne zadanie (priorytet najpierw)"""
35        if not self.priority_tasks.is_empty():
36            task = self.priority_tasks.dequeue()
37            print(f"⚡ Wykonuję priorytetowe: {task}")
38            return task
39        elif not self.task_queue.is_empty():
40            task = self.task_queue.dequeue()
41            print(f"✓ Wykonuję: {task}")
42            return task
43        else:
44            print("✓ Wszystkie zadania wykonane!")
45            return None
46
47    def record_discovery(self, species):
48        """Zapisz odkrycie"""
49        self.recent_discoveries.append(species)
50        print(f"🔬 Odkryto: {species}")
51
52    def show_recent_discoveries(self, n=5):
53        """Pokaż ostatnie N odkryć"""
54        recent = list(self.recent_discoveries)[-n:]
55        print(f"\n📊 Ostatnie {len(recent)} odkryć:")
56        for i, species in enumerate(reversed(recent), 1):
57            print(f"  {i}. {species}")
58
59# Użycie
60planner = ExpeditionPlanner()
61
62# Eksploracja
63planner.enter_location("Las Północny")
64planner.enter_location("Rzeka")
65planner.enter_location("Wodospad")
66
67# Odkrycia
68planner.record_discovery("Python regius")
69planner.record_discovery("Panthera leo")
70
71# Zadania
72planner.add_task("Zbadaj próbki wody")
73planner.add_task("PILNE: Napraw sprzęt komunikacyjny", priority=1)
74planner.add_task("Stwórz mapę terenu")
75
76# Przetwarzanie zadań
77planner.process_next_task()  # PILNE najpierw!
78planner.process_next_task()
79planner.process_next_task()
80
81# Backtracking
82planner.backtrack()
83planner.backtrack()
84planner.backtrack()
85
86# Podsumowanie
87planner.show_recent_discoveries()

Zadanie praktyczne

Stwórz "Safari Command Center":

1. Stack - Historia poleceń (możliwość undo)
2. Queue - Kolejka zadań badawczych
3. Priority Queue - Alerty i zadania priorytetowe
4. Deque - Ostatnie 5 lokalizacji zespołu

Podsumowanie

W tej lekcji nauczyłeś/aś się:

• ✅ Stack (LIFO) - ostatni wchodzi, pierwszy wychodzi
• ✅ Queue (FIFO) - pierwszy wchodzi, pierwszy wychodzi
• ✅ Deque - dodawanie/usuwanie z obu końców
• ✅ Priority Queue - obsługa według priorytetu
• ✅ Implementacji w Pythonie (lista, deque, heapq)
• ✅ Zastosowań każdej struktury
• ✅ Złożoności operacji
• ✅ Praktycznych przykładów

Checkpoint

Przed przejściem dalej:

• [ ] Rozumiesz różnicę między LIFO a FIFO
• [ ] Potrafisz zaimplementować Stack i Queue
• [ ] Znasz zastosowania każdej struktury
• [ ] Rozumiesz dlaczego używać deque zamiast list dla Queue
• [ ] Wiesz kiedy użyć Priority Queue
• [ ] Potrafisz wybrać odpowiednią strukturę dla danego problemu

Kluczowe: Stack dla backtrackingu i undo, Queue dla BFS i scheduling, Deque dla sliding window!

W następnej i ostatniej lekcji tego modułu Darwin wprowadzi Cię w rekursję - funkcje wywołujące same siebie! 🔄🌀