Oba są liniowymi ADT-ami z O(1) końcówkami, ale kolejność usuwania jest odwrotna: stos to LIFO (najnowsze pierwsze), kolejka to FIFO (najstarsze pierwsze). Dopasuj strukturę do kolejności wymaganej przez Twój problem.
Stack (LIFO): push 1,2,3 -> pop order 3,2,1
Queue (FIFO): enq 1,2,3 -> deq order 1,2,3
| Użyj STOSU gdy... | Użyj KOLEJKI gdy... |
|---|
| Cofnij/Ponów (najnowsza akcja pierwsza) | Planowanie zadań (kolejność przybycia) |
| Przycisk wstecz przeglądarki | Kolejka drukowania / kolejka zadań |
| Wywołanie funkcji/rekursja | BFS / najkrótsza ścieżka na grafie |
| Pasujące nawiasy, parsing | Buforowanie wiadomości między usługami |
| DFS (eksploruj najpierw najgłębiej) | Ograniczanie szybkości / obsługa żądań |
# DFS uses a stack: explore newest branch first
stack = [start]
while stack:
node = stack.pop() # LIFO -> goes deep
for nb in graph[node]: stack.append(nb)
# BFS uses a queue: explore nearest first
from collections import deque
q = deque([start])
while q:
node = q.popleft() # FIFO -> goes level by level
for nb in graph[node]: q.append(nb)
Wybór LIFO versus FIFO bezpośrednio zmienia zachowanie algorytmu: ta sama traversacja grafu staje się DFS ze stosem lub BFS z kolejką.
Rozpoznanie, czy Twój problem wymaga "najnowsze" czy "najstarsze pierwsze", natychmiast wskazuje na właściwą strukturę.
Biblioteka pytań rekrutacyjnych IT ze szczegółowymi odpowiedziami — od Juniora do Seniora.
Wesprzyj