Part 3: Stacks and Queues – Core Concepts and Python Implementations

🚀 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

🔧 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.

💬 What’s your favorite stack/queue trick? Got stuck on a BFS problem? Drop your questions below! 🔁📤