Stacks vs Queues - Learning Module

Loading content...

0/276

When to Use Queues

Mastering Queue Selection

If stacks embody the principle of recency, queues embody the principle of fairness. A queue says: "The element that has been waiting longest deserves to be processed next."

This seemingly simple principle has profound implications. It governs how operating systems schedule processes, how networks deliver packets, how web servers handle requests, and how algorithms find shortest paths. The FIFO discipline isn't just one option among many—it's often the only option that produces correct results.

This page will develop your intuition for queue problems. We'll explore the comprehensive landscape of scenarios where queues shine, understanding not just that they work, but why they must work.

The fundamental insight is this: Queues excel whenever processing order must match arrival order, or when all items at one 'distance' must be handled before items further away. This manifests in task scheduling, breadth-first traversal, message passing, and simulation of real-world waiting lines.

What You Will Master

You'll learn the precise conditions that signal 'use a queue here', explore the categories of problems where queues are optimal, understand why FIFO is essential for each category, and develop the pattern recognition that makes queue selection instinctive.

The Universal Queue Signal

Before exploring specific categories, let's establish the universal patterns that signal 'queue territory'.

The Core Question

Ask yourself: "Does this problem require processing items in the order they arrived, or processing all items at distance N before any at distance N+1?"

If yes, you need FIFO, which means you need a queue.

This manifests in several forms:

Fair scheduling: Items should be served in arrival order—no cutting in line
Wave propagation: Effects spread outward level by level
Shortest path finding: Closer nodes before farther ones
Order preservation: Output sequence should match input sequence
Buffering: Temporary storage that releases items in order

Queue Selection Signals

•"First come, first served" — Any fair scheduling or processing requirement
•"Process level by level" — Breadth-first traversal, level-order processing
•"Find the shortest path" — Unweighted graphs where FIFO guarantees minimum distance
•"Preserve the order" — Output must match input sequence
•"Buffer until ready" — Temporary storage with predictable release order
•"Spread outward from source" — Simulation, propagation effects
•"Wait your turn" — Any system modeling real-world waiting lines

The Fairness and Distance Tests

Two quick tests for queue suitability: (1) The Fairness Test: Should older items be processed before newer ones? (2) The Distance Test: Should all items at distance N be processed before any at distance N+1? If either is yes, you need a queue.

Breadth-First Search and Level-Order Traversal

Breadth-First Search (BFS) is perhaps the most iconic queue application. It's not merely that queues can implement BFS—they're the only structure that correctly implements it.

Why Queues Are Mandatory for BFS

BFS explores a graph or tree level by level:

First, visit the starting node
Then, visit all nodes 1 step away
Then, visit all nodes 2 steps away
And so on...

For this ordering to work:

Nodes discovered first (closer to start) must be visited before nodes discovered later
Nodes at the same distance must all be visited before nodes at greater distance

This is precisely FIFO semantics:

Discovery order = enqueue order
FIFO ensures earlier-discovered (closer) nodes are dequeued first

The Invariant

At any moment during BFS:

The queue contains only nodes at distances d and d+1 from the start
All distance-d nodes appear before all distance-(d+1) nodes (FIFO preserves this)
Nodes at distance < d have already been processed

This invariant guarantees level-by-level processing.

bfs_traversal.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from collections import deque
 
