Stacks & Queues - Learn Step by Step

🌟 Level 1: The Basics (Start Here!)

Level 1

What is a Stack? Think of a Stack of Plates! 🍽️

Imagine a stack of plates in a cafeteria. You can only take the top plate, and when you add a new plate, it goes on top. That's exactly how a stack works - Last In, First Out (LIFO)!

🥘

Top (Newest)

↑ Push / Pop ↓

🍲

Plate 3

🍛

Plate 2

🍕

Bottom (Oldest)

Stack Operations:

📥 Push - Add to the top
📤 Pop - Remove from the top
👀 Peek/Top - Look at the top without removing
❓ isEmpty - Check if stack is empty

Creating Your First Stack in Python 🐍

# Python's list works as a stack!
stack = []   # Empty stack (like empty plate holder)

# Push: Add plates to the top
stack.append("Plate 1")   # Stack: [Plate 1]
stack.append("Plate 2")   # Stack: [Plate 1, Plate 2]
stack.append("Plate 3")   # Stack: [Plate 1, Plate 2, Plate 3]

# Pop: Take the top plate
top_plate = stack.pop()   # Returns "Plate 3"
# Stack now: [Plate 1, Plate 2]

# Peek: Look at top without removing
if stack:   # Always check if not empty!
    current_top = stack[-1]   # "Plate 2"

# Check if empty
is_empty = len(stack) == 0
                                

What is a Queue? Think of a Line at a Store! 🛒

A queue is like waiting in line at a grocery store. First person in line gets served first. That's First In, First Out (FIFO)!

👶

Rear (Newest)

←

👩‍👦

Person 3

👨‍💼

Person 2

👵

Front (Oldest)

→ Exit

Creating Your First Queue in Python 🐍

from collections import deque

# Create a queue (deque is efficient for queues)
queue = deque()

# Enqueue: Join the line at the back
queue.append("Person 1")   # Queue: [Person 1]
queue.append("Person 2")   # Queue: [Person 1, Person 2]
queue.append("Person 3")   # Queue: [Person 1, Person 2, Person 3]

# Dequeue: Serve the first person
first = queue.popleft()   # Returns "Person 1"
# Queue now: [Person 2, Person 3]

# Peek at front without removing
if queue:
    front_person = queue[0]   # "Person 2"
                                

⚠️ Common Mistake #1: Stack Overflow

# ❌ WRONG - No size check!
def recursive_function(n):
    return recursive_function(n + 1)   # Infinite recursion!
                            

Why it happens: Each function call adds to the call stack. Without a base case, the stack grows until memory runs out!

✅ The Right Way

# ✅ CORRECT - Always have a base case
def recursive_function(n):
    if n >= 100:   # Base case
        return n
    return recursive_function(n + 1)
                            

🎮 Try It Yourself: Stack Operations

Practice push and pop operations on a visual stack!

🤔 Why Should You Care About Stacks & Queues?

↩️

Browser Back Button

Your browser history is a stack! When you click back, you pop the current page and return to the previous one.

⌨️

Undo/Redo Operations

Every Ctrl+Z (undo) pops an action from the stack. Ctrl+Y (redo) pushes it to another stack!

📞

Call Center Queue

Customer service calls are handled in a queue - first caller gets helped first (FIFO).

🖨️

Print Queue

Documents sent to a printer wait in a queue. First document sent prints first!

🎮

Game Matchmaking

Players waiting for a match are in a queue. First to join gets matched first!

📱

App Navigation

Mobile app screens use a stack. Press back to pop the current screen!

🎨 Level 2: Common Patterns

Level 2

Pattern 1: Balanced Parentheses (Stack)

Check if brackets are properly matched - a classic stack problem!

How it Works

1

Opening bracket: Push to stack

2

Closing bracket: Pop and check if matches

3

End: Stack should be empty

Balanced Parentheses Checker

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in '([{':
            # Opening bracket - push to stack
            stack.append(char)
        elif char in ')]}':
            # Closing bracket - check if matches
            if not stack:
                return False   # No opening bracket
            if stack.pop() != pairs[char]:
                return False   # Mismatch
    
    return len(stack) == 0   # All matched if empty

# Examples
print(is_balanced("(())"))    # True ✅
print(is_balanced("([)]"))    # False ❌
                                

Pattern 2: BFS with Queue

Breadth-First Search explores level by level using a queue!

Level Order Tree Traversal

from collections import deque

def level_order(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])   # Start with root
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        # Process all nodes at current level
        for _ in range(level_size):
            node = queue.popleft()   # Get from front
            current_level.append(node.val)
            
            # Add children to queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result
                                

💪 Practice Problems (From Easy to Hard)

Easy

Problem 1: Implement Min Stack

Design a stack that supports push, pop, and retrieving the minimum element in O(1) time.

Think About It First! 🤔

Hint: What if you kept track of the minimum at each level?

Show Solution

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []   # Track minimums
    
    def push(self, val):
        self.stack.append(val)
        # Push new min or current min
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        else:
            self.min_stack.append(self.min_stack[-1])
    
    def pop(self):
        self.stack.pop()
        self.min_stack.pop()
    
    def get_min(self):
        return self.min_stack[-1]
                                    

Problem 2: Implement Queue using Stacks

Create a queue using only two stacks.

Strategy Hint 💡

One stack for input, one for output. Transfer when needed!

Show Solution

class MyQueue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []
    
    def enqueue(self, x):
        # Always push to input stack
        self.input_stack.append(x)
    
    def dequeue(self):
        # If output stack is empty, transfer all
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        
        return self.output_stack.pop()
                                    

🚀 Level 3: Advanced Techniques

Advanced

Monotonic Stack

A stack where elements are always in increasing or decreasing order!

Next Greater Element

def next_greater_element(nums):
    # Find next greater element for each number
    result = [-1] * len(nums)
    stack = []   # Monotonic decreasing stack
    
    for i, num in enumerate(nums):
        # Pop all smaller elements
        while stack and nums[stack[-1]] < num:
            idx = stack.pop()
            result[idx] = num   # Found greater element!
        
        stack.append(i)
    
    return result

# Example: [4, 5, 2, 10]
# Result:  [5, 10, 10, -1]
                                

Circular Queue

A queue that wraps around - efficient use of fixed space!

class CircularQueue:
    def __init__(self, k):
        self.queue = [None] * k
        self.size = k
        self.front = 0
        self.rear = -1
        self.count = 0
    
    def enqueue(self, value):
        if self.count == self.size:
            return False   # Queue full
        
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = value
        self.count += 1
        return True
    
    def dequeue(self):
        if self.count == 0:
            return None   # Queue empty
        
        value = self.queue[self.front]
        self.front = (self.front + 1) % self.size
        self.count -= 1
        return value
                        

📖 Quick Reference Guide

Stack vs Queue Operations

Operation	Stack (LIFO)	Queue (FIFO)	Time
Add Element	Push (top)	Enqueue (rear)	O(1)
Remove Element	Pop (top)	Dequeue (front)	O(1)
View Next	Peek/Top	Front	O(1)
Check Empty	isEmpty	isEmpty	O(1)

🎯 When to Use Stack

✅ Matching parentheses
✅ Function calls (recursion)
✅ Undo operations
✅ Expression evaluation
✅ Backtracking algorithms

🎯 When to Use Queue

✅ BFS traversal
✅ Task scheduling
✅ Message passing
✅ Handling requests
✅ Level-order traversal

🔧 Common Patterns

Monotonic Stack: Next greater/smaller
Min/Max Stack: Track extremes
Double-ended Queue: Sliding window
Priority Queue: Heap implementation