Beginner·1 min read
Stacks
Master the LIFO principle with array and linked list implementations.
Stacks
A stack follows Last In, First Out (LIFO) - like a pile of plates.
``
Push(10), Push(20), Push(30):
┌─────┐
│ 30 │ ← Top (peek/pop from here)
├─────┤
│ 20 │
├─────┤
│ 10 │
└─────┘
`
Core Operations
Header Operation Description Time
Header push(x) Add x to top O(1) pop() Remove and return top O(1) peek() Return top without removing O(1) isEmpty() Check if stack is empty O(1)
Implementations
Array-based: Use a list with append/pop from end. Simple and cache-friendly.
Linked-list-based: Push/pop at head. No capacity limit.
Applications
- Expression evaluation: Convert infix to postfix, evaluate postfix
- Balanced parentheses: Push '(', pop on ')', check empty
- Function call stack: Recursion uses the system stack
- Undo/redo: Text editors, Photoshop
- Backtracking: DFS, maze solving
- Browser history: Back button
Infix to Postfix (Shunting Yard)
`
Infix: (3 + 4) × 5 - 6
Postfix: 3 4 + 5 × 6 -
``
Rules:
- Output numbers directly
- Push '(' onto stack
- On ')', pop until '('
- On operator, pop higher-precedence operators first, then push
Code Example
python
# Stack using Python list
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Pop from empty stack")
return self.items.pop()
def peek(self):
if self.is_empty():
raise IndexError("Peek from empty stack")
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
def __str__(self):
return f"Stack(bottom→top): {self.items}"
# Balance checker
def is_balanced(expression):
stack = Stack()
pairs = {')': '(', ']': '[', '}': '{'}
for char in expression:
if char in '([{':
stack.push(char)
elif char in ')]}':
if stack.is_empty() or stack.pop() != pairs[char]:
return False
return stack.is_empty()
print(is_balanced("({[()]})")) # True
print(is_balanced("({[)]}")) # False
# Postfix evaluator
def eval_postfix(expr):
stack = Stack()
for token in expr.split():
if token.isdigit():
stack.push(int(token))
else:
b, a = stack.pop(), stack.pop()
if token == '+': stack.push(a + b)
elif token == '-': stack.push(a - b)
elif token == '*': stack.push(a * b)
elif token == '/': stack.push(int(a / b))
return stack.pop()
print(eval_postfix("3 4 + 5 * 6 -")) # 29Practice Problems
- 01Implement a min-stack that returns the minimum element in O(1)
- 02Evaluate a mathematical expression given as a string
- 03Sort a stack using only one additional stack