🚀 Introduction
Stacks and queues are two of the most fundamental data structures in computer science.
They are the backbone of:
Expression evaluation (infix, postfix)
Backtracking algorithms
Tree and graph traversals
Task scheduling and async operations
In this post, we’ll cover:
✅ What stacks and queues are
✅ Pythonic implementations using list and collections.deque
✅ Real-world problems and patterns
✅ Best practices and interview tips
📦 1️⃣ What is a Stack? (LIFO – Last In, First Out)
Think of a stack of plates — you can only remove or add from the top.
🔹 Basic Operations:
- push: Add to top
- pop: Remove from top
- peek: See top item
- is_empty: Check if empty🔹 Python Implementation:
stack = []
stack.append(1) # push
stack.append(2)
print(stack.pop()) # 2
print(stack[-1]) # peek → 1✅ Python’s list provides all you need for stack operations.
📚 Real-World Stack Use Cases
- Undo/Redo systems
- Backtracking (maze, Sudoku)
- Balanced parentheses checking
- Function call stack (recursion)🔍 Example: Valid Parentheses
def is_valid_parentheses(s):
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in mapping.values():
stack.append(char)
elif char in mapping:
if not stack or stack.pop() != mapping[char]:
return False
return not stack📦 2️⃣ What is a Queue? (FIFO – First In, First Out)
Think of a line at the bank — the first person in is the first one served.
🔹 Basic Operations:
- enqueue: Add to rear
- dequeue: Remove from front
- peek: View front item🔹 Python Implementation with deque:
from collections import deque
queue = deque()
queue.append(1) # enqueue
queue.append(2)
print(queue.popleft()) # dequeue → 1✅ deque is preferred for performance: O(1) operations from both ends.
🧭 Real-World Queue Use Cases
- Breadth-first search (BFS) in trees and graphs
- Task scheduling (OS, threads, async)
- Buffering data streams
- Print job queues🔍 Example: BFS in a Binary Tree
from collections import deque
def bfs(root):
if not root:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)🧪 3️⃣ Interview-Favorite Problems
| Problem | Data Structure | Pattern |
|---|---|---|
| Valid Parentheses | Stack | Matching pairs |
| Min Stack | Stack | Track min values |
| Daily Temperatures | Stack | Monotonic stack |
| BFS Traversal | Queue | Level-order |
| Rotten Oranges | Queue | BFS in grid |
| Design Circular Queue | Queue | Array + Pointers |
🔧 4️⃣ Implementing a Min Stack
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
min_val = val if not self.min_stack else min(val, self.min_stack[-1])
self.min_stack.append(min_val)
def pop(self):
self.stack.pop()
self.min_stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]✅ All operations in O(1) time.
✅ Best Practices
✔️ Use deque for queues and double-ended operations
✔️ Don’t use list.pop(0) for queues — it’s O(n)
✔️ Know stack vs queue behavior clearly — it affects algorithm choice
✔️ Watch out for edge cases: empty stack/queue, null root, etc.
✔️ Practice problems with state tracking and multi-level logic (e.g., BFS + levels)
🧠 Summary
✔️ Stacks (LIFO) and queues (FIFO) solve real-world ordering and traversal problems
✔️ Python provides clean abstractions using list and deque
✔️ Learn core patterns like parentheses validation, BFS, and monotonic stacks
✔️ Mastering these unlocks tree/graph algorithms and many classic interview questions
🔜 Coming Up Next:
👉 Part 4: Hash Maps and Sets – Frequency Maps, Lookups, and Real-World Applications
We’ll cover:
1. Counter, defaultdict, set
Grouping anagrams
Sliding window with hash map
Interview favorites: 2-sum, longest substring, etc.
