We use cookies to enhance your experience on the site

Stacks and Queues - Equipment Organization

Welcome back, @name! Darwin here with the last data structures before recursion.

Imagine organizing an expedition:

Backpack stack - you pack things one on top of another. To get something from the bottom, you must first take out everything from the top (LIFO - Last In, First Out)
Watering hole queue - animals line up in a queue. The first animal in line is served first (FIFO - First In, First Out)

These are exactly stacks and queues - fundamental data structures!

Stack - LIFO

A Stack is a data structure where the last added element is the first to be removed (LIFO - Last In, First Out).

Safari Analogy: A stack of plates - you take a plate from the top (the last one added), not from the bottom.

Stack Operations

| Operation | Complexity | Description | |-----------|-----------|-------------| | push(x) | O(1) | Add element to the top | | pop() | O(1) | Remove and return element from the top | | peek() / top() | O(1) | View element at the top (without removing) | | is_empty() | O(1) | Check if the stack is empty | | size() | O(1) | Return the number of elements |

Stack Implementation in Python

1# Method 1: Python list (simplest!)
2class Stack:
3    """Stack implementation using a list"""
4
5    def __init__(self):
6        self.items = []
7
8    def push(self, item):
9        """Add element to the top - O(1)"""
10        self.items.append(item)
11
12    def pop(self):
13        """Remove and return element from the top - O(1)"""
14        if self.is_empty():
15            raise IndexError("Stack is empty!")
16        return self.items.pop()
17
18    def peek(self):
19        """View element at the top - O(1)"""
20        if self.is_empty():
21            raise IndexError("Stack is empty!")
22        return self.items[-1]
23
24    def is_empty(self):
25        """Check if the stack is empty - O(1)"""
26        return len(self.items) == 0
27
28    def size(self):
29        """Return the number of elements - O(1)"""
30        return len(self.items)
31
32    def __str__(self):
33        """String representation"""
34        return f"Stack({self.items})"
35
36# Usage example
37equipment_stack = Stack()
38equipment_stack.push("Tent")
39equipment_stack.push("Sleeping Bag")
40equipment_stack.push("Flashlight")
41equipment_stack.push("Map")
42
43print(equipment_stack)  # Stack(['Tent', 'Sleeping Bag', 'Flashlight', 'Map'])
44print(f"Top: {equipment_stack.peek()}")  # Map (last added)
45print(f"Removing: {equipment_stack.pop()}")  # Map
46print(f"Now top: {equipment_stack.peek()}")  # Flashlight
47print(f"Size: {equipment_stack.size()}")  # 3

Safari example - Tracking the exploration path:

1def track_exploration_path():
2    """Track the expedition path using a stack"""
3    path = Stack()
4
5    # Explore the jungle
6    path.push("Base Camp")
7    print(f"Entering: Base Camp")
8
9    path.push("Northern Forest")
10    print(f"Entering: Northern Forest")
11
12    path.push("River")
13    print(f"Entering: River")
14
15    # We return the same way (backtracking)
16    print("\nReturning along the same path:")
17    while not path.is_empty():
18        location = path.pop()
19        print(f"Leaving: {location}")
20
21# Output:
22# Entering: Base Camp
23# Entering: Northern Forest
24# Entering: River
25# Returning along the same path:
26# Leaving: River
27# Leaving: Northern Forest
28# Leaving: Base Camp

Stack Applications

Undo/Redo in editors - each action on a stack
Browser history - the "Back" button
Call stack - function calls in a program
Expression parsing - checking brackets, RPN notation
DFS (Depth-First Search) - search algorithm
Backtracking - backtracking in algorithms

Example - Checking Balanced Brackets

1def is_balanced(expression):
2    """
3    Check if brackets are balanced
4    Example: "({[]})" -> True, "({[}])" -> False
5    """
6    stack = Stack()
7    pairs = {')': '(', ']': '[', '}': '{'}
8
9    for char in expression:
10        if char in '([{':
11            # Opening bracket - push onto stack
12            stack.push(char)
13        elif char in ')]}':
14            # Closing bracket - check if it matches
15            if stack.is_empty():
16                return False  # No opening bracket
17            if stack.pop() != pairs[char]:
18                return False  # Doesn't match
19            # Matches - continue
20
21    # Stack should be empty at the end
22    return stack.is_empty()
23
24# Tests
25print(is_balanced("({[]})"))  # True
26print(is_balanced("({[}])"))  # False
27print(is_balanced("((()))"))  # True
28print(is_balanced("(()"))     # False
29
30# Safari example
31code = "species = {name: 'Python', data: [1, 2, 3]}"
32print(f"Code: {code}")
33print(f"Balanced: {is_balanced(code)}")  # True

