Stack (stos) i queue (kolejka) to dwie z najczęstszych struktur na rozmowie technicznej. Większość zadań typu „cofnij ostatnią rzecz", „sprawdź najbliżej otwarty nawias", „przejdź graf poziomami" albo „obsłuż zadania w kolejności przyjścia" sprowadza się do prostego pytania: LIFO czy FIFO?
W tym artykule pokazuję obie struktury jako narzędzia algorytmiczne: kiedy list wystarczy jako stos, dlaczego list.pop(0) nie nadaje się do kolejki, kiedy używać collections.deque, jak zbudować parser nawiasów i undo/redo. Implementacje są w Pythonie, ale wzorzec jest language-agnostic — analogicznie zachowa się w Javie, C++ czy JavaScript.
Pozostaję w obrębie zwykłych stosów i kolejek FIFO. Priority queue (heap), thread-safe coordination i deque-based sliding window to powiązane, ale osobne tematy.
Czym jest stack (LIFO) i queue (FIFO)
Stack, czyli stos, to abstrakcyjna struktura danych działająca według zasady LIFO: Last In First Out. Ostatni element dodany do stosu jest pierwszym, który z niego zdejmiesz. Queue, czyli kolejka, działa według zasady FIFO: First In First Out. Pierwszy element dodany do kolejki jest pierwszym, który zostanie obsłużony.
Intuicja jest bardzo prosta: stos przypomina talerze układane jeden na drugim, a kolejka przypomina ludzi czekających przy kasie. W stosie dostępny jest tylko „wierzch", więc naturalne operacje to dodanie na koniec i zdjęcie z końca. W kolejce dodajesz na jednym końcu, a zdejmujesz z drugiego.
STACK / LIFO QUEUE / FIFO
push A enqueue A
push B enqueue B
push C enqueue C
top front back
| | |
v v v
[C] <- pop first [A] [B] [C]
[B] dequeue first ->
[A]
Na rozmowie rekrutacyjnej stack i queue rzadko są celem samym w sobie. Częściej są sygnałem, że problem ma naturalną kolejność przetwarzania: „cofnij ostatnią rzecz", „sprawdź ostatnio otwarty nawias", „przejdź graf poziomami", „obsłuż zadania w kolejności przyjścia".
stack = []
stack.append("A")
stack.append("B")
print(stack.pop()) # expected_output: B
queue = ["A", "B"]
print(queue[0]) # expected_output: A
Pułapka: mylenie LIFO i FIFO. Dla wejścia A, B, C stos zwróci najpierw C, a kolejka zwróci najpierw A. Jeśli w BFS użyjesz stosu zamiast kolejki, algorytm zacznie zachowywać się jak DFS i kolejność odwiedzania wierzchołków będzie inna.
List jako stack w Pythonie
Pythonowa list bardzo dobrze nadaje się do implementacji stosu. Operacja append() dodaje element na koniec listy, a pop() bez argumentu zdejmuje element z końca. Dla typowego użycia jako LIFO obie operacje mają amortyzowany koszt O(1) — szczegóły klas złożoności w Big O w 10 minut.
Intuicja wynika z tego, jak lista przechowuje elementy: koniec tablicy dynamicznej jest miejscem, gdzie Python może szybko dopisać nowy element albo usunąć ostatni bez przesuwania reszty. Stos dokładnie tego potrzebuje.
stack = []
append("read")
["read"]
append("parse")
["read", "parse"]
pop()
["read"] -> returns "parse"
Na rozmowie używaj listy jako stosu, gdy widzisz słowa: ostatni, cofnięcie, zagnieżdżenie, najnowszy kontekst, aktualna ścieżka, backtracking, DFS. To jest idiomatyczne i czytelne w Pythonie.
stack = []
stack.append("open")
stack.append("edit")
stack.append("save")
last_action = stack.pop()
print(last_action) # expected_output: save
print(stack) # expected_output: ['open', 'edit']
Pułapka: używanie insert(0, item) i pop(0) do symulowania stosu „od lewej strony". Dla wejścia z tysiącami elementów działa poprawnie logicznie, ale mechanicznie wymusza przesuwanie elementów w pamięci. Stos na liście powinien rosnąć i maleć z końca.
List NIE jest dobrą kolejką
Pythonowa list nie jest dobrą kolejką, jeśli zdejmujesz elementy z początku przez pop(0). Sama operacja zwróci poprawny element FIFO, ale ma koszt O(n), ponieważ po usunięciu pierwszego elementu Python musi przesunąć wszystkie pozostałe elementy o jedno miejsce w lewo.
Intuicja: lista jest tablicą dynamiczną, więc elementy stoją obok siebie w indeksach. Gdy znika indeks 0, element z indeksu 1 musi stać się nowym 0, element z indeksu 2 nowym 1 i tak dalej. To nie jest „zdjęcie z przodu", tylko zdjęcie plus masowe przesuwanie.
before pop(0):
index: 0 1 2 3
value: [A] [B] [C] [D]
remove A, then shift:
[B] -> index 0
[C] -> index 1
[D] -> index 2
Na rozmowie to częsty test świadomości złożoności. Kandydat może napisać BFS z list.pop(0) i dostać poprawny wynik na małym przykładzie, ale rozwiązanie skaluje się słabo. Sygnał ostrzegawczy: „kolejka" plus częste zdejmowanie z początku listy.
queue = ["A", "B", "C", "D"]
first = queue.pop(0)
print(first) # expected_output: A
print(queue) # expected_output: ['B', 'C', 'D']
Pułapka: „przecież działa na przykładzie". Dla wejścia ["A", "B", "C", "D"] wynik jest poprawny, ale po pop(0) Python przesuwa B, C i D. Przy milionie elementów robisz to wielokrotnie, więc koszt może zdominować cały algorytm.
collections.deque
collections.deque to struktura typu double-ended queue, czyli kolejka z dwoma końcami. Pozwala dodawać i zdejmować elementy z lewej oraz prawej strony w O(1): append, pop, appendleft, popleft.
Intuicja: deque nie działa jak zwykła płaska lista, tylko jak double-linked-list-of-blocks. W praktyce oznacza to, że Python zarządza blokami elementów i może efektywnie operować na obu końcach bez przesuwania całej zawartości.
DEQUE
left end right end
| |
v v
[A] [B] [C] [D]
appendleft("X") -> [X] [A] [B] [C] [D]
popleft() -> [A] [B] [C] [D]
append("Y") -> [A] [B] [C] [D] [Y]
pop() -> [A] [B] [C] [D]
Na rozmowie deque jest domyślnym wyborem do BFS, kolejek roboczych i problemów, gdzie trzeba sprawnie zdejmować elementy z przodu. Jeśli problem mówi o dwóch końcach, oknie przesuwanym albo operacjach z lewej i prawej strony, deque powinien być pierwszym skojarzeniem.
from collections import deque
items = deque(["B", "C"])
items.appendleft("A")
items.append("D")
print(items.popleft()) # expected_output: A
print(items.pop()) # expected_output: D
Pułapka: traktowanie deque jak listy do losowego dostępu po indeksach. Dla wejścia z dużą liczbą elementów częste items[i] w środku struktury nie jest głównym zastosowaniem deque. Jeśli potrzebujesz intensywnego indeksowania, zwykła lista może być lepsza.
queue.Queue thread-safe vs deque
queue.Queue to kolejka z modułu queue, zaprojektowana do komunikacji między wątkami. Jest thread-safe i ma semantykę blokującą: get() może czekać, aż pojawi się element, a put() może czekać, jeśli kolejka ma limit rozmiaru. deque jest prostszy i zwykle wybierany w kodzie jednowątkowym.
Intuicja: deque jest strukturą danych, a queue.Queue jest narzędziem koordynacji. Jeśli masz jeden algorytm, jedną pętlę i chcesz BFS, wybierasz deque. Jeśli masz producentów i konsumentów w wielu wątkach, potrzebujesz kolejki, która pilnuje synchronizacji.
single-thread algorithm:
producer code -> deque -> consumer code
multi-thread program:
thread A -> queue.Queue -> thread B
waits safely
Na rozmowie technicznej różnica jest ważna, bo pokazuje, że nie wybierasz narzędzia tylko po nazwie. queue.Queue nie jest „lepszą deque"; jest cięższym narzędziem do innego problemu. Do BFS w normalnym algorytmie użyj collections.deque.
from queue import Queue
jobs = Queue()
jobs.put("parse")
jobs.put("score")
print(jobs.get()) # expected_output: parse
print(jobs.get()) # expected_output: score
Pułapka: użycie queue.Queue.get() tam, gdzie nie masz pewności, że element istnieje. Dla pustej kolejki get() może blokować program. W algorytmie jednowątkowym to wygląda jak „zawieszenie", bo kod czeka na element, którego nikt nigdy nie doda.
Wzorzec: parser zbalansowanych nawiasów
Parser zbalansowanych nawiasów to klasyczny przykład użycia stacku. Dla każdego otwierającego nawiasu robisz push, a dla każdego zamykającego robisz pop i sprawdzasz, czy typ pasuje. Jeśli na końcu stack jest pusty, nawiasy są poprawnie zbalansowane.
Intuicja: najbliższy zamykający nawias musi pasować do ostatniego jeszcze niezamkniętego nawiasu. To jest dokładnie LIFO. Gdy widzisz ([{}]), nawias { zamyka się przed [, a [ przed (. Ostatnio otwarty kontekst musi zostać zamknięty jako pierwszy.
input: ([{}])
read ( -> push (
read [ -> push [
read { -> push {
read } -> pop { OK
read ] -> pop [ OK
read ) -> pop ( OK
end -> stack empty OK
Na rozmowie ten wzorzec pojawia się jako walidacja nawiasów, tagów, bloków składni, ścieżek rekurencji albo stanów zagnieżdżonych. Sygnał rozpoznawczy: „ostatni otwarty element musi być pierwszym zamkniętym".
def is_balanced(text):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for char in text:
if char in "([{":
stack.append(char)
elif char in pairs:
if not stack or stack.pop() != pairs[char]:
return False
return not stack
print(is_balanced("([{}])")) # expected_output: True
print(is_balanced("([)]")) # expected_output: False
Trace dla is_balanced("([)]"):
Krok 1: czytamy ( → push (. Stack: ['('].
Krok 2: czytamy [ → push [. Stack: ['(', '['].
Krok 3: czytamy ) → pop zwraca [, ale pairs[')'] = '('. Niezgodność → return False.
Klucz: licznik samych otwarć i zamknięć by tu nie pomógł — ([)] ma po 2 z każdego, ale kolejność łamie LIFO. Stack łapie błąd dzięki temu, że pamięta jaki nawias był ostatnio otwarty.
Pułapka: sprawdzanie tylko liczby nawiasów. Input ([)] ma tyle samo otwarć i zamknięć, ale jest błędny. Mechanizm błędu: przy ) ostatnim otwartym nawiasem jest [, więc ) nie może go zamknąć. Sam licznik tego nie wykryje.
Wzorzec: undo/redo z dwoma stosami
Undo/redo naturalnie modeluje się dwoma stosami. done_stack przechowuje wykonane akcje, a redo_stack przechowuje akcje cofnięte. Każda nowa akcja trafia na done_stack; undo robi done_stack.pop() i przenosi akcję na redo_stack.
Intuicja: cofanie zawsze dotyczy ostatniej wykonanej akcji, więc to LIFO. Redo też działa LIFO względem akcji cofniętych: ostatnio cofnięta akcja jest pierwszą, którą możesz ponownie wykonać. Nowa akcja zwykle czyści redo_stack, bo historia alternatywna przestaje być poprawna.
done_stack: [type A, type B, type C]
undo -> pop type C
done_stack: [type A, type B]
redo_stack: [type C]
redo -> pop type C back to done_stack
Na rozmowie ten wzorzec może pojawić się w edytorach tekstu, historii przeglądarki, operacjach na dokumencie, grach i systemach komend. Sygnał: „cofnij ostatnią operację" oraz „przywróć ostatnio cofniętą operację".
done_stack = []
redo_stack = []
done_stack.append("type A")
done_stack.append("type B")
redo_stack.append(done_stack.pop())
done_stack.append(redo_stack.pop())
print(done_stack) # expected_output: ['type A', 'type B']
print(redo_stack) # expected_output: []
Pułapka: nieczyszczenie redo_stack po nowej akcji. Input: wykonujesz A, potem B, robisz undo B, a potem wykonujesz nowe C. Jeśli redo_stack nadal zawiera B, redo może przywrócić akcję z nieaktualnej gałęzi historii, dając sekwencję A, C, B, której użytkownik nie wykonał.
Wzorzec: BFS na drzewie lub grafie z deque
BFS, czyli breadth-first search, przegląda drzewo lub graf warstwami. Używa kolejki FIFO: najpierw odwiedzasz wierzchołek startowy, potem jego sąsiadów, potem sąsiadów sąsiadów. DFS używa stacku LIFO, BFS używa queue FIFO; to ważny związek z Drzewami Binarnymi.
Intuicja: FIFO zachowuje kolejność odkrywania. Jeśli najpierw odkrywasz dzieci poziomu 1, one muszą zostać obsłużone przed dziećmi poziomu 2. Gdyby użyć stosu, najnowszy sąsiad zostałby przetworzony od razu i algorytm poszedłby głębiej.
tree:
A
/ \
B C
/ \ \
D E F
BFS queue:
[A] -> [B, C] -> [C, D, E] -> [D, E, F]
order: A, B, C, D, E, F
Na rozmowie BFS pojawia się przy najkrótszej ścieżce w grafie nieważonym, level-order traversal, minimalnej liczbie kroków, rozlewaniu się stanu po planszy i problemach „najpierw wszystkie możliwości oddalone o 1, potem o 2". Domyślna struktura w Pythonie to deque.
from collections import deque
graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": [], "F": []}
queue = deque(["A"])
order = []
while queue:
node = queue.popleft()
order.append(node)
queue.extend(graph[node])
print(order) # expected_output: ['A', 'B', 'C', 'D', 'E', 'F']
Trace BFS:
Krok 1: kolejka startuje jako [A].
Krok 2: zdejmij A, dodaj B i C → kolejka [B, C].
Krok 3: zdejmij B, dodaj D i E → kolejka [C, D, E].
Krok 4: zdejmij C, dodaj F → kolejka [D, E, F].
Krok 5: zdejmuj D, E, F (puste sąsiedztwa). Kolejność wyniku: A, B, C, D, E, F.
Pułapka: brak visited w grafie z cyklami. Dla grafu A -> B, B -> A kolejka będzie w kółko dodawać już odwiedzone wierzchołki. W drzewie to zwykle nie wyjdzie, ale w grafie mechanizm błędu to ponowne odkrywanie tych samych stanów (rozwiązanie: visited = set() jak w Haszowaniu).
Sygnały rozpoznawcze: kiedy LIFO, kiedy FIFO
W rozmowie rekrutacyjnej najważniejsze jest rozpoznanie wzorca, zanim zaczniesz kodować. Stack wybierasz, gdy najważniejszy jest ostatnio dodany element. Queue wybierasz, gdy musisz zachować kolejność przyjścia albo przetwarzać rzeczy warstwami.
Intuicja opiera się na pytaniu: „który element ma być następny?". Jeśli odpowiedź brzmi „najnowszy", myślisz LIFO. Jeśli odpowiedź brzmi „najstarszy czekający", myślisz FIFO. Jeśli oba końce są ważne, myślisz o deque.
question: which item is next?
latest added -> stack -> LIFO
oldest waiting -> queue -> FIFO
both ends matter -> deque -> double-ended queue
Sygnały rozpoznawcze: zbalansowane nawiasy → stack; DFS iteracyjny → stack; backtracking → stack; undo → stack; BFS → queue; level-order traversal → queue; producer-consumer między wątkami → queue.Queue; sliding window z operacjami na końcach → deque.
patterns = {
"balanced parentheses": "stack",
"BFS": "queue",
"undo": "two stacks",
"two-ended operations": "deque",
}
print(patterns["BFS"]) # expected_output: queue
print(patterns["undo"]) # expected_output: two stacks
Pułapka: wybieranie struktury po nazwie problemu zamiast po kolejności przetwarzania. Input: „traverse a tree" nie wystarcza. Jeśli oczekiwany jest preorder w głąb, pasuje stack lub rekurencja DFS — szczegóły: Rekurencja vs Iteracja. Jeśli oczekiwany jest level-order, pasuje queue.
Kiedy NIE stack/queue
Nie każdy problem z „następnym elementem" jest stackiem albo kolejką. Jeśli następny ma być element o najwyższym lub najniższym priorytecie, to jest priority queue i w Pythonie zwykle użyjesz heapq. Jeśli potrzebujesz wyszukiwania pozycji w posortowanej liście, pasuje bisect. To są osobne narzędzia.
Intuicja: stack i queue ignorują wartość elementu; liczy się tylko kolejność dodania. Heap wybiera według priorytetu. bisect wykorzystuje porządek sortowania do wyszukiwania miejsca. collections.Counter, heapq i queue.PriorityQueue nie są zamiennikami hash mapy, stacku ani zwykłej kolejki; rozwiązują inne problemy.
next by recency -> stack
next by arrival -> queue
next by priority -> heap / priority queue
position in sorted -> bisect
frequency counting -> Counter
Na rozmowie anty-przykłady są równie ważne jak wzorce. Konkretny anty-przykład: zadania (priority=5, "A"), (priority=1, "B") z FIFO obsłużą A jeśli przyszło pierwsze, ale poprawny wybór priorytetowy to B. Mechanizm błędu: kolejka patrzy na czas dodania, nie na wartość priorytetu. Tu pasuje heapq.heappop.
import heapq
tasks = [(2, "email"), (1, "deploy")]
heapq.heapify(tasks)
print(heapq.heappop(tasks)) # expected_output: (1, 'deploy')
Pułapka: używanie queue do problemu z priorytetem. Input zadania [(5, "A"), (1, "B")]: FIFO obsłuży (5, "A") pierwsze (jako pierwsze dodane), ale priority queue da (1, "B") jako bardziej pilne. Mechanizm błędu: FIFO ignoruje wartości — zwraca elementy w kolejności wstawiania, nie ważności.
Najczęstsze błędy
Mylenie LIFO i FIFO. Dla wejścia A, B, C stos zwróci najpierw C, kolejka A. Jeśli w BFS użyjesz stosu, algorytm zachowuje się jak DFS — kolejność odwiedzania węzłów jest inna, a problem typu „najkrótsza ścieżka w grafie nieważonym" da błędną odpowiedź. Naprawa: zawsze wprost zadawaj pytanie „najnowszy czy najstarszy element ma być następny?".
list.pop(0) jako kolejka. Wynik logicznie poprawny, ale koszt O(n) per operacja, bo Python przesuwa wszystkie pozostałe elementy w lewo. Przy 10⁶ elementach to 10¹² operacji vs O(1) dla deque.popleft(). Naprawa: from collections import deque; queue.popleft().
Sprawdzanie tylko liczby nawiasów w parserze. Input ([)] ma 2 otwarcia i 2 zamknięcia, licznik mówi „balanced", ale nawiasy są przeplecione. Stack łapie błąd dzięki LIFO: gdy widzisz ), na wierzchu jest [, niezgodność wykryta. Naprawa: zawsze stack, nie licznik.
Używanie queue.Queue.get() w jednowątkowym algorytmie. Pusta kolejka blokuje wątek, kod wisi bez timeoutu. Naprawa: w single-thread BFS używaj collections.deque z warunkiem while queue:. queue.Queue zostaw do koordynacji wielu wątków.
Brak visited w BFS na grafie z cyklami. Algorytm w kółko dodaje już odwiedzone wierzchołki, czas pracy eksploduje, możliwy stack overflow w wariancie rekurencyjnym. Naprawa: visited = set(), sprawdzaj if node not in visited przed dodaniem do kolejki.
FAQ
Mogę używać list jako kolejki dla małych danych?
Technicznie tak — wynik będzie poprawny. Dla n < 100 różnica O(n) vs O(1) jest nieistotna. Ale na rozmowie nawet poprawny list.pop(0) jest sygnałem braku świadomości złożoności — rozmówca może drążyć „a co przy 10⁶ elementów?". Bezpiecznie: zawsze deque dla kolejki, niezależnie od n.
Czemu Python ma osobny queue.Queue, skoro jest deque?
Bo to różne narzędzia. deque to struktura danych — szybkie operacje na obu końcach, brak gwarancji thread-safety. queue.Queue to mechanizm koordynacji wielu wątków — używa locków wewnętrznie, blokuje na pustej kolejce w get(), blokuje na pełnej w put(). Do BFS wybierasz deque. Do producer-consumer między threadami — queue.Queue.
Czy deque może zastąpić listę w każdym kontekście?
Nie. deque ma O(n) losowy dostęp deque[i] i nie wspiera slicing tak elastycznie jak lista. list ma O(1) dostęp po indeksie i jest bardziej Pythonic dla kolekcji bez intensywnych operacji na początku. Reguła: deque gdy potrzebujesz popleft/appendleft, list gdy potrzebujesz indeksowania i slicing.
Jak zaimplementować priority queue ręcznie?
W Pythonie używasz heapq na zwykłej liście — to in-place binary heap. heappush(items, value) dodaje, heappop(items) zwraca najmniejszy. Dla max-heap negujesz wartości lub używasz tuple z odwróconym priorytetem. queue.PriorityQueue jest też dostępne, ale dodaje thread-safety overhead, którego rzadko potrzebujesz.
Czy DFS rekurencyjny używa „prawdziwego" stacku?
Tak — call stack interpretera Pythona to LIFO. Każde rekurencyjne wywołanie dodaje ramkę na stos wywołań, każdy return zdejmuje ją. Iteracyjny DFS z list jako stosem robi to samo, ale jawnie. Różnica: rekurencja ma limit głębokości (sys.getrecursionlimit(), domyślnie 1000), iteracja z explicit stackiem nie. Kontekst: Rekurencja vs Iteracja.
Czemu undo/redo wymaga DWÓCH stacków, nie jednego?
Bo jeden stack mówi tylko „cofnij", drugi jest potrzebny do „przywróć cofnięcie". Akcja z done_stack.pop() musi gdzieś trafić, żeby redo mogło ją znaleźć. Kluczowe: nowa akcja po undo czyści redo_stack, bo gałąź historii alternatywnej staje się nieaktualna. Bez czyszczenia możesz przywrócić akcję, której logicznie nie wykonałeś.
Powiązane tematy
- Drzewa Binarne — Wzorzec Rekurencyjny na Rozmowie — DFS używa stacku (LIFO), BFS używa kolejki (FIFO); ten artykuł rozszerza intuicję traversali na konkretnych drzewach.
- Rekurencja vs Iteracja — Kiedy Która Wygrywa — call stack rekurencji to ukryty stack LIFO; explicit stack to iteracyjne równoważnik z lepszą kontrolą głębokości.
- Big O w 10 Minut — Notacja Złożoności — kontekst dla
O(1)(append/pop) vsO(n)(pop(0)); klasyfikacja kosztów operacji na strukturach danych.
Sprawdź swoją wiedzę quizem
Przerób ten artykuł w 15-pytaniowy quiz testujący LIFO/FIFO, list vs deque, parser nawiasów, undo i BFS — gdzie masz luki przed rozmową techniczną: https://odpytywarka.pl/q/vlQGwg.
Masz własne notatki na rozmowę? Wgraj PDF lub wklej tekst na stworz-quiz-z-pdf — pierwsze 3 strony PDF i 15 pytań jednokrotnego wyboru za darmo, generowanie 30-60 sekund.
Źródła
- Python docs —
collections.deque— double-ended queue z O(1) na obu końcach. - Python docs —
queue.Queue— thread-safe queue dla komunikacji wielowątkowej. - Wikipedia — Stack (abstract data type) — formalna definicja LIFO.
- Wikipedia — Queue (abstract data type) — formalna definicja FIFO.