Stacks and Queues

Two disciplines for ordered access

Stacks and queues are both restricted-access data structures: you can only interact with the ends, not the middle. That restriction is precisely what makes them powerful — each models a real-world ordering discipline.

Stacks — Last In, First Out (LIFO)

A stack adds and removes only at one end (the top). Think of a stack of plates: you put a plate on top, and you take the top plate off first.

stack.push(1);   // [1]
stack.push(2);   // [1, 2]
stack.push(3);   // [1, 2, 3]
stack.pop();     // 3  →  [1, 2]
stack.peek();    // 2 (look without removing)

The two operations are push (add to top) and pop (remove from top), both O(1).

The call stack

Every running program uses a stack internally to track function calls. When a function is invoked, its frame (locals, return address) is pushed. When it returns, the frame is popped. This is why recursion that goes too deep causes a stack overflow — the stack literally runs out of space.

Queues — First In, First Out (FIFO)

A queue adds at one end (the back) and removes from the other (the front). Think of a line at a coffee shop: first person in line is served first.

queue.enqueue("A");   // [A]
queue.enqueue("B");   // [A, B]
queue.enqueue("C");   // [A, B, C]
queue.dequeue();      // "A"  →  [B, C]

When to use which

• Stack — undo history, expression evaluation, backtracking, depth-first search (DFS).
• Queue — task scheduling, print spooling, request buffering, breadth-first search (BFS).

BFS and DFS are the same algorithm with a different container: a queue gives you BFS, a stack gives you DFS. The data structure chooses the traversal order.