🚀 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.
Top comments (0)