Stos i kolejka w Pythonie — struktury proste i użyteczne

Po co się tego uczymy?

Historia stron w przeglądarce, kolejka do drukarki, cofanie ostatniego ruchu w grze — wszystko to działa dzięki DWÓM prostym strukturom danych: stosowi i kolejce. To fundament, na którym zbudowane są bardziej złożone struktury (drzewa, grafy) oraz algorytmy przeszukiwania (BFS/DFS z kolejnej lekcji).

Teoria

Tablica statyczna vs struktura dynamiczna — tablica statyczna ma OKREŚLONY rozmiar, którego nie da się łatwo zmienić (jak pudełko na 10 miejsc — jedenasty przedmiot wymaga większego pudełka i przepakowania). Struktura dynamiczna (jak lista w Pythonie) potrafi ZMIENIAĆ rozmiar w trakcie działania programu — możesz dokładać elementy, kiedy chcesz, bez przepakowywania.

Lista to najprostsza struktura dynamiczna — zbiór elementów w kolejności, do którego można DODAĆ nowy element (append()), USUNĄĆ ostatni (pop()), WSTAWIĆ coś w wybrane miejsce (insert()). Można manipulować danymi SWOBODNIE — w dowolnym miejscu.

Stos (stack) działa jak wieża talerzy w stołówce — kładziesz jeden na drugim, ale żeby wziąć talerz, ZDEJMUJESZ ten z góry (nie sięgniesz po środkowy, dopóki nie zdejmiesz wszystkich powyżej). Zasada działania to LIFO (Last In, First Out) — ostatni element, który wszedł, WYCHODZI PIERWSZY. W Pythonie realizuje się to zwykłą listą: append() dokłada na wierzch, pop() zdejmuje z wierzchu.

Zastosowania stosu: historia stron w przeglądarce (przycisk "Wstecz"), cofanie ostatniego ruchu w grze (undo), sprawdzanie poprawności nawiasów w wyrażeniach matematycznych.

Kolejka (queue) działa jak kolejka w sklepie — kto pierwszy stanął, ten pierwszy wychodzi; nie możesz się przepchnąć na początek. Zasada to FIFO (First In, First Out) — pierwszy element, który wszedł, wychodzi PIERWSZY. W Pythonie najlepiej realizować kolejkę przez collections.deque (nie zwykłą listę — usuwanie z początku listy jest wolne): append() dokłada na koniec, popleft() zdejmuje z początku.

Zastosowania kolejki: kolejka klientów do obsługi (drukarka, sklep), kolejka zadań w systemie operacyjnym, kolejka graczy w grach online.

Podsumowanie różnic:

Struktura	Zasada	Sposób działania
Lista	Dodajesz, usuwasz, wstawiasz gdzie chcesz	swobodne manipulowanie danymi
Stos	Ostatni wchodzi, pierwszy wychodzi (LIFO)	`append()` i `pop()`
Kolejka	Pierwszy wchodzi, pierwszy wychodzi (FIFO)	`append()` i `popleft()`

Schemat

LISTA:
[A] – [B] – [C]     ← można dodać lub wyjąć w DOWOLNYM miejscu

STOS (LIFO):
↑ Angielski     ← zdejmujesz TYLKO z góry
↑ Informatyka
↑ Matematyka

KOLEJKA (FIFO):
Ola → Tomek → Kasia     ← pierwszy wchodzi, pierwszy wychodzi
 ↑ obsłużony jako pierwszy (popleft())

Przykład z życia

Przycisk "Wstecz" w przeglądarce internetowej to podręcznikowy przykład stosu — każda odwiedzona strona "kładzie się" na stos, a "Wstecz" zdejmuje TYLKO OSTATNIĄ. Kolejka do drukarki w biurze to z kolei czysta kolejka FIFO — dokument wysłany jako pierwszy, drukuje się jako pierwszy, niezależnie od tego, ile innych dokumentów wysłano później.

lista_i_stos.py

# LISTA - swobodne dodawanie, usuwanie, wstawianie
lista = []  # pusta lista

lista.append("mleko")
lista.append("chleb")
lista.append("masło")

print("Lista zakupów:", lista)

lista.pop()  # usuwa ostatni element
print("Po usunięciu:", lista)

lista.insert(1, "ser")  # wstawiamy w środek
print("Po wstawieniu sera:", lista)
# Wynik:
# Lista zakupów: ['mleko', 'chleb', 'masło']
# Po usunięciu: ['mleko', 'chleb']
# Po wstawieniu sera: ['mleko', 'ser', 'chleb']


