Stack fundamentals
Scenario
Ever hit Ctrl+Z? That undo history is a stack — the last thing you did is the first thing undone.
How do we structurally enforce this reverse-chronological order?
Why it exists
Problem: Sometimes we need to process data in the exact reverse order of its arrival, like hitting 'undo' in an editor or returning from nested function calls. A generic array or list doesn't strictly enforce this ordering.
Naive approach: Using a standard array and manually tracking the 'last inserted' index, or shifting elements, which can lead to bugs or O(n) operations if not careful.
Better idea: A Stack restricts access to a single boundary called the 'top'. By strictly enforcing a Last-In-First-Out (LIFO) policy, we guarantee O(1) time complexity for adding (push) or removing (pop) the most recent item.
Mental model
Think of a physical stack of plates in a cafeteria. You can only add a new plate to the top, and you can only take a plate off the top.
A stack is a dynamic set functioning strictly under a Last-In-First-Out (LIFO) policy. It can be implemented using a dynamic array (excellent cache locality) or a linked list (strict O(1) bounds). Popping an element doesn't destroy the data in memory; it just shifts the 'top' boundary pointer downwards.
Repeated decision: When inserting, place the item at the current top boundary. When removing, take the item at the top boundary and shift the boundary down.
Explanation
A stack is the foundational linear data structure for anything that requires reversing chronological order. Whether it is a depth-first search exploring the deepest branch first, or the CPU executing nested subroutine calls, stacks elegantly freeze a current state to be resumed later.
While you can technically build a stack out of a linked list (inserting and removing at the head), modern production systems almost universally use dynamic arrays (like Python's list or Java's ArrayDeque). This is because contiguous memory allows the CPU to pre-fetch the array into its extremely fast L1/L2 caches, obliterating the performance of pointer-heavy linked lists in the real world.
One subtlety with array-backed stacks: when the array fills up it must double its capacity, and that single push costs O(n) to copy everything across. But because a doubling buys you n more free pushes before the next resize, the cost averages out to O(1) per push over many operations — this is what 'amortized O(1)' means. (Pop is always strict O(1); it never resizes.) A final party trick: two stacks placed back-to-back can simulate a FIFO queue — push onto an 'in' stack, and when you need to dequeue, pour everything into an 'out' stack, which reverses the LIFO order into FIFO.
Key points
- Invariant: Elements are strictly added and removed from only one end (the top).
- Complexity: O(1) time for push and pop operations.
- Recognition cue: Whenever you need to process data in a Last-In-First-Out (LIFO) or reverse-chronological order.
Pattern: LIFO Processing
Recognition cues:
- Requires reversing the order of input
- Processing nested structures
- Simulating recursion
Failure signals
- Need to access elements in the middle of the collection
- Need FIFO ordering instead of LIFO
Engineering examples
Function Call Stack
Tracking nested subroutine execution state
The LIFO property perfectly models suspending a current context, handling a nested context, and resuming the original state.
Undo/Redo Buffers
Reversing sequential document mutations
Each action is pushed onto a stack. An undo pops the most recent action and reverses it.
Common mistakes
- Using legacy Java Stack: The legacy java.util.Stack extends Vector, inheriting index-based access (breaking the LIFO invariant) and incurring heavy synchronization locks. Modern Java uses ArrayDeque.
- Ignoring Cache Locality: While linked lists provide strict O(1) pushes, array-based stacks are overwhelmingly preferred in engineering due to superior CPU cache prefetching.
Recall questions
- What is the defining property of a Stack?
- What is the time complexity of push and pop operations?
- Why is an array-based stack often faster in practice than a linked-list stack?
Questions & answers
Design an undo/redo system for a text editor.
Use two stacks. Push actions to the undo stack. On undo, pop from the undo stack, reverse the action, and push to the redo stack.
Approach: Recognize that reversing actions perfectly maps to a LIFO structure.
How does the operating system manage function calls?
It uses a call stack. Each function call pushes a stack frame (local variables, return address). Returning pops the frame.
Approach: Demonstrate understanding of systemic stack usage.
Implement a Queue using two Stacks.
Use one stack for enqueueing. For dequeue, if the out-stack is empty, pop everything from the in-stack and push to the out-stack, reversing the order. Pop from out-stack. Amortized O(1).
Approach: Simulate FIFO by reversing LIFO twice.
Continue learning
Next: Valid parentheses
Next: Min stack
Related: Min stack
Related: Monotonic stack
Related: Valid parentheses
Related: Queue & deque