DSA: Stacks
Master the stack data structure, its implementations, and its applications in expression evaluation, monotonic problems, and more.
Stack ADT
A stack is a Last-In First-Out (LIFO) data structure. The element pushed last is the first to be popped. The only accessible element at any time is the top of the stack.
Core Stack Operations
All four standard stack operations run in O(1) time on both array and linked-list implementations.
- push(x): add element x to the top
- pop(): remove and return the top element
- peek() / top(): read the top element without removing it
- isEmpty(): returns true if the stack has no elements
| Operation | Array Stack | Linked List Stack |
|---|---|---|
| push | O(1) amortized | O(1) |
| pop | O(1) | O(1) |
| peek | O(1) | O(1) |
| isEmpty | O(1) | O(1) |
| Memory | Contiguous block | Scattered nodes + pointer overhead |
Array-Based Stack Implementation
An array-based stack uses a top index to track the last pushed element. Push increments top and writes the value; pop reads the value and decrements top.
Array Stack
The top variable acts as the stack pointer. Overflow occurs when top reaches the array capacity.
- Initial state: top = -1 (empty stack)
- push: top++, then arr[top] = val
- pop: return arr[top], then top--
- Stack overflow if top == capacity - 1; underflow if top == -1
Array-Based Stack
C++top tracks the index of the most recently pushed element. All operations are O(1).
Linked List-Based Stack Implementation
A linked-list stack uses the head of the list as the top. Push prepends a new node; pop removes the head node. No capacity limit is needed.
Linked List Stack
The head node is always the top. Push and pop only touch the head, so both are O(1) with no overflow risk.
- push: create a new node with next pointing to current head, update head
- pop: save head->data, move head to head->next, delete old head
- No fixed capacity, grows dynamically with heap allocation
- Each node carries extra pointer memory compared to the array version
Linked List Stack
C++head is the top. push prepends a node; pop removes and frees the head node.
Balanced Parentheses Checking
Push every opening bracket onto the stack. When a closing bracket is seen, pop the stack and verify the pair matches. If the stack is empty at the end, the string is balanced.
Bracket Matching Rules
Every closing bracket must match the most recently opened bracket, exactly what a stack models.
- Opening brackets: push onto stack
- Closing bracket: pop and check if it matches the corresponding opener
- Mismatch or pop from empty stack: unbalanced
- Non-empty stack at the end: unbalanced (unclosed openers remain)
Balanced Parentheses Checker
C++Three bracket types handled uniformly. A final empty-stack check catches unclosed openers.
Infix to Postfix Conversion
The Shunting-Yard algorithm converts infix expressions (operators between operands) to postfix (operators after operands) using a stack to handle operator precedence and parentheses.
Shunting-Yard Algorithm
Operands go directly to output. Operators wait on the stack until an operator of lower precedence arrives, then they are flushed to output.
- Operand (A-Z, 0-9): append directly to output string
- Operator: pop and output all stack operators with higher or equal precedence, then push the new operator
- Opening bracket: push onto stack
- Closing bracket: pop and output until the matching opening bracket is found, then discard both brackets
Infix to Postfix (Shunting-Yard)
C++Higher-precedence operators are flushed before the new operator is pushed, preserving evaluation order.
Postfix Expression Evaluation
Evaluate a postfix expression by pushing operands onto the stack and, upon each operator, popping two operands, applying the operator, and pushing the result back.
Postfix Evaluation Rule
In postfix, no parentheses or precedence rules are needed. Operands accumulate; each operator immediately consumes the two most recent operands.
- Digit: push its integer value
- Operator: pop b (top), then pop a, compute a op b, push result
- Note the order: second-popped value is the left operand
- Final stack top is the result after the full expression is processed
Postfix Evaluation
C++Pop b then a so that a is the left operand: a - b and a / b give the correct result.
Next Greater Element
For each element in an array, find the first element to its right that is greater. The naive O(n²) solution uses nested loops; a monotonic stack solves it in O(n).
Monotonic Stack Pattern
Maintain a stack of indices whose Next Greater Element has not been found yet. When a larger element arrives, it resolves all smaller waiting elements.
- Traverse left to right; for each element, pop indices while stack top element is smaller
- The current element is the NGE for every index just popped
- Push the current index onto the stack
- Remaining indices in the stack have no NGE; assign -1
Next Greater Element in O(n)
C++Each element is pushed and popped at most once, giving O(n) total time across the entire pass.
Stock Span Problem
The span of a stock price on day i is the number of consecutive days up to and including day i where the price was less than or equal to today's price. A stack of indices solves this in O(n).
Stock Span with a Stack
Pop all days from the stack whose price is less than or equal to today. The span equals today's index minus the index of the first day still on the stack.
- Push each day index onto the stack
- Before pushing, pop all indices where price is smaller than or equal to today
- If the stack is empty after popping, span = i + 1 (all previous days qualify)
- Otherwise span = i - stack.top() (distance to the last blocking day)
Stock Span Problem
C++Each index is pushed and popped once. span[i] = distance back to the first day with a higher price.
Min Stack: O(1) getMin
A Min Stack supports push, pop, and getMin all in O(1) time. An auxiliary stack tracks the current minimum after every push, so getMin is always a peek at the auxiliary stack's top.
Auxiliary Min Stack
Maintain a second stack where each position stores the minimum value in the main stack at that depth.
- push(x): push x to main stack; push min(x, minStack.top()) to auxiliary stack
- pop(): pop both stacks simultaneously
- getMin(): return minStack.top(), always O(1)
- The auxiliary stack top always reflects the current minimum without any scan
Min Stack with O(1) getMin
C++Each push records the running minimum so far. Popping both stacks together keeps them in sync.
Largest Rectangle in Histogram
Given bar heights in a histogram, find the largest rectangle that fits entirely within the bars. A monotonic increasing stack tracks the left boundary for each bar, giving an O(n) solution.
Histogram Stack Strategy
Maintain a stack of indices in increasing height order. When a shorter bar arrives, every taller bar in the stack can no longer extend right, compute their rectangle areas.
- Push bar indices while heights are increasing
- When heights[i] is smaller than the stack top height, pop and compute area: height * (i - stack.top() - 1)
- After traversal, pop remaining bars using n as the right boundary
- Time: O(n), Space: O(n). Each bar is pushed and popped exactly once.
Largest Rectangle in Histogram
C++A sentinel 0 at the end forces all remaining bars to be processed. Width = i - stack.top() - 1 after popping.
Celebrity Problem
A celebrity is known by everyone but knows nobody. Given a matrix where knows[i][j] = 1 means person i knows person j, find the celebrity in O(n) using a stack.
Celebrity via Stack Elimination
Push all candidates. Compare the top two: whoever knows the other cannot be the celebrity and is eliminated. One candidate remains for final verification.
- Push all n people onto the stack
- Pop two at a time: if A knows B, A is eliminated (push B back); else B is eliminated (push A back)
- The last person on the stack is the potential celebrity
- Verify: check that everyone knows the candidate and the candidate knows nobody
Celebrity Problem in O(n)
C++Each comparison eliminates one candidate. The single remaining candidate is verified in one final O(n) pass.
Knowledge Check
1. Which principle does a stack follow?
2. What is the time complexity of push and pop on an array-based stack?
3. To check balanced parentheses, what do you do when you see a closing bracket?
4. In infix-to-postfix conversion, what happens when an operator of lower or equal precedence is encountered while the stack top has higher precedence?
5. The Next Greater Element problem is solved efficiently using:
6. In the Min Stack design, how is O(1) getMin achieved?
7. In the Largest Rectangle in Histogram problem, the stack stores:
8. The Stock Span problem computes for each day: