icaoberg / Data structures - Queue

Created Sun, 03 May 2026 00:00:00 +0000 Modified Sun, 03 May 2026 09:38:19 -0400

Jupyter Notebook python

Data structures - Queue¶

A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle: the first element added is the first one removed — just like a checkout line at a store.

This notebook covers:

What is a Queue?
The Queue class
Core operations: enqueue, dequeue, peek, is_empty, size
Example: task scheduling simulation

1. What is a Queue?¶

Operation	Description	Time complexity
`enqueue(item)`	Add an item to the back	O(1)
`dequeue()`	Remove and return the front item	O(1)
`peek()`	Return the front item without removing it	O(1)
`is_empty()`	Return `True` if the queue has no items	O(1)
`size()`	Return the number of items	O(1)

Python's built-in collections.deque gives O(1) appends and pops from both ends, making it the ideal backing structure for a queue.

2. The `Queue` class¶

In [1]:

from collections import deque


class Queue:
    """FIFO queue backed by collections.deque."""

    def __init__(self):
        self._data = deque()

    def enqueue(self, item):
        """Add *item* to the back of the queue."""
        self._data.append(item)

    def dequeue(self):
        """Remove and return the front item. Raises IndexError if empty."""
        if self.is_empty():
            raise IndexError("dequeue from an empty queue")
        return self._data.popleft()

    def peek(self):
        """Return the front item without removing it. Raises IndexError if empty."""
        if self.is_empty():
            raise IndexError("peek at an empty queue")
        return self._data[0]

    def is_empty(self):
        """Return True if the queue contains no items."""
        return len(self._data) == 0

    def size(self):
        """Return the number of items in the queue."""
        return len(self._data)

    def __repr__(self):
        items = list(self._data)
        return f"Queue(front={items[0]!r}, size={len(items)})" if items else "Queue(empty)"

    def __str__(self):
        return " <- ".join(str(i) for i in self._data) or "(empty)"

3. Core operations¶

In [2]:

q = Queue()
print("Empty?  ", q.is_empty())
print("Size:   ", q.size())
print("Queue:  ", q)

Empty?   True
Size:    0
Queue:   (empty)

In [3]:

# enqueue three items
for value in ["alpha", "beta", "gamma"]:
    q.enqueue(value)
    print(f"enqueue({value!r})  →  {q}")

enqueue('alpha')  →  alpha
enqueue('beta')  →  alpha <- beta
enqueue('gamma')  →  alpha <- beta <- gamma

In [4]:

print("peek():   ", q.peek())    # front item, queue unchanged
print("size():   ", q.size())
print("Queue:    ", q)

peek():    alpha
size():    3
Queue:     alpha <- beta <- gamma

In [5]:

# dequeue all items
while not q.is_empty():
    item = q.dequeue()
    print(f"dequeue() → {item!r}   remaining: {q}")

dequeue() → 'alpha'   remaining: beta <- gamma
dequeue() → 'beta'   remaining: gamma
dequeue() → 'gamma'   remaining: (empty)

In [6]:

# dequeue from empty queue raises IndexError
try:
    q.dequeue()
except IndexError as e:
    print("Caught:", e)

Caught: dequeue from an empty queue

4. Example: task scheduling simulation¶

The snippet below simulates a simple round-robin task processor: tasks are submitted to a queue and a worker picks them off one by one.

In [7]:

import time
import random

random.seed(42)


def process_task(task):
    """Simulate work by sleeping a short random interval."""
    duration = random.uniform(0.05, 0.15)
    time.sleep(duration)
    return duration


# Submit tasks
scheduler = Queue()
task_names = [f"Task-{i}" for i in range(1, 7)]

print("Submitting tasks...")
for name in task_names:
    scheduler.enqueue(name)
    print(f"  queued  {name}")

print(f"\nQueue size before processing: {scheduler.size()}")
print("\nProcessing tasks (FIFO order):")

total_time = 0.0
while not scheduler.is_empty():
    task = scheduler.dequeue()
    elapsed = process_task(task)
    total_time += elapsed
    print(f"  finished {task:<10}  ({elapsed:.3f}s)  remaining in queue: {scheduler.size()}")

print(f"\nAll tasks complete. Total simulated time: {total_time:.3f}s")

Submitting tasks...
  queued  Task-1
  queued  Task-2
  queued  Task-3
  queued  Task-4
  queued  Task-5
  queued  Task-6

Queue size before processing: 6

Processing tasks (FIFO order):
  finished Task-1      (0.114s)  remaining in queue: 5
  finished Task-2      (0.053s)  remaining in queue: 4
  finished Task-3      (0.078s)  remaining in queue: 3
  finished Task-4      (0.072s)  remaining in queue: 2
  finished Task-5      (0.124s)  remaining in queue: 1
  finished Task-6      (0.118s)  remaining in queue: 0

All tasks complete. Total simulated time: 0.558s

Licensed under the GNU General Public License v2.0 (GPL-2).
You may redistribute and/or modify this work under the terms of GPL-2.
This work is distributed WITHOUT ANY WARRANTY.
Happy computing.