PYTHON PROGRAMMING:Day 16: Advanced Data Structures

In Days 5 through 7 you learned lists, tuples, and dictionaries — the everyday containers Python gives you out of the box. Those structures handle most beginner and intermediate work beautifully. But some problems need a more specialized shape: undo buttons, print queues, word counts, or "always give me the smallest item next."

Advanced data structures are purpose-built containers. Each one is optimized for a specific access pattern — adding at one end, removing from another, counting occurrences, or always returning the minimum value. Python's standard library includes several of these ready to use, and you can also build your own when you need full control.

Think of it this way: a list is a Swiss Army knife — versatile, but not always the fastest tool for every job. A stack is a plate dispenser at a buffet. A queue is the checkout line at a grocery store. Choosing the right structure makes your code simpler and often faster.

What You Will Learn in This Chapter

By the end of this tutorial you will be able to:

• Explain the difference between stacks (LIFO) and queues (FIFO)
• Implement stacks and queues using Python lists
• Use collections.deque for efficient double-ended operations
• Count items with collections.Counter
• Group data with collections.defaultdict
• Use heapq for priority queues (always get the smallest item)
• Choose the right structure for a given problem
• Avoid common performance mistakes with lists used as queues

Estimated time: 50 minutes reading + 25 minutes practice

Stacks — Last In, First Out (LIFO)

A stack works like a stack of plates. You add a plate on top (push), and when you take one off, you always take the top plate (pop). The last item you put in is the first one you take out — Last In, First Out (LIFO).

Real-world uses:

• Undo in a text editor — each action is pushed; undo pops the most recent one
• Browser back button — each page visit is pushed; back pops to the previous page
• Function call stack — Python itself uses a stack to track which function called which

Building a Stack with a List

Python lists already support stack operations at the end:

stack = []

# push — add to the top
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)          # [1, 2, 3]

# peek — look at the top without removing
print(stack[-1])      # 3

# pop — remove and return the top
top = stack.pop()
print(top)            # 3
print(stack)          # [1, 2]

Output:

[1, 2, 3]
3
3
[1, 2]

append() and pop() at the end of a list are both O(1) — constant time. That makes lists an excellent stack implementation in Python.

A Reusable Stack Class

When you want clear method names and safety checks, wrap the list in a class:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Test the stack
stack = Stack()
stack.push("first")
stack.push("second")
stack.push("third")
print(f"Top item: {stack.peek()}")    # third
print(f"Popped: {stack.pop()}")       # third
print(f"Size now: {stack.size()}")    # 2

Output:

Top item: third
Popped: third
Size now: 2

Walkthrough:

1. push() calls append() — adds to the end (the "top" of the stack).
2. peek() reads items[-1] without removing anything.
3. pop() removes from the end — always the most recently pushed item.
4. is_empty() prevents errors when popping from an empty stack.

Queues — First In, First Out (FIFO)

A queue works like a line at a coffee shop. The first person in line is the first person served. You add at the back (enqueue) and remove from the front (dequeue) — First In, First Out (FIFO).

Real-world uses:

• Print jobs — documents print in the order they were submitted
• Task schedulers — background jobs run in arrival order
• Message queues — chat apps deliver messages in order

Building a Queue — and Why Lists Are Tricky

You can build a queue with a list, but there is a catch:

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)       # add to the back

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)  # remove from the front
        return None

    def front(self):
        if not self.is_empty():
            return self.items[0]
        return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Test the queue
queue = Queue()
queue.enqueue("Alice")
queue.enqueue("Bob")
queue.enqueue("Carol")
print(f"Front: {queue.front()}")      # Alice
print(f"Dequeue: {queue.dequeue()}")  # Alice
print(f"Front now: {queue.front()}")  # Bob

Output:

Front: Alice
Dequeue: Alice
Front now: Bob

Why this works but is slow: pop(0) removes from the front of a list, which forces Python to shift every remaining element one position left. For a queue with thousands of items, that gets expensive. For learning and small programs, it is fine. For production code, use deque instead.

deque — The Right Tool for Queues

collections.deque (pronounced "deck," short for double-ended queue) supports fast append and pop from both ends:

from collections import deque

# Create a deque
tasks = deque(["email boss", "buy milk", "walk dog"])

# Add to the back (enqueue)
tasks.append("call dentist")
print(tasks)
# deque(['email boss', 'buy milk', 'walk dog', 'call dentist'])

# Remove from the front (dequeue)
next_task = tasks.popleft()
print(f"Doing: {next_task}")
print(tasks)
# deque(['buy milk', 'walk dog', 'call dentist'])

# Also works as a stack — pop from the right
tasks.append("urgent fix")
urgent = tasks.pop()
print(f"Urgent: {urgent}")

Output:

deque(['email boss', 'buy milk', 'walk dog', 'call dentist'])
Doing: email boss
deque(['buy milk', 'walk dog', 'call dentist'])
Urgent: urgent fix

Both append()/pop() and appendleft()/popleft() are O(1) on a deque. When you need a queue in real code, reach for deque — not a plain list.

Counter — Counting Things Automatically

collections.Counter is a dictionary specialized for counting. Pass it any iterable and it tallies occurrences:

from collections import Counter

