Stack and Queue
Two ordered collections defined by their access discipline: last-in-first-out and first-in-first-out.
Definition
A stack is a last-in-first-out (LIFO) collection: the most recently added item is removed first. A queue is first-in-first-out (FIFO): items leave in the order they arrived. Both restrict access to enforce a useful discipline.
A double-ended queue generalizes both, allowing insertion and removal at either end, and underlies sliding-window algorithms and work-stealing schedulers. Ring buffers implement queues in fixed memory, a common pattern in embedded and real-time systems.
These disciplines model an enormous range of real processes precisely because their constrained interfaces make behavior easy to reason about. The stack's role in managing function calls is what makes recursion possible; queues buffer work between producers and consumers running at different rates. Priority queues, which serve the most urgent item next, generalize the queue and underlie scheduling, event simulation, and shortest-path algorithms alike.
Where they appear
- Stacks: function call management, expression evaluation, undo history, depth-first search.
- Queues: task scheduling, buffering, breadth-first search.
- Priority queues: serve the highest-priority item next.
Why it matters
These simple disciplines model an enormous range of real processes. The call stack that makes recursion work is a stack; job schedulers and data buffers are queues. Their constrained interface makes reasoning about correctness straightforward.
Fusion connection
Job queues manage the batches of simulation runs submitted to Kronos compute clusters, sequencing work across many nodes.