# STOS (LIFO) - append() dokłada na wierzch, pop() zdejmuje z wierzchu
stos = []

stos.append("Matematyka")
stos.append("Informatyka")
stos.append("Angielski")

print("Stos:", stos)

ostatni = stos.pop()
print("Zdejmuję ze stosu:", ostatni)
print("Po zdjęciu:", stos)
# Wynik:
# Stos: ['Matematyka', 'Informatyka', 'Angielski']
# Zdejmuję ze stosu: Angielski
# Po zdjęciu: ['Matematyka', 'Informatyka']

kolejka.py

# KOLEJKA (FIFO) - collections.deque, append() na koniec, popleft() z początku
from collections import deque

kolejka = deque()

kolejka.append("Ola")
kolejka.append("Tomek")
kolejka.append("Kasia")

print("Kolejka:", kolejka)

pierwszy = kolejka.popleft()
print("Obsłużono:", pierwszy)
print("Zostało:", kolejka)
# Wynik:
# Kolejka: deque(['Ola', 'Tomek', 'Kasia'])
# Obsłużono: Ola
# Zostało: deque(['Tomek', 'Kasia'])

Komentarz i wyjaśnienie kodu

W przykładzie stosu stos.pop() BEZ argumentu usuwa i zwraca OSTATNI element listy — to naturalna realizacja LIFO, bo Python listy przechowują elementy w kolejności dodawania, a pop() domyślnie działa na końcu.

collections.deque ("double-ended queue") jest użyty do kolejki zamiast zwykłej listy, bo lista.pop(0) (usuwanie PIERWSZEGO elementu zwykłej listy) jest WOLNE — wymaga przesunięcia WSZYSTKICH pozostałych elementów o jedną pozycję. deque jest zoptymalizowany do szybkiego dodawania/usuwania z OBU końców.

Ćwiczenie samodzielne

Uruchom oba przykłady (stos i kolejka) i prześledź, w jakiej kolejności elementy są dodawane i usuwane. Dodaj do stosu 5 przedmiotów i zdejmij je wszystkie — w jakiej kolejności się pojawiają?

Zadania do pracy własnej

Napisz program z listą zakupów, który pozwala: dodawać produkty do listy, usuwać ostatni, wyświetlać całą listę. Program kończy działanie, gdy użytkownik wpisze "koniec".
Zaimplementuj stos, do którego można dodawać tytuły książek (push = append()) i zdejmować je (pop). Po serii operacji wypisz, które książki pozostały na stosie.
Utwórz kolejkę pacjentów (każdy wpisuje swoje imię), a lekarz obsługuje ich w kolejności zgłoszeń (popleft()). Dla chętnych: napisz program sprawdzający, czy nawiasy w wyrażeniu matematycznym (np. "(2+3)*(4-1)") są poprawnie dopasowane — użyj stosu do śledzenia otwierających nawiasów (przy każdym nawiasie otwierającym odkładaj na stos, przy zamykającym zdejmuj — jeśli stos jest pusty w momencie napotkania nawiasu zamykającego albo zostają elementy na końcu, wyrażenie jest niepoprawne).

Typowe błędy

Używanie zwykłej listy jako kolejki (lista.pop(0)) zamiast collections.deque — działa poprawnie, ale jest ZNACZNIE wolniejsze dla dużych kolejek, bo każde usunięcie z początku przesuwa wszystkie pozostałe elementy.

Mylenie pop() (stos, usuwa OSTATNI) z popleft() (kolejka, usuwa PIERWSZY) — użycie niewłaściwej metody odwraca kolejność przetwarzania danych.

Próba zdjęcia elementu z pustego stosu lub kolejki — pop()/popleft() na pustej strukturze rzuci błąd (IndexError); w prawdziwych programach trzeba wcześniej sprawdzić, czy struktura nie jest pusta.

Nawiązanie do egzaminu zawodowego

Stos i kolejka to fundament, na którym oparte są algorytmy przeszukiwania grafów z kolejnej lekcji — DFS (przeszukiwanie w głąb) naturalnie korzysta ze STOSU (albo rekurencji, co jest równoważne), a BFS (przeszukiwanie wszerz) korzysta z KOLEJKI. Zrozumienie tych dwóch prostych struktur to klucz do zrozumienia znacznie bardziej złożonych algorytmów na grafach.