Stack
3 min read
data-structuresstackcs-fundamentalsinterview-prep
LIFO (Last In, First Out) data structure. The last element pushed is the first popped. Think: browser back button, undo operations, call stack.
Core Structure
text
Stack:
data[]
top = -1
push(val): data[++top] = val
pop(): return data[top--]
peek(): return data[top]
isEmpty(): return top == -1
Core Operations
| Operation | Description | Time | Space |
|---|---|---|---|
| push(val) | Add to top | O(1) | O(1) |
| pop() | Remove from top | O(1) | O(1) |
| peek() | View top without removing | O(1) | O(1) |
| isEmpty() | Check if empty | O(1) | O(1) |
Implementations
| Backing Structure | Notes |
|---|---|
| Array | Fixed or dynamic size, cache-friendly |
| Linked List | Dynamic size, pointer overhead |
text
// Array-backed
push(val): arr[++top] = val
pop(): return arr[top--]
// LinkedList-backed
push(val): node = Node(val); node.next = head; head = node
pop(): val = head.value; head = head.next; return val
Valid Parentheses
Push open brackets, pop and match on close brackets.
text
isValid(s):
stack = []
for ch in s:
if ch in '([{': stack.push(ch)
else:
if stack.isEmpty(): return false
if !matches(stack.pop(), ch): return false
return stack.isEmpty()
| Time | Space | |
|---|---|---|
| Complexity | O(n) | O(n) |
Evaluate Expression (Postfix)
text
evalPostfix(tokens):
stack = []
for token in tokens:
if isNumber(token):
stack.push(token)
else:
b = stack.pop()
a = stack.pop()
stack.push(apply(a, token, b))
return stack.pop()
| Time | Space | |
|---|---|---|
| Complexity | O(n) | O(n) |
Monotonic Stack
Stack that maintains elements in increasing or decreasing order. Used for "next greater/smaller element" problems.
text
nextGreater(arr):
stack = []
result[0..n] = -1
for i from 0 to n:
while stack not empty and arr[stack.top()] < arr[i]:
idx = stack.pop()
result[idx] = arr[i]
stack.push(i)
return result
| Time | Space | |
|---|---|---|
| Complexity | O(n) | O(n) |
Each element is pushed and popped at most once — total O(n) even with the inner while loop.
Common Interview Patterns
| Pattern | Problem Examples |
|---|---|
| Matching/balancing | Valid parentheses, HTML tag validation |
| Monotonic stack | Next greater element, daily temperatures |
| Expression evaluation | Postfix, infix-to-postfix conversion |
| DFS simulation | Tree/graph traversal without recursion |
| Undo/redo mechanics | Text editor, browser history |
Quick Reference
| Stack | |
|---|---|
| Order | LIFO |
| Insert | push → top |
| Remove | pop ← top |
| Peek | top element |
| Overflow | Push on full stack |
| Underflow | Pop on empty stack |