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)