Queue - FIFO

A Queue is a data structure where the first added element is the first to be removed (FIFO - First In, First Out).

Safari Analogy: A queue of animals at the watering hole - the first in line is served first.

Queue Operations

| Operation | Complexity | Description | |-----------|-----------|-------------| | enqueue(x) | O(1) | Add element to the end | | dequeue() | O(1) | Remove and return element from the front | | front() / peek() | O(1) | View element at the front | | is_empty() | O(1) | Check if the queue is empty | | size() | O(1) | Return the number of elements |

Queue Implementation in Python

1from collections import deque
2
3class Queue:
4    """Queue implementation using deque"""
5
6    def __init__(self):
7        # deque = double-ended queue - O(1) operations from both ends!
8        self.items = deque()
9
10    def enqueue(self, item):
11        """Add element to the end - O(1)"""
12        self.items.append(item)
13
14    def dequeue(self):
15        """Remove and return element from the front - O(1)"""
16        if self.is_empty():
17            raise IndexError("Queue is empty!")
18        return self.items.popleft()  # popleft() from deque = O(1)!
19
20    def front(self):
21        """View element at the front - O(1)"""
22        if self.is_empty():
23            raise IndexError("Queue is empty!")
24        return self.items[0]
25
26    def is_empty(self):
27        """Check if the queue is empty - O(1)"""
28        return len(self.items) == 0
29
30    def size(self):
31        """Return the number of elements - O(1)"""
32        return len(self.items)
33
34    def __str__(self):
35        """String representation"""
36        return f"Queue({list(self.items)})"
37
38# Usage example
39species_queue = Queue()
40species_queue.enqueue("Python")
41species_queue.enqueue("Leo")
42species_queue.enqueue("Elephas")
43
44print(species_queue)  # Queue(['Python', 'Leo', 'Elephas'])
45print(f"First: {species_queue.front()}")  # Python
46print(f"Processing: {species_queue.dequeue()}")  # Python (first added)
47print(f"Now first: {species_queue.front()}")  # Leo

WARNING: Do not use Python's list with `pop(0)` for a queue - it's O(n)! Use `deque`!

1# ❌ WRONG - pop(0) is O(n)
2queue = []
3queue.append(1)  # O(1)
4queue.pop(0)     # O(n) - must shift all elements!
5
6# ✅ RIGHT - deque with popleft()
7from collections import deque
8queue = deque()
9queue.append(1)   # O(1)
10queue.popleft()   # O(1) - optimized!

Queue Applications

BFS (Breadth-First Search) - search algorithm
Print queue - print job queue
Task scheduling - task queueing
Buffering - data buffering (e.g., video streaming)
Simulations - simulations (e.g., store queues)

Example - Discovery Processing System Simulation

1def process_discoveries():
2    """Simulate processing discoveries in order of submission"""
3    discovery_queue = Queue()
4
5    # Discovery submissions
6    print("=== DISCOVERY SUBMISSIONS ===")
7    discoveries = ["Python regius", "Panthera leo", "Gorilla gorilla", "Elephas maximus"]
8    for species in discoveries:
9        discovery_queue.enqueue(species)
10        print(f"Submitted: {species}")
11
12    print(f"\nIn queue: {discovery_queue.size()} discoveries\n")
13
14    # Processing in FIFO order
15    print("=== PROCESSING ===")
16    while not discovery_queue.is_empty():
17        current = discovery_queue.dequeue()
18        print(f"Cataloging: {current}")
19        # Processing simulation
20        import time
21        time.sleep(0.5)
22
23    print("\n✓ All discoveries cataloged!")
24
25# Output:
26# === DISCOVERY SUBMISSIONS ===
27# Submitted: Python regius
28# Submitted: Panthera leo
29# Submitted: Gorilla gorilla
30# Submitted: Elephas maximus
31#
32# In queue: 4 discoveries
33#
34# === PROCESSING ===
35# Cataloging: Python regius (first submitted)
36# Cataloging: Panthera leo
37# Cataloging: Gorilla gorilla
38# Cataloging: Elephas maximus
39#
40# ✓ All discoveries cataloged!

