Stacks and Queues

After arrays, linked lists, and hash maps, structures defined by how they store, stacks and queues are something different: structures defined by what they refuse to do. Both hold a collection, both add and remove elements, but each enforces a single rule about which element leaves next, and that one rule is the entire specification. This is the cleanest example in computing of an interface, what operations exist and what they promise, standing apart from an implementation, whatever machinery delivers the promise, a distinction MIT's 6.006 hammers from its second lecture onward.

• Stack, LIFO, last in, first out: push adds to the top, pop removes from the top. The newest element always leaves first.
• Queue, FIFO, first in, first out: enqueue adds at the back, dequeue removes from the front. The oldest element always leaves first.

The cafeteria owns both metaphors. The spring-loaded plate dispenser is a stack: the plate you take is the one most recently placed, and reaching a lower plate means removing every plate above it. The checkout line is a queue: whoever has waited longest is served next, and newcomers join the back. Notice that neither structure lets you grab from the middle, and that restriction is a feature: it makes behavior perfectly predictable and every operation constant-time.

One rule, opposite behavior

The two disciplines produce opposite orderings of the same input. Push A, B, C onto a stack and pop everything: out comes C, B, A, reversed. Enqueue A, B, C and drain the queue: out comes A, B, C, preserved. Reversal versus preservation is the entire behavioral difference, and it decides which structure an algorithm needs. Anything that must retrace its steps, most recent first, wants a stack. Anything that must be fair to arrival order, or explore things in the order they were discovered, wants a queue. The playground below demonstrates stack reversal with a charming trick: since the teaching language has no arrays, the stack is packed into the digits of one number, push multiplies by 10 and adds, pop reads and strips the last digit.

Implementations: both are thin skins

Neither structure needs new machinery, both are disciplines imposed on structures you already know. A stack over a dynamic array is trivial: push appends at the end, pop removes from the end, both amortized O(1), and this is what most real stacks are. A queue over a plain array has a famous trap: dequeuing from the front by shifting every element is O(n). The fixes are either a linked list with head and tail pointers, dequeue at the head, enqueue at the tail, both O(1), or the circular buffer, an array whose head and tail indexes wrap around modulo the capacity, the remainder trick from the hash lesson reappearing as geometry. All standard treatments, Open Data Structures covers each in its array and linked chapters.

Interface versus implementation is worth one more beat here: an algorithm that says give me a stack does not care which implementation arrives, and swapping the array version for the linked version cannot change the algorithm's correctness, only its constants. This substitutability is why the next lessons can say BFS uses a queue, DFS uses a stack, as complete specifications: the discipline is the meaning, the container is a detail. That is the deepest lesson these two structures teach, and it is the same interface discipline that lets a virtual machine swap its internals while running the same bytecode.

Where each discipline runs your machine

• The call stack: function calls push frames, returns pop them, which is why recursion depth is stack space and why the overflow is named after this structure.
• Undo and redo: each edit pushes its inverse onto a stack, undo pops the most recent, redo pushes onto a second stack.
• Expression evaluation: the stack machines of Level 3 evaluate bytecode by pushing operands and popping them at each operation.
• Task scheduling and message passing: event loops and job runners dequeue work in arrival order, the fairness guarantee only FIFO provides.
• Search: depth-first exploration follows a stack, plunging down the newest path first; breadth-first follows a queue, expanding the oldest frontier first. The graphs lesson turns this one bullet into an entire algorithm family.

Stacks, queues, and protected code

For this Academy, the stack is nothing less than the protagonist's shadow: the stack machines that run bytecode in Level 3, the call stacks that debuggers pause and read in Level 5, the dispatch loops of Level 7 whose virtual machines maintain their own operand stacks inside the real one. When an analyst attaches a debugger to a protected program, the call stack is the first thing they read, a truthful history of how execution arrived at the breakpoint, and anti-analysis techniques that scramble or deepen call chains exist precisely to poison that reading. Queues run the other side of the shop: the event loops and job pipelines that process obfuscation requests are FIFO systems, dequeuing work in fairness order. Two disciplines, both O(1) per operation, quietly running everything.

A stack serves the newest element first, a queue serves the oldest, and that single rule difference makes one reverse its input and the other preserve it. Both run at O(1) per operation over an array or linked list. Call stacks, undo, and depth-first search are LIFO; schedulers, pipelines, and breadth-first search are FIFO.

Frequently asked questions