DSA · Chapter 15 of 40
Stacks
A stack is a LIFO (last in, first out) structure with push, pop and peek, all O(1). It can be built on an array or a linked list.
Stacks model anything that must be undone in reverse order: function calls, undo history, bracket matching and expression evaluation.
Operations
push adds to the top, pop removes the top, peek reads the top without removing. Popping an empty stack is an error, so always check.
Where it appears
The call stack, browser back history, DFS on graphs, and converting infix expressions to postfix.
Example 1 (python)
stack = []
stack.append(1)
stack.append(2)
print(stack.pop())
print(stack[-1])Output
2
1A Python list works as a stack with append and pop.
Example 2 (python)
def balanced(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in '([{':
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
print(balanced('{[()]}'))Output
TrueBracket matching is the classic stack problem.
Key points
- A stack is LIFO with O(1) push, pop and peek.
- Bracket matching and expression parsing use stacks.
- DFS can be written with an explicit stack.
- Check for an empty stack before popping.
💡 Note: If a problem involves 'most recent' or 'nearest previous', a stack is usually the answer.