Deque (Double-Ended Queue)

A Deque (pronounced "deck") is a queue from both ends - you can add and remove from the front and back!

1from collections import deque
2
3# Create a deque
4dq = deque([1, 2, 3])
5
6# Operations from the right side (like a list)
7dq.append(4)        # [1, 2, 3, 4]
8dq.pop()            # 4, remaining [1, 2, 3]
9
10# Operations from the left side (unique to deque!)
11dq.appendleft(0)    # [0, 1, 2, 3]
12dq.popleft()        # 0, remaining [1, 2, 3]
13
14# Other operations
15dq.extend([4, 5])           # [1, 2, 3, 4, 5]
16dq.extendleft([0, -1])      # [-1, 0, 1, 2, 3, 4, 5]
17dq.rotate(2)                # [4, 5, -1, 0, 1, 2, 3] (rotate right)

Safari example - Recent discoveries tracker

1class RecentDiscoveriesTracker:
2    """Track the last N discoveries"""
3
4    def __init__(self, max_size=5):
5        self.discoveries = deque(maxlen=max_size)  # Automatic removal of old ones!
6
7    def add_discovery(self, species):
8        """Add a discovery (automatically removes oldest if max exceeded)"""
9        self.discoveries.append(species)
10
11    def get_recent(self):
12        """Return recent discoveries (newest first)"""
13        return list(reversed(self.discoveries))
14
15    def __str__(self):
16        return f"Last {len(self.discoveries)} discoveries: {list(self.discoveries)}"
17
18# Usage
19tracker = RecentDiscoveriesTracker(max_size=3)
20tracker.add_discovery("Python")
21tracker.add_discovery("Leo")
22tracker.add_discovery("Elephas")
23print(tracker)  # ['Python', 'Leo', 'Elephas']
24
25tracker.add_discovery("Gorilla")  # Exceeds max - removes Python!
26print(tracker)  # ['Leo', 'Elephas', 'Gorilla']
27
28print(f"Newest first: {tracker.get_recent()}")
29# ['Gorilla', 'Elephas', 'Leo']

Priority Queue

A Priority Queue is a queue where elements are served according to priority, not order of addition.

1import heapq
2
3class PriorityQueue:
4    """Priority queue (lower priority number = higher priority)"""
5
6    def __init__(self):
7        self.heap = []
8        self.counter = 0  # To preserve order for equal priorities
9
10    def enqueue(self, item, priority):
11        """Add element with priority - O(log n)"""
12        # Heapq uses a min-heap (smallest on top)
13        # We add counter to preserve FIFO order for equal priorities
14        heapq.heappush(self.heap, (priority, self.counter, item))
15        self.counter += 1
16
17    def dequeue(self):
18        """Remove and return element with highest priority - O(log n)"""
19        if self.is_empty():
20            raise IndexError("PriorityQueue is empty!")
21        priority, _, item = heapq.heappop(self.heap)
22        return item
23
24    def is_empty(self):
25        """Check if empty - O(1)"""
26        return len(self.heap) == 0
27
28    def size(self):
29        """Return size - O(1)"""
30        return len(self.heap)
31
32# Safari example - Prioritizing species research
33pq = PriorityQueue()
34
35# Add species with priority (1 = highest, 5 = lowest)
36pq.enqueue("Crocodylus niloticus", priority=1)  # Dangerous - priority!
37pq.enqueue("Python regius", priority=3)          # Normal priority
38pq.enqueue("Panthera leo", priority=1)           # Dangerous - priority!
39pq.enqueue("Gorilla gorilla", priority=2)        # Medium priority
40pq.enqueue("Elephas maximus", priority=3)        # Normal priority
41
42print("Research order (by priority):")
43while not pq.is_empty():
44    species = pq.dequeue()
45    print(f"  Researching: {species}")
46
47# Output:
48# Researching: Crocodylus niloticus (priority 1, first added)
49# Researching: Panthera leo (priority 1, second added)
50# Researching: Gorilla gorilla (priority 2)
51# Researching: Python regius (priority 3, first added)
52# Researching: Elephas maximus (priority 3, second added)

Comparing Stack vs Queue vs Deque

