Stack Data Structure: Complete Guide with LIFO Examples
The stack is the data structure you reach for when the most recent item must be handled first. Function calls nest on the call stack, and the last function called is the first one that returns. Undo history pops the most recent action before any older one. Bracket parsing closes the innermost opener first. All of these follow one rule: last in, first out, which is why the ordering is called LIFO.
Definition: a stack is a container with three core operations. Push adds an element to the top. Pop removes the top element and returns it. Peek reads the top element without removing it. Every stack algorithm, from expression evaluation to depth-first search, is built from these three operations plus the discipline of checking whether the stack is empty before reading from it.
Real-World Analogy
A set of nesting dolls is the cleanest picture. To reach the innermost doll you must open every doll that contains it, one at a time. To put the set away you build it back up from the inside. The last doll you opened is the first one you close again. That is exactly the contract a stack enforces. It also matches the call stack when one function calls another: the inner call finishes before the outer call continues, because the outer frame was opened first and closes last.
Visual Explanation
Here is the basic push and pop sequence on a stack of three values:
graph LR
A["Empty stack"] -->|"push(10)"| B["[10]"]
B -->|"push(20)"| C["[10, 20]"]
C -->|"push(30)"| D["[10, 20, 30]"]
D -->|"pop() returns 30"| E["[10, 20]"]
E -->|"pop() returns 20"| F["[10]"]
The pop returns 30 even though 10 arrived first. To reach 10 you must first pop everything pushed after it. This reversal of arrival order is the whole pattern. Most stack interview problems come down to one question: what must be processed in reverse order, and what needs to be remembered until a later element arrives?
The same structure drives bracket validation. Openers go on the stack, and a closer must match whatever is on top:
graph TD
A["Input: ( [ ) ]"] --> B["'(' goes on the stack"]
B --> C["'[' goes on the stack"]
C --> D["')' arrives. Top is '[' not '('."]
D --> E["Invalid: the brackets cross"]
A count of brackets would not catch this input. The counts are balanced, but the order is wrong. Only a stack remembers the most recent unclosed opener.
When to Use This Pattern
- The most recently seen element must be processed next. Undo history, browser back, and any “last action first” phrasing point here.
- The input has nested structure that must be validated or parsed. Parentheses, HTML tags, JSON, and arithmetic expressions all close in the reverse order they open.
- An operator or keyword applies to the most recent operands. Reverse Polish notation and calculator problems are stack problems by definition.
- You would write recursion but the depth is unbounded. An explicit stack gives the same behavior without the risk of a call stack overflow.
- You need the next greater or next smaller element for each position in an array. That is the monotonic stack, a specialized stack variant covered on its own page.
Complexity Analysis
| Operation | Time | Space | Notes |
|---|---|---|---|
| Push | O(1) | O(1) | Appends to the end of the backing array |
| Pop | O(1) | O(1) | Removes the top element |
| Peek | O(1) | O(1) | Reads the top element |
| Search | O(N) | O(1) | Must work through the stack to find a value |
| Stack of N elements | N/A | O(N) | Stores every element it was given |
Push and pop are
Common Mistakes
These four errors account for most stack solutions that fail a hidden test case.
Reading from an empty stack. A pop or a peek on an empty stack returns null in some languages and is undefined behavior in others. The usual cause is checking emptiness after the pop instead of before, or assuming the input guarantees a valid pop. Test with the first character of the input. If a closing bracket or a backspace arrives before anything was pushed, the guard is missing.
Mixing LIFO with FIFO. A queue also processes elements in arrival order, and the two containers look similar, so the wrong choice produces output that is almost right. State which element must come out next. If it is the most recent one, the container is a stack. If it is the earliest one, it is a queue. The queue pattern page covers that mirror.
Pushing in the wrong order when replacing recursion with an explicit stack. Recursion handles the call order implicitly, and the unwinding reverses it. An explicit stack that pushes children in the natural order processes them in reverse, so iterative DFS visits nodes differently from the recursive version. Push children in reverse order when the traversal order matters, and test on a small tree before moving on.
Validating nesting with counts instead of a stack. Counting each bracket type misses crossing patterns like ([)], where every type is balanced but the nesting is wrong. Any problem where the closing order matters needs a stack, because only a stack remembers the most recent unclosed opener. Keep ([)] as a permanent test case. A counter accepts it. A stack rejects it.
Related Patterns
- Monotonic Stack . The monotonic stack keeps its contents sorted to answer next greater and next smaller queries in one pass. It is still a stack, but the ordering discipline deserves its own page.
- Queue . The queue is the FIFO mirror of the stack. They meet in problems like Implement Queue using Stacks, where draining one stack into another reverses the order twice and restores FIFO.
- Recursion . Recursion runs on the call stack. When the depth is unbounded, converting to an explicit stack keeps the same logic without the overflow risk.
Next Steps
Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.