dsa / dsa-complexity
20 mins
DSA Module 5: Stack LIFO & Monotonic Stack
Why This Matters: Stacks operate on Last-In, First-Out (LIFO) mechanics, ideal for expression evaluation.
## Stacks (LIFO) & Parentheses Matching
Pushing and popping elements from a LIFO stack.
```python
def is_valid_parentheses(s: str) -> bool:
stack = []
pairs = {")": "(", "}": "{", "]": "["}
for char in s:
if char in pairs:
top = stack.pop() if stack else '#'
if pairs[char] != top:
return False
else:
stack.append(char)
return len(stack) == 0
```
MENTAL MODEL & MEMORY LAYOUT
STACK LIFO OPERATIONS:
Push '(' ──► [ '(' ]
Push '{' ──► [ '{', '(' ]
Pop '}' ──► Matches '{'! Stack becomes [ '(' ] COMMON PITFALLS TO AVOID
- Popping from an empty stack (raises IndexError). Always check `if stack:`.
Parentheses Validation Pattern
stack = []
stack.append('(')
top = stack.pop() # '('Pushes opening brackets and pops to verify matching closing brackets.
CONCEPT MASTERY CHECKPOINT
Which data structure property describes a Stack?
NEXT RECOMMENDED LESSON
DSA Module 6: Hashing & Hash Tables
Challenge: Check if string parentheses are balanced using stack.