| Structure | Adding | Removing | Complexity | Use Case | |-----------|--------|----------|-----------|----------| | Stack | push (top) | pop (top) | O(1) | Undo, Call stack, DFS | | Queue | enqueue (back) | dequeue (front) | O(1) | BFS, Scheduling, Buffering | | Deque | append/appendleft | pop/popleft | O(1) | Sliding window, Recent history | | Priority Queue | enqueue | dequeue (min) | O(log n) | Dijkstra, Task scheduling |

Practical Example - Expedition Planner

1class ExpeditionPlanner:
2    """Expedition planning system using various data structures"""
3
4    def __init__(self):
5        self.path_history = Stack()        # Path history (for backtracking)
6        self.task_queue = Queue()          # Task queue to execute
7        self.recent_discoveries = deque(maxlen=10)  # 10 most recent discoveries
8        self.priority_tasks = PriorityQueue()  # Priority tasks
9
10    def enter_location(self, location):
11        """Enter a location (save in history)"""
12        self.path_history.push(location)
13        print(f"➡️  Entering: {location}")
14
15    def backtrack(self):
16        """Return to the previous location"""
17        if self.path_history.is_empty():
18            print("⚠️  Already at base camp!")
19            return None
20        location = self.path_history.pop()
21        print(f"⬅️  Leaving: {location}")
22        return location
23
24    def add_task(self, task, priority=None):
25        """Add a task (normal or priority)"""
26        if priority is not None:
27            self.priority_tasks.enqueue(task, priority)
28            print(f"📌 Priority task: {task} (priority {priority})")
29        else:
30            self.task_queue.enqueue(task)
31            print(f"📋 Task: {task}")
32
33    def process_next_task(self):
34        """Process the next task (priority first)"""
35        if not self.priority_tasks.is_empty():
36            task = self.priority_tasks.dequeue()
37            print(f"⚡ Executing priority: {task}")
38            return task
39        elif not self.task_queue.is_empty():
40            task = self.task_queue.dequeue()
41            print(f"✓ Executing: {task}")
42            return task
43        else:
44            print("✓ All tasks completed!")
45            return None
46
47    def record_discovery(self, species):
48        """Record a discovery"""
49        self.recent_discoveries.append(species)
50        print(f"🔬 Discovered: {species}")
51
52    def show_recent_discoveries(self, n=5):
53        """Show the last N discoveries"""
54        recent = list(self.recent_discoveries)[-n:]
55        print(f"\n📊 Last {len(recent)} discoveries:")
56        for i, species in enumerate(reversed(recent), 1):
57            print(f"  {i}. {species}")
58
59# Usage
60planner = ExpeditionPlanner()
61
62# Exploration
63planner.enter_location("Northern Forest")
64planner.enter_location("River")
65planner.enter_location("Waterfall")
66
67# Discoveries
68planner.record_discovery("Python regius")
69planner.record_discovery("Panthera leo")
70
71# Tasks
72planner.add_task("Examine water samples")
73planner.add_task("URGENT: Repair communication equipment", priority=1)
74planner.add_task("Create terrain map")
75
76# Processing tasks
77planner.process_next_task()  # URGENT first!
78planner.process_next_task()
79planner.process_next_task()
80
81# Backtracking
82planner.backtrack()
83planner.backtrack()
84planner.backtrack()
85
86# Summary
87planner.show_recent_discoveries()

Practical Exercise

Create a "Safari Command Center":

Stack - Command history (undo capability)
Queue - Research task queue
Priority Queue - Alerts and priority tasks
Deque - Last 5 team locations

Summary

In this lesson you learned:

✅ Stack (LIFO) - last in, first out
✅ Queue (FIFO) - first in, first out
✅ Deque - adding/removing from both ends
✅ Priority Queue - processing by priority
✅ Implementation in Python (list, deque, heapq)
✅ Applications of each structure
✅ Operation complexities
✅ Practical examples

Checkpoint

Before moving on:

[ ] You understand the difference between LIFO and FIFO
[ ] You can implement Stack and Queue
[ ] You know the applications of each structure
[ ] You understand why to use deque instead of list for Queue
[ ] You know when to use Priority Queue
[ ] You can choose the appropriate structure for a given problem

Key takeaway: Stack for backtracking and undo, Queue for BFS and scheduling, Deque for sliding window!

In the next and final lesson of this module Darwin will introduce you to recursion - functions that call themselves! 🔄🌀

Go to CodeWorlds→