def bfs_levels(root):
    """
    BFS traversal returning nodes organized by level.
    
    Queue invariant: contains nodes at current level followed by
    nodes at next level. FIFO ensures level-by-level processing.
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)  # Nodes at current level
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()  # FIFO: oldest (closest) first
            current_level.append(node.value)
            
            # Enqueue children (next level)
            for child in node.children:
                queue.append(child)
        
        result.append(current_level)
    
    return result
 
# For tree:
#         A
#        /|\
#       B C D
#      /|   |
#     E F   G
#
# BFS levels: [[A], [B, C, D], [E, F, G]]
# 
# Trace:
# Initial queue: [A]
# Process A, enqueue B, C, D -> queue: [B, C, D]
# Process B, enqueue E, F -> queue: [C, D, E, F]
# Process C -> queue: [D, E, F]
# Process D, enqueue G -> queue: [E, F, G]
# Process E, F, G (all are leaves) -> queue: []

BFS Applications

•Level-order tree traversal: Visit all nodes at each depth before going deeper
•Finding minimum depth: First leaf encountered is at minimum depth
•Connected components: Explore all reachable nodes from a source
•Shortest path in unweighted graphs: BFS finds it automatically
•Word ladder problems: Minimum transformations between words
•Social network distance: Minimum 'degrees of separation' between people

Shortest Path in Unweighted Graphs

One of the most powerful properties of BFS is that it automatically finds shortest paths in unweighted graphs. This isn't a special feature—it's a direct consequence of FIFO ordering.

Why FIFO Guarantees Shortest Paths

When all edges have equal weight (or no weight, meaning each step costs 1):

The first time you reach a node, you've found the shortest path to it
This is because FIFO ensures you process all distance-d nodes before any distance-(d+1) nodes
Therefore, you can't reach a node via a longer path before a shorter one

The Proof Intuition

The source is at distance 0 (enqueued first)
When we process the source, we enqueue its neighbors (distance 1)
FIFO ensures we process all distance-1 nodes before any distance-2 nodes
When we process a distance-1 node, we enqueue its unvisited neighbors (distance 2)
This continues, maintaining the invariant: we always process shorter distances first

Contrast with DFS (Stack)

If we used a stack instead, we'd get depth-first behavior:

We might reach a node via a long, winding path before a direct path
The first discovery wouldn't be the shortest path
We'd need extra tracking to find the actual shortest path

With BFS (queue), shortest path is free.

shortest_path_bfs.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from collections import deque
 
def shortest_path(graph: dict, start, end):
    """
    Find shortest path in unweighted graph using BFS.
    
    BFS guarantees: the first time we reach a node, we've found
    the shortest path, because FIFO processes nodes in order
    of their distance from the start.
    """
    if start == end:
        return [start]
    
    # Queue stores (node, path_to_node)
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        node, path = queue.popleft()
        
        for neighbor in graph.get(node, []):
            if neighbor == end:
                # First time reaching end = shortest path
                return path + [neighbor]
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # No path exists
 
# Example graph (undirected):
# A -- B -- C
# |    |
# D -- E -- F
#
# graph = {
#     'A': ['B', 'D'],
#     'B': ['A', 'C', 'E'],
#     'C': ['B'],
#     'D': ['A', 'E'],
#     'E': ['B', 'D', 'F'],
#     'F': ['E']
# }
#
# shortest_path(graph, 'A', 'F') -> ['A', 'B', 'E', 'F'] or ['A', 'D', 'E', 'F']
# (both are length 3, both are shortest paths)

Only for Unweighted (or Equal-Weighted) Graphs!

BFS finds shortest paths only when all edges have equal weight. For weighted graphs with different edge costs, you need Dijkstra's algorithm (using a priority queue, not a regular queue) or Bellman-Ford.

Task Scheduling and Fair Processing

Real-world systems constantly face the problem: "Multiple tasks are waiting to be processed. Which one should we handle next?" When fairness or order preservation matters, the answer is a queue.

Why Queues for Scheduling

Consider these scenarios:

Print jobs: You submit a document to print. You expect it to print after all earlier jobs finish, not to be indefinitely delayed by later jobs.
Web server requests: Users send HTTP requests. A fair server processes them in order—later users don't cut in front of earlier ones.
Customer service: A ticket system assigns support tickets to agents. Oldest tickets should be addressed first to limit maximum wait time.

In all cases, FIFO is the natural model for fairness. No task waits indefinitely while newer tasks keep jumping ahead.

Round-Robin Scheduling

Operating systems often use round-robin scheduling, a queue-based approach:

Ready processes wait in a queue
The CPU takes the front process and runs it for a time quantum
If not finished, the process returns to the back of the queue
Repeat

This ensures every process gets regular CPU time, and the maximum wait is bounded.

round_robin.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from collections import deque
 
class Process:
    def __init__(self, pid: int, burst_time: int):
        self.pid = pid
        self.remaining_time = burst_time
        self.arrival_time = 0
        self.completion_time = 0
 
def round_robin_scheduler(processes: list, time_quantum: int):
    """
    Simulate round-robin CPU scheduling using a queue.
    
    Queue invariant: contains all ready processes in the order
    they should receive CPU time. FIFO ensures fair rotation.
    """
    queue = deque(processes)
    current_time = 0
    schedule = []  # Log of which process ran when
    
    while queue:
        # Dequeue next process (FIFO: whoever waited longest)
        process = queue.popleft()
        
        # Determine how long to run
        run_time = min(time_quantum, process.remaining_time)
        
        # Record the execution
        schedule.append({
            'pid': process.pid,
            'start': current_time,
            'duration': run_time
        })
        
        # Update state
        current_time += run_time
        process.remaining_time -= run_time
        
        if process.remaining_time > 0:
            # Not finished: return to back of queue
            queue.append(process)
        else:
            # Finished!
            process.completion_time = current_time
    
    return schedule
 
# Example:
# P1: 10 units, P2: 4 units, P3: 6 units
# Time quantum: 3 units
#
# Schedule:
# P1 runs 0-3 (7 remaining)
# P2 runs 3-6 (1 remaining)
# P3 runs 6-9 (3 remaining)
# P1 runs 9-12 (4 remaining)
# P2 runs 12-13 (0 remaining - done!)
# P3 runs 13-16 (0 remaining - done!)
# P1 runs 16-19 (1 remaining)
# P1 runs 19-20 (0 remaining - done!)

Queue-Based Scheduling Applications

•CPU scheduling (Round-Robin): Fair time-sharing among processes
•Print spooling: Documents print in submission order
•Web request handling: Requests served in arrival order
•Call center queues: Callers served in order of call time
•Ticket systems: Support tickets assigned to agents fairly
•Job queues in distributed systems: Tasks processed in order

Message Queues and Buffering

In distributed systems and asynchronous programming, message queues are fundamental infrastructure. They decouple producers from consumers, allowing systems to handle varying loads and failures gracefully.

Why Queues for Message Passing

When system A sends messages to system B:

Messages may arrive faster than B can process them
B may be temporarily unavailable
Order may matter for message semantics

A queue solves all three problems:

Buffering: Messages wait in the queue until B can handle them
Persistence: Messages survive temporary consumer outages
Ordering: FIFO guarantees messages are processed in send order

Order Preservation

For many applications, message order is critical:

Bank transactions: Deposit, then withdrawal must process in order
Event sourcing: Events must replay in original order to reconstruct state
Chat messages: Messages should display in conversation order
Logs: Log entries must maintain chronological order

FIFO queues guarantee this ordering automatically.

message_queue.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from collections import deque
import threading
import time
 
class SimpleMessageQueue:
    """
    Thread-safe in-memory message queue.
    
    Demonstrates FIFO semantics for message passing between
    producers and consumers.
    """
    
    def __init__(self, max_size=1000):
        self.queue = deque()
        self.lock = threading.Lock()
        self.max_size = max_size
        self.not_empty = threading.Condition(self.lock)
        self.not_full = threading.Condition(self.lock)
    
    def enqueue(self, message):
        """Add message to queue (producer calls this)"""
        with self.not_full:
            while len(self.queue) >= self.max_size:
                self.not_full.wait()  # Block if full
            
            self.queue.append(message)
            self.not_empty.notify()  # Wake up waiting consumer
    
    def dequeue(self, timeout=None):
        """Remove and return oldest message (consumer calls this)"""
        with self.not_empty:
            while len(self.queue) == 0:
                if not self.not_empty.wait(timeout):
                    return None  # Timeout
            
            message = self.queue.popleft()  # FIFO: oldest first
            self.not_full.notify()  # Wake up waiting producer
            return message
 
# Usage pattern:
# Producer: queue.enqueue({"event": "user_signup", "user_id": 123})
# Consumer: message = queue.dequeue()
#
# FIFO guarantees: messages processed in the order they were sent
# This is critical for maintaining data consistency

Real-World Message Queues

Production systems use message queue services like RabbitMQ, Apache Kafka, Amazon SQS, or Redis. These all provide FIFO semantics (with varying guarantees) and add features like persistence, multiple consumers, and partitioning for scale.

Simulation of Real-World Queuing Systems

Queues are used extensively to simulate real-world waiting line systems. This application is so common that an entire field—queuing theory—exists to mathematically analyze such systems.

When to Simulate with Queues

Any scenario involving:

Arrivals: Entities arriving at a system
Waiting: Entities waiting for service
Service: Entities being processed by limited servers

Examples include:

Bank teller lines
Airport security checkpoints
Traffic flow at intersections
Hospital emergency rooms
Call centers
Computer network congestion

Why Queues Model These Accurately

Real waiting lines are FIFO by nature (in most cultures). To accurately simulate:

Arrivals enqueue into the waiting line
When a server is free, they dequeue the next customer
Processing time may vary, but serving order follows FIFO

Using a stack would give completely unrealistic results—late arrivals wouldn't wait at all while early arrivals wait indefinitely.

queue_simulation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from collections import deque
import random
 
class BankSimulation:
    """
    Simulate a bank with multiple tellers and customer arrivals.
    
    Queue models the waiting line. FIFO ensures fair service order.
    """
    
    def __init__(self, num_tellers: int):
        self.customer_queue = deque()
        self.tellers = [None] * num_tellers  # None = free
        self.current_time = 0
        self.total_wait_time = 0
        self.customers_served = 0
    
    def customer_arrives(self, customer_id: int, service_time: int):
        """A customer joins the queue"""
        self.customer_queue.append({
            'id': customer_id,
            'arrival_time': self.current_time,
            'service_time': service_time
        })
    
    def update(self):
        """Advance simulation by one time unit"""
        self.current_time += 1
        
        # Check each teller
        for i in range(len(self.tellers)):
            if self.tellers[i] is not None:
                self.tellers[i]['remaining'] -= 1
                if self.tellers[i]['remaining'] == 0:
                    # Teller finishes with current customer
                    self.tellers[i] = None
            
            if self.tellers[i] is None and self.customer_queue:
                # Teller is free and someone is waiting
                customer = self.customer_queue.popleft()  # FIFO!
                wait_time = self.current_time - customer['arrival_time']
                self.total_wait_time += wait_time
                self.customers_served += 1
                
                self.tellers[i] = {
                    'customer': customer['id'],
                    'remaining': customer['service_time']
                }
    
    def average_wait_time(self):
        if self.customers_served == 0:
            return 0
        return self.total_wait_time / self.customers_served
 
# Typical simulation usage:
# sim = BankSimulation(num_tellers=3)
# for minute in range(480):  # 8-hour day
#     if random.random() < 0.3:  # ~30% chance of arrival each minute
#         sim.customer_arrives(minute, random.randint(2, 10))
#     sim.update()
# print(f"Average wait: {sim.average_wait_time():.1f} minutes")

Queuing Theory Applications

Queuing theory helps answer questions like: 'How many tellers do we need to keep average wait under 5 minutes?' or 'What happens to wait times if arrival rate increases 20%?' The FIFO queue is the fundamental building block of these analyses.

Stream Processing and Order-Preserving Pipelines

When processing data streams, maintaining order is often critical. Queues serve as the connective tissue between processing stages, ensuring data flows through in the correct sequence.

The Pipeline Pattern

Many systems process data in stages:

Ingest: Data arrives from external sources
Transform: Data is cleaned, enriched, transformed
Aggregate: Data is combined with other data
Output: Results are delivered

Between each stage, queues buffer data while maintaining order.

Why Order Matters

Log processing: Events must be analyzed in chronological order
Video streaming: Frames must play in capture order
Financial transactions: Trades must be processed in timestamp order
Sensor data: Readings must correlate with their actual time

Rate Matching

Queues also handle rate mismatches between pipeline stages:

Producer is fast, consumer is slow → queue absorbs bursts
Consumer catches up during lulls
Overall throughput averages out

pipeline_processing.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from collections import deque
 
class OrderPreservingPipeline:
    """
    A multi-stage processing pipeline using queues.
    
    Each stage has an input queue. FIFO semantics ensure
    data maintains its original order through all stages.
    """
    
    def __init__(self):
        self.stages = []
        self.queues = []  # Queue between each stage
    
    def add_stage(self, processor):
        """Add a processing stage to the pipeline"""
        self.stages.append(processor)
        self.queues.append(deque())
    
    def submit(self, item):
        """Submit an item to the first stage"""
        if self.queues:
            self.queues[0].append(item)
    
    def process_step(self):
        """Process one item from each stage (if available)"""
        for i, stage in enumerate(self.stages):
            input_queue = self.queues[i]
            output_queue = self.queues[i + 1] if i + 1 < len(self.queues) else None
            
            if input_queue:
                item = input_queue.popleft()  # FIFO: preserve order
                result = stage(item)
                
                if output_queue is not None:
                    output_queue.append(result)
                else:
                    # Last stage: emit result
                    yield result
    
    def run(self, items):
        """Process all items through the pipeline"""
        results = []
        
        # Submit all items
        for item in items:
            self.submit(item)
        
        # Process until all queues empty
        while any(q for q in self.queues):
            for result in self.process_step():
                results.append(result)
        
        return results
 
# Usage:
# pipeline = OrderPreservingPipeline()
# pipeline.add_stage(lambda x: x.upper())       # Stage 1: uppercase
# pipeline.add_stage(lambda x: x.strip())       # Stage 2: strip
# pipeline.add_stage(lambda x: f"[{x}]")        # Stage 3: wrap
#
# results = pipeline.run(["  hello  ", "  world  "])
# -> ["[HELLO]", "[WORLD]"]
# Order is preserved through all stages!

Real-World Stream Processing

Production stream processing systems like Apache Kafka, Apache Flink, and AWS Kinesis all use queues (or partitioned logs with queue semantics) to maintain order while enabling parallel processing and fault tolerance.

Summary: The Queue Selection Framework

We've explored the rich landscape of queue-appropriate problems. Let's consolidate this into an actionable framework:

Queue Selection Decision Table
Problem Signal	Queue Use Case	Core FIFO Requirement
Process level by level	BFS / Level-order traversal	All distance-N nodes before distance-(N+1)
Find shortest path	Graph shortest path	Closer nodes processed before farther nodes
First come, first served	Task scheduling	Older items processed before newer
Messages in order	Message queues	Messages delivered in send order
Model waiting lines	Queuing simulation	Service order matches arrival order
Pipeline processing	Stream processing	Data order preserved across stages
Buffer between rates	Rate matching	Items buffered and released in order

Key Takeaways

•Queues embody fairness and order preservation — When arrival order matters, use a queue.
•BFS is the canonical queue algorithm — Level-order traversal requires FIFO to work correctly.
•Shortest path in unweighted graphs comes free with BFS — FIFO guarantees optimal paths.
•Fair scheduling is inherently FIFO — Round-robin and first-come-first-served need queues.
•Message queues maintain order across asynchronous systems — Critical for event sourcing and distributed systems.
•Real-world waiting lines are naturally FIFO — Queue simulations model reality accurately.
•Pipelines use queues to preserve order between stages — Stream processing relies on FIFO buffering.

Page Complete

You now have a comprehensive understanding of when queues are the right choice. In the next page, we'll synthesize everything—developing the pattern recognition skills to instantly identify whether a problem calls for a stack, a queue, or perhaps something else entirely.