Båda är linjära ADT:er med O(1) i ändarna, men ordningen för borttagning är motsatt: en stack är LIFO (nyaste först), en kö är FIFO (äldsta först). Matcha strukturen med den ordning ditt problem kräver.
Stack (LIFO): push 1,2,3 -> pop order 3,2,1
Queue (FIFO): enq 1,2,3 -> deq order 1,2,3
| Använd en STACK när... | Använd en KÖ när... |
|---|
| Undo/redo (senaste åtgärd först) | Schemaläggning av jobb (ankomstordning) |
| Webbläsarens bakåtknapp | Skrivarkö / uppgiftskö |
| Funktionsanrop/rekursion | BFS / kortaste väg i en graf |
| Matchning av parenteser, parsing | Meddelandebuffring mellan tjänster |
| DFS (utforska djupast först) | Hastighetsbegränsning / förfrågehantering |
# 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)
Valet LIFO-mot-FIFO ändrar direkt algoritmens beteende: samma graftransversal blir DFS med en stack eller BFS med en kö.
Att identifiera om ditt problem behöver "senaste" eller "äldsta först" pekar omedelbar på rätt struktur.