Szybki quiz – przypomnienie poprzedniej lekcji

Pytanie 1. Co zostanie wyświetlone?

lst = ["a", "b", "c", "d", "e"]
print(lst[1:4])
print(lst[-2])

Pytanie 2. Ile elementów będzie miała lista po wykonaniu kodu?

lst = [1, 2, 3]
lst.append([4, 5])
print(len(lst))

Pytanie 3. Co zostanie wyświetlone?

lst = ["a", "b", "c", "d"]
x = lst.pop(1)
lst.remove("c")
print(x, lst)

Pytanie 4. Co wyświetli pierwsza linia print, a co się stanie przy drugiej?

osoba = {"name": "Kama", "age": 30}
print(osoba.get("city", "brak"))
print(osoba["city"])

Pytanie 5. Uczeń chciał utworzyć krotkę jednoelementową. Jaki typ wyświetli program i jak poprawić kod?

t = (5)
print(type(t))

Pytanie 6. Dlaczego ten kod nie zadziała i jak uzyskać zmianę pierwszego elementu?

animals = ("kot", "pies", "koń")
animals[0] = "ptak"

Pytanie 7. Co zostanie wyświetlone?

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print(A - B)
print(A & B)
print(set([1, 2, 2, 3, 3, 3]))

Stos (Stack)

Stos to struktura danych typu LIFO — „Last In, First Out”, czyli ostatni dodany element jest pierwszym, który zostanie usunięty.

To przykład „kontenera” (ang. container / collection) liniowego — czyli struktury przechowującej kilka elementów w kolejności i udostępniającej określone operacje.

Można to porównać do stosu talerzy lub książek — układamy jedno na drugim, a zdejmujemy tylko z góry.

Operacje typowe dla stosu to:

push(x) — dodać element x na wierzch stosu

pop() — usunąć i zwrócić element z wierzchu stosu

peek/top — zobaczyć (ale nie usuwać) element ze szczytu, lub top = stack[-1]

isEmpty — sprawdzić czy stos jest pusty,

size — liczba elementów.

stack = []          # pusty stos []
stack.append(1)     # teraz mamy 1 element [1]
stack.append(2)     # teraz dodajemy następny na koniec [1, 2]
print(stack)        # [1, 2]
top = stack.pop()   # pop → 2 zabieramy element z góry stosu
print(top)          # 2
print(stack)        # [1]

Kolejka (Queue)

Kolejka działa w modelu FIFO — „First In, First Out”, czyli pierwszy dodany element jest pierwszym, który zostanie usunięty.

W kolejce elementy są „na linii” — nowy element zawsze dołącza na koniec kolejki (tail, rear), a usuwamy zawsze z początku (head, front). Kolejka także jest kontenerem liniowym/sekwencyjnym, lecz z inną zasadą dostępu niż stos

Podstawowe operacje:

enqueue(x) — dodać element x na koniec kolejki

dequeue() — usunąć i zwrócić element z początku kolejki

peek/front — sprawdzić pierwszy element bez usuwania, isEmpty,

size — liczba elementów.

Chociaż można próbować używać listy jako kolejki (np. .pop(0) do zdejmowania elementu z przodu), to takie podejście jest nieefektywne — usuwanie z początku listy wymaga przesunięcia wszystkich pozostałych elementów.

Dlatego zaleca się użyć strukturę collections.deque. deque zapewnia szybkie (O(1)) operacje dodawania i usuwania na obu końcach, dzięki czemu działa wydajnie zarówno jako kolejka (FIFO), jak i — przy odpowiednim użyciu — jako stos (LIFO), to tzw. double-ended queue — czyli struktura, która pozwala operować na obu końcach: można dodawać i usuwać elementy zarówno z początku, jak i końca. Dzięki temu można ją traktować jako kolejkę, stos albo coś pomiędzy.

from collections import deque

queue = deque(["Alicja", "Bartek", "Celina"])
queue.append("Daniel")      # enqueue
first = queue.popleft()     # dequeue → "Alicja"
print(first)
print(queue)

PODSUMOWANIE

