Mindkettő O(1) végpontokkal rendelkező lineáris ADT, de az eltávolítás sorrendje ellenkező: a stack LIFO (legújabb először), a queue FIFO (legrégebbi először). Igazítsa a struktúrát a probléma szükséges sorrendjéhez.
Stack (LIFO): push 1,2,3 -> pop order 3,2,1
Queue (FIFO): enq 1,2,3 -> deq order 1,2,3
| STACK használata akkor... | QUEUE használata akkor... |
|---|
| Visszavonás/ismétlés (legújabb művelet először) | Feladat ütemezése (érkezési sorrend) |
| Böngésző vissza gombja | Nyomtatási sor / feladat sor |
| Függvényhívás/rekurzió | BFS / legrövidebb út egy gráfon |
| Zárójel illesztés, elemzés | Üzenet buffering szolgáltatások között |
| DFS (mélyebbre nézés először) | Sebesség korlátozás / kérelem kezelés |
# 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)
A LIFO-vs-FIFO választás közvetlenül megváltoztatja az algoritmus viselkedését: az ugyanaz a gráf bejárás stack-kel DFS-é válik, vagy queue-val BFS-é.
Annak felismerése, hogy a problémája "legújabb"-ra vagy "legrégebbi először"-re van szüksége, azonnal a megfelelő struktúrára irányítja.