votes = ["apple", "banana", "apple", "cherry", "apple", "banana"]
counts = Counter(votes)
print(counts)
# Counter({'apple': 3, 'banana': 2, 'cherry': 1})

print(counts["apple"])       # 3
print(counts.most_common(2)) # [('apple', 3), ('banana', 2)]

Output:

Counter({'apple': 3, 'banana': 2, 'cherry': 1})
3
[('apple', 3), ('banana', 2)]

Counter behaves like a dictionary — accessing a missing key returns 0 instead of raising KeyError. That alone saves you from writing if key in dict: dict[key] += 1 else: dict[key] = 1 over and over.

defaultdict — Dictionaries with Default Values

collections.defaultdict creates a dictionary that automatically creates a default value for missing keys:

from collections import defaultdict

# Group words by their first letter
words = ["apple", "avocado", "banana", "blueberry", "cherry"]
by_letter = defaultdict(list)

for word in words:
    by_letter[word[0]].append(word)

print(dict(by_letter))
# {'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}

Output:

{'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}

Without defaultdict, you would need:

by_letter = {}
for word in words:
    letter = word[0]
    if letter not in by_letter:
        by_letter[letter] = []
    by_letter[letter].append(word)

defaultdict(list) calls list() automatically whenever you access a key that does not exist yet, giving you an empty list ready to append to.

heapq — Priority Queues

Sometimes you do not want the first item — you want the smallest (or largest) item. A heap (priority queue) always gives you the minimum element efficiently.

Python's heapq module works on a regular list, maintaining the heap property internally:

import heapq

tasks = []
heapq.heappush(tasks, (3, "low priority"))
heapq.heappush(tasks, (1, "urgent!"))
heapq.heappush(tasks, (2, "medium"))

# Always pops the smallest priority number first
while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"[{priority}] {task}")

Output:

[1] urgent!
[2] medium
[3] low priority

We store tuples (priority, task) because Python compares tuples element by element — lower priority number comes out first. If two items have the same priority, Python compares the second element (the string).

heapq is ideal for schedulers, Dijkstra's algorithm, "find the K largest/smallest" problems, and anywhere you repeatedly need the minimum value from a changing collection.

Choosing the Right Structure

When in doubt, start with a list or dict — they cover 90% of cases. Reach for specialized structures when you hit a specific pattern repeatedly or notice performance problems.

Putting It Together — Browser History Simulator

class Browser:
    def __init__(self):
        self.history = []       # stack for back button
        self.current = None

    def visit(self, url):
        if self.current:
            self.history.append(self.current)
        self.current = url
        print(f"Visiting: {url}")

    def back(self):
        if self.history:
            self.current = self.history.pop()
            print(f"Back to: {self.current}")
        else:
            print("No history to go back to")

browser = Browser()
browser.visit("google.com")
browser.visit("python.org")
browser.visit("schoolabe.com")
browser.back()
browser.back()

Output:

Visiting: google.com
Visiting: python.org
Visiting: schoolabe.com
Back to: python.org
Back to: google.com

Each visit() pushes the previous page onto the stack. Each back() pops the most recent previous page. This is exactly how real browser history works.

Common Mistakes

Mistake 1: Using list.pop(0) for large queues

# Slow for large queues — O(n) per dequeue
items.pop(0)

# Fast — O(1) per dequeue
from collections import deque
items = deque(items)
items.popleft()

Mistake 2: Forgetting to check if a stack/queue is empty

# Crashes with IndexError on empty list
value = stack.pop()

# Safe
if stack:
    value = stack.pop()
else:
    print("Stack is empty")

Mistake 3: Using a list when you need a heap

# Works but inefficient — O(n log n) every sort
tasks.sort()
next_task = tasks.pop(0)

# Efficient — O(log n) per push/pop
import heapq
heapq.heappush(tasks, priority)
next_task = heapq.heappop(tasks)

Mistake 4: Confusing stack and queue direction

Remember: stack = add and remove from the same end (top). Queue = add at one end (back), remove from the other (front).

Practice Exercises

Exercise 1: Implement a function is_balanced(s) that checks whether parentheses in a string are balanced — "(())" is balanced, "(()" is not. Use a stack.

Exercise 2: Simulate a printer queue. Add five print jobs, process them one at a time with deque, and print each job name as it prints.

Exercise 3: Given a paragraph of text, use Counter to find the five most common words.

Exercise 4: Build a task scheduler with heapq where lower numbers mean higher priority. Add four tasks and process them in priority order.

→ See all Python practice exercises with solutions

What Comes Next — Day 17: Basic Algorithms

You now have specialized containers for organizing data. Next you will learn algorithms — step-by-step procedures for searching, sorting, and solving problems efficiently. The data structure you choose and the algorithm you apply work together.

Day 17 covers:

• Sorting algorithms (bubble sort, selection sort)
• Searching (linear search, binary search)
• Understanding algorithm efficiency with Big O notation
• When to use built-in Python tools vs writing your own

→ Continue to Day 17: Basic Algorithms

Chapter navigation

• Previous: Day 15: Exception Handling
• Next: Day 17: Basic Algorithms
• Python Quiz: Take the Python quiz
• All Python exercises: Explore Python exercises