• Stos to struktura LIFO (Last In, First Out): ostatni dodany element jest usuwany jako pierwszy. Pracujemy tylko na jego szczycie.
• Kolejka to struktura FIFO (First In, First Out): pierwszy dodany element jest usuwany jako pierwszy. Dodajemy na koniec (tail), usuwamy z początku (head).
• Stos i kolejka to kontenery liniowe. Przechowują elementy w kolejności, ale różnią się zasadą dostępu.
• Stos w Pythonie budujemy na zwykłej liście: append() to push, pop() to usunięcie ze szczytu.
• Kolejkę budujemy na collections.deque: append() to enqueue, popleft() to dequeue.
• list.pop(0) działa jako dequeue, ale jest nieefektywne, bo wszystkie pozostałe elementy trzeba przesunąć. deque wykonuje operacje na obu końcach w czasie O(1).
• deque (double-ended queue) może pełnić rolę kolejki, a przy odpowiednim użyciu także stosu.
• Źródło błędów: pop() i popleft() zdejmują element z różnych końców. Pomylenie ich zamienia kolejkę w stos.
• Odczyt bez usuwania (peek) to stack[-1] dla stosu, a dla kolejki odczyt pierwszego elementu (front).

Minimum, które powinno wejść w pamięć

Jeżeli masz zapamiętać tylko kilka rzeczy z tej lekcji, zapamiętaj te:

1. Stos = LIFO (jak stos talerzy). Kolejka = FIFO (jak kolejka w sklepie).
2. Stos na liście: append() dodaje, pop() zdejmuje ze szczytu, stack[-1] pokazuje szczyt.
3. Kolejka na deque: append() dodaje na koniec, popleft() zdejmuje z początku.
4. Przed użyciem deque trzeba napisać from collections import deque.
5. pop() i popleft() zwracają usunięty element, więc zwykle zapisujemy go do zmiennej.
6. Do kolejki nie używamy list.pop(0), bo jest wolne. Używamy deque.
7. Nie ma metod push(), enqueue() ani dequeue(). To nazwy operacji, a w Pythonie używamy append(), pop() i popleft().

Ściągawka – najważniejsze polecenia i składnia

from collections import deque   # wymagany import dla deque

Najczęstsze pomyłki:

queue.pop()        # usuwa z KOŃCA, to nie jest dequeue
queue.popleft()    # usuwa z POCZĄTKU, to jest dequeue
lst.pop(0)         # działa, ale jest nieefektywne dla kolejki

Quiz – sprawdź się

Pytanie 1. Która struktura działa w modelu LIFO, a która FIFO? Do której z nich pasuje stos książek na biurku, a do której osoby czekające w kolejce do kasy?

Pytanie 2. Co zostanie wyświetlone?

stack = []
stack.append("A")
stack.append("B")
stack.append("C")
stack.pop()
print(stack)
print(stack[-1])

Pytanie 3. Co zostanie wyświetlone?

from collections import deque

q = deque(["Ala", "Ola"])
q.append("Ewa")
q.popleft()
print(q)
print(q[0])

Pytanie 4. Program ma zdjąć z kolejki pierwszą osobę (oczekiwany wynik: Alicja). Znajdź błąd i popraw go.

from collections import deque

queue = deque(["Alicja", "Bartek", "Celina"])
first = queue.pop()
print(first)

Pytanie 5. Uzupełnij kod tak, aby wyświetlił 30, a potem 20.

stack = [10, 20, 30]
top = stack.______()
print(top)
print(stack[______])

Pytanie 6. Która linia poprawnie dodaje element "X" na koniec kolejki queue utworzonej jako deque?

• a) queue.enqueue("X")
• b) queue.append("X")
• c) queue.push("X")
• d) queue.add("X")

Pytanie 7. Dlaczego do budowy kolejki zaleca się deque, a nie listę z pop(0)?

Pytanie 8. Zadanie praktyczne. Utwórz kolejkę klienci zawierającą "Ania", "Bartek", "Celina". Obsłuż pierwszego klienta (zdejmij go z kolejki i wyświetl jego imię), a następnie wyświetl, kto jest następny w kolejce i ilu klientów zostało.

top = stack.pop()
print(top)          # 30
print(stack[-1])    # 20

from collections import deque

klienci = deque(["Ania", "Bartek", "Celina"])
obslugiwany = klienci.popleft()
print(obslugiwany)    # Ania
print(klienci[0])     # Bartek
print(len(klienci))   # 2