Queue & Circular Queue

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 2 Time to complete: ~20 minutes

The FIFO Principle
Why a Plain List Makes a Bad Queue
Implementing a Queue with collections.deque
The Circular Queue
Summary & Next Steps

1. The FIFO Principle

A queue is a collection where the first item added is the first one removed — First In, First Out (FIFO). Picture a checkout line: whoever joined first gets served first, and new arrivals join at the back, not the front.

enqueue(1) → [1]
enqueue(2) → [1, 2]
enqueue(3) → [1, 2, 3]
dequeue()  → returns 1, queue is now [2, 3]   ← the FIRST one in was the FIRST one out

2. Why a Plain List Makes a Bad Queue

A queue removes from the front. As Module 2 established, removing from the front of a Python list is O(n) — every remaining element must shift left by one to fill the gap:

queue = [1, 2, 3, 4, 5]
first = queue.pop(0)      # O(n) — shifts every remaining element left

For a single dequeue this is harmless, but a queue processed repeatedly (which is the normal use case — see Module 9's BFS) turns an intended O(1) operation into O(n) every time, silently degrading an entire algorithm's complexity. This is exactly the kind of hidden cost Module 1 Chapter 6 warned you to look for.

3. Implementing a Queue with collections.deque

Python's standard library provides collections.deque ("double-ended queue," covered fully in Chapter 4), which supports O(1) operations at both ends — making it the correct default choice for a queue in Python:

from collections import deque
 
queue = deque()
 
queue.append(1)          # enqueue — O(1)
queue.append(2)
queue.append(3)
print(queue)               # deque([1, 2, 3])
 
first = queue.popleft()   # dequeue — O(1), unlike list.pop(0)
print(first)                 # 1
print(queue)                  # deque([2, 3])

A thin wrapper, mirroring Chapter 1's Stack class, makes the queue's intent explicit in code that uses it:

class Queue:
    def __init__(self):
        self._items = deque()
 
    def enqueue(self, item):
        self._items.append(item)
 
    def dequeue(self):
        return self._items.popleft()
 
    def is_empty(self):
        return len(self._items) == 0
 
    def __len__(self):
        return len(self._items)

4. The Circular Queue

A circular queue is a fixed-size queue implemented over a fixed-size array, where the "front" and "rear" positions wrap around to the beginning once they reach the end — reusing freed-up space instead of leaving it empty. This matters for fixed-capacity buffers (streaming data, producer/consumer buffers) where allocating a new array on every operation would be wasteful.

class CircularQueue:
    def __init__(self, capacity):
        self._data = [None] * capacity
        self._capacity = capacity
        self._front = 0
        self._size = 0
 
    def enqueue(self, item):
        if self._size == self._capacity:
            raise OverflowError("Queue is full")
        rear = (self._front + self._size) % self._capacity   # wrap around
        self._data[rear] = item
        self._size += 1
 
    def dequeue(self):
        if self._size == 0:
            raise IndexError("Queue is empty")
        item = self._data[self._front]
        self._front = (self._front + 1) % self._capacity        # wrap around
        self._size -= 1
        return item
 
    def is_full(self):
        return self._size == self._capacity
 
    def is_empty(self):
        return self._size == 0

capacity = 4, data = [None, None, None, None], front = 0, size = 0

enqueue(1) → data = [1, None, None, None], size = 1
enqueue(2) → data = [1, 2, None, None],    size = 2
dequeue()  → returns 1,  front = 1,          size = 1
enqueue(3) → data = [1, 2, 3, None],        size = 2
enqueue(4) → data = [1, 2, 3, 4],           size = 3
enqueue(5) → rear = (1 + 3) % 4 = 0 → data = [5, 2, 3, 4], size = 4  ← wrapped around

The rear position "wraps" back to index 0 once it would otherwise run past the end of the fixed array — that wraparound (% capacity) is the entire idea behind "circular."

5. Summary & Next Steps

Key Takeaways

A queue is FIFO — the first item added is the first removed, unlike a stack's LIFO.
list.pop(0) is O(n) — never use a plain list for a queue in a loop; use collections.deque, which supports O(1) operations at both ends.
A circular queue reuses a fixed-size array by wrapping the front/rear indices with the modulo operator, avoiding wasted space in fixed-capacity buffers.

Concept Check

Why does list.pop(0) cost O(n), and why does that matter more inside a loop than for a single call?
What Python standard-library structure gives O(1) operations at both the front and back, and why does that make it the right default for queues?
What does the modulo operation (% capacity) accomplish in the circular queue's enqueue/dequeue?

Next Chapter

→ Chapter 4: Deque

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index