The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Circular Queues

Next ►
►

The Queue from the previous lesson grows without bound: as long as there is memory, it accepts elements. But many systems work with fixed memory: a network buffer, the keyboard buffer, an application's log of recent events. For those cases there is a classic and remarkably elegant implementation: the circular queue (or ring buffer), a FIFO queue built on a fixed-capacity array whose indices, upon reaching the end, "wrap around" and reuse the slots freed at the front. In this lesson we will build the CircularQueue class with modular arithmetic, solve the puzzle of telling "full" apart from "empty", and apply it to TaskFlow: the log of the system's last N events. We will also connect the idea with an old friend: the CircularList from module 2.

Contents

  1. The problem: a queue on a fixed array
  2. The circular idea: modular arithmetic
  3. The puzzle: full or empty?
  4. The CircularQueue class
  5. Visual trace of the modular advance
  6. Ring buffers in the real world and the link to CircularList
  7. TaskFlow: EventLog, the last N events

The problem: a queue on a fixed array

Suppose all we have is a fixed-capacity array, say 5 slots, and we want a FIFO queue on top of it. The first naive attempt: enqueue by advancing a back index and dequeue by advancing a front index:

enqueue(A), enqueue(B), enqueue(C):      dequeue() twice:

indices:  0    1    2    3    4          indices:  0    1    2    3    4
        [ A ][ B ][ C ][   ][   ]                [ · ][ · ][ C ][   ][   ]
          ↑front         ↑back                               ↑front ↑back

After dequeuing A and B, slots 0 and 1 are free... but back keeps marching to the right. When back reaches slot 4, the queue will look "full" with two wasted slots on the left. There are two bad alternatives:

  • Shifting the elements to the left on every dequeue: that is exactly the O(n) pop(0) we have spent two modules avoiding.
  • Rejecting insertions even though there is room: unacceptable waste in a buffer.

The good solution: when back runs past the right edge, it continues at slot 0. The array stops being a strip and becomes, conceptually, a ring.

The circular idea: modular arithmetic

No magic is needed to "wrap around" — the modulo operator % is enough. If the capacity is c, the index after i is:

next_index = (i + 1) % c

With c = 5: after 3 comes 4, and after 4 comes (4 + 1) % 5 = 0. The modulo turns the line of indices into a circle:

graph LR
    I0((0)) --> I1((1)) --> I2((2)) --> I3((3)) --> I4((4)) --> I0

Sound familiar? It is the same idea as the CircularList from module 2, where the last node pointed back to the first (last.next) and the TaskDispatcher rotated indefinitely. There, the circle was built with links between nodes; here it is built with arithmetic over array indices. Same concept, different implementation — and this version, being a contiguous fixed-size array, is more compact in memory and friendlier to the processor cache, which is why it is the one chosen in drivers and embedded systems.

The puzzle: full or empty?

There is a famous subtlety. If we represent the queue with only the front and back indices, the condition front == back is ambiguous: it holds both when the queue is empty and when it is full (the back has come all the way around and caught up with the front). There are two classic solutions:

Strategy How it works Cost
Element counter Keep size: empty if size == 0, full if size == capacity One extra integer; very clear code
Sacrificed slot Always keep one gap free: full if (back + 1) % c == front One slot wasted; indices only

We will use the counter, which also gives us size() for free (it is in the contract). You will see the sacrificed-slot strategy in low-level C code, where avoiding an extra field matters; it is worth recognizing when you read it.

With a counter, we don't even need to store back: it can be derived from front and size:

back = (front + size) % capacity   # slot where the NEXT element will land

Less state to maintain means fewer invariants to break: a design principle we already applied in the CircularList (we only stored self.last).

The CircularQueue class

class CircularQueue:
    """Fixed-capacity FIFO queue on an array, with modular indices.

    Honors the queue contract (enqueue, dequeue, front, is_empty,
    size) and adds is_full() and capacity(), specific to the fixed size.
    """

    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self._data = [None] * capacity     # fixed array: created once
        self._capacity = capacity
        self._front = 0                    # index of the oldest element
        self._size = 0                     # number of occupied slots

    def enqueue(self, element):
        if self.is_full():
            raise OverflowError("enqueue onto a full queue")
        back = (self._front + self._size) % self._capacity
        self._data[back] = element         # write into the back slot
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from an empty queue")
        element = self._data[self._front]
        self._data[self._front] = None     # release the reference (hygiene)
        self._front = (self._front + 1) % self._capacity   # modular advance
        self._size -= 1
        return element

    def front(self):
        if self.is_empty():
            raise IndexError("front of an empty queue")
        return self._data[self._front]

    def is_empty(self):
        return self._size == 0

    def is_full(self):
        return self._size == self._capacity

    def size(self):
        return self._size

    def capacity(self):
        return self._capacity

Points that deserve a detailed explanation:

  • Everything is O(1), no fine print: enqueue and dequeue perform one write, one addition, and one modulo. There are no shifts (the great sin of SlowQueue) and no nodes to create (unlike the linked Queue). There are no resizes either: the memory is reserved exactly once in __init__.
  • self._data[self._front] = None in dequeue: it is not required for correctness, but if the slot keeps the reference to the object, Python cannot free it from memory until the slot is overwritten. In slowly rotating queues that keeps "ghost" objects alive. It is the same kind of hygiene as the dangling references from module 2.
  • OverflowError when full: a fixed queue must decide its saturation policy. Raising an exception is the honest default policy; in the TaskFlow example we will see the other common policy (discard the oldest). What matters is that it is an explicit decision.

Visual trace of the modular advance

Let's follow a CircularQueue(4) operation by operation. We mark F under the front index and compute back = (front + size) % 4 (the slot of the next enqueue):

Operation Array [0][1][2][3] front size back (next) Returns
(initial) [ · ][ · ][ · ][ · ] 0 0 0 —
enqueue(A) [ A ][ · ][ · ][ · ] 0 1 1 —
enqueue(B) [ A ][ B ][ · ][ · ] 0 2 2 —
enqueue(C) [ A ][ B ][ C ][ · ] 0 3 3 —
dequeue() [ · ][ B ][ C ][ · ] 1 2 3 A
enqueue(D) [ · ][ B ][ C ][ D ] 1 3 0 —
enqueue(E) [ E ][ B ][ C ][ D ] 1 4 — (full) —
dequeue() [ E ][ · ][ C ][ D ] 2 3 1 B
dequeue() [ E ][ · ][ · ][ D ] 3 2 1 C

The two bold rows tell the whole story:

  • After enqueue(D), the next back is (1 + 3) % 4 = 0: it has wrapped around. That is why E lands in slot 0, which A left free. No slot is wasted, nothing is shifted.
  • With the queue full (size == 4), front is 1 and the "back" slot would coincide with it: exactly the ambiguity the counter resolves.

Also notice that the FIFO order is preserved perfectly even though physically E sits "before" B in the array: the logical order is dictated by front and the modular advance, not by physical position. It is the ADT/implementation distinction from module 1 in its most graphic form.

Ring buffers in the real world and the link to CircularList

The professional name for this structure is ring buffer (circular buffer), and it appears the moment you scratch any system:

  • Keyboard and network buffers: the hardware produces bytes at its own rate; the software consumes them at another. A fixed-size ring buffer absorbs the difference without ever requesting memory (crucial in a driver, where you cannot "ask for more memory").
  • Streaming audio and video: the player reads from the front while the download writes at the back; if the download gets too far ahead, it waits (queue full); if it falls behind, the player waits (queue empty).
  • Recent-event logs: system journals, avionics black boxes, the "last N" history of any application: the old is overwritten automatically.

Comparison with its cousin from module 2:

CircularList (module 2) CircularQueue (this lesson)
Circularity achieved by The last node linking to the first The % operator over indices
Capacity Unlimited (grows node by node) Fixed (array reserved upfront)
Memory One Node per element, scattered Contiguous and compact
Typical use Infinite rotation (TaskDispatcher round-robin) Bounded producer/consumer buffer

TaskFlow: EventLog, the last N events

In TaskFlow we want a "recent activity" panel: the last 100 events of the system (task created, completed, reassigned...). We do not want to store them all — a database will handle that — only the N most recent, in constant memory. It is the perfect use case for the ring buffer with a discard the oldest policy:

class EventLog:
    """Stores the last N TaskFlow events in fixed memory.

    Saturation policy: when full, the oldest event is discarded
    to make room for the new one (unlike the default OverflowError).
    """

    def __init__(self, limit=100):
        self._events = CircularQueue(limit)

    def record(self, task, action):
        if self._events.is_full():
            self._events.dequeue()              # discards the oldest: O(1)
        self._events.enqueue({
            "task_id": task["id"],
            "title": task["title"],
            "action": action,
        })

    def recent_activity(self):
        """Returns the events from oldest to newest (O(n))."""
        recent = []
        for _ in range(self._events.size()):
            event = self._events.dequeue()
            recent.append(event)
            self._events.enqueue(event)         # rotates the queue one full turn
        return recent


# --- Usage ---
log = EventLog(limit=3)                         # 3 to see it with little noise
t1 = {"id": 1, "title": "Design logo", "priority": 2, "status": "pending"}
t2 = {"id": 2, "title": "Configure server", "priority": 1, "status": "pending"}

log.record(t1, "created")
log.record(t2, "created")
log.record(t2, "in_progress")
log.record(t2, "completed")                     # full! discards "t1 created"

for e in log.recent_activity():
    print(f"task {e['task_id']}: {e['action']}")
# task 2: created
# task 2: in_progress
# task 2: completed

Two decisions worth commenting on:

  • record implements "discard the old" by composing the public contract (is_full + dequeue + enqueue), without touching the guts of CircularQueue. The policy lives in the TaskFlow layer; the structure stays generic and reusable.
  • recent_activity uses the full rotation trick: it dequeues each element and enqueues it back, so that after size() turns the queue is exactly as it was. It is the way to traverse a queue while respecting its contract (without reaching into the internal array).

You may remember that BoundedHistory from module 3 did something similar ("keep the last k") paying an O(n) pop(0). EventLog now does everything in O(1)... at the cost of fixing the capacity upfront. In lesson 04-05 we will see the third way, the most Pythonic one: deque(maxlen=k).

Common Mistakes and Tips

  • Forgetting the % in some advance: if you write self._front += 1 without the modulo, the queue works wonderfully... until the first wrap-around, and then it indexes outside the array (IndexError) or reads garbage. "Second lap" bugs are treacherous because short tests never catch them: always test with more operations than capacity.
  • Using front == back as the emptiness test with only two indices: that is the full/empty ambiguity. Pick a strategy (counter or sacrificed slot) and be consistent; with a counter, don't compare indices at all.
  • Confusing capacity with size: capacity() is how many fit; size() is how many are there. The saturation code (is_full) compares them against each other, and mixing them up produces queues that "fill up" at the halfway point.
  • Choosing the wrong saturation policy: exception, discard the new, or discard the old? For a user's command buffer, losing the new is usually worse; for an activity log, losing the old is exactly what you want. There is no universal policy: document the one you chose.
  • Tip: when debugging a circular queue, always print the triple (front, size, capacity) next to the array. Seeing front = 3, size = 2 over [E][·][·][D] teaches you more than twenty prints of the array alone.

Exercises

Exercise 1: trace with a full wrap-around

On a CircularQueue(3), run in order: enqueue(1), enqueue(2), dequeue(), enqueue(3), enqueue(4), dequeue(), dequeue(), enqueue(5). Build the trace table (array, front, size, returned value) after each operation. Which physical slot does 5 end up in, and why?

Exercise 2: last_enqueued

Add a last_enqueued() method to CircularQueue that returns (without removing) the most recent element, raising IndexError if the queue is empty. Careful: the last element's slot is not (front + size) % capacity (that is the next one). Do it in O(1).

Exercise 3: resize preserving the order

Write a resize(new_capacity) method that replaces the internal array with one of the new capacity, preserving the elements in FIFO order and leaving front = 0. It must reject with ValueError a capacity smaller than size(). Hint: do not copy slots by physical position; relocate following the logical order, with modular indices starting at the old front.

Solutions

Solution 1:

Operation [0][1][2] front size Returns
enqueue(1) [1][·][·] 0 1 —
enqueue(2) [1][2][·] 0 2 —
dequeue() [·][2][·] 1 1 1
enqueue(3) [·][2][3] 1 2 —
enqueue(4) [4][2][3] 1 3 —
dequeue() [4][·][3] 2 2 2
dequeue() [4][·][·] 0 1 3
enqueue(5) [4][5][·] 0 2 —

4 landed in slot 0 because (1 + 2) % 3 = 0 (first wrap-around), and 5 lands in slot 1 because, with front = 0 and size = 1, the next back is (0 + 1) % 3 = 1. The logical order (front→back) is 4, 5, even though 4 sits physically first: FIFO is dictated by the indices, not the position.

Solution 2:

def last_enqueued(self):
    if self.is_empty():
        raise IndexError("last_enqueued on an empty queue")
    # The next gap is (front + size) % capacity;
    # the last occupied slot is the one BEFORE that gap:
    index = (self._front + self._size - 1) % self._capacity
    return self._data[index]

The - 1 inside the modulo also handles the wrap-around case: with front = 2, size = 1, capacity = 3, the last element is at (2 + 1 - 1) % 3 = 2, correct. In Python, even (0 - 1) % 3 gives 2 (Python's modulo is never negative), so the formula is safe.

Solution 3:

def resize(self, new_capacity):
    if new_capacity < self._size:
        raise ValueError("the current elements do not fit")
    new_data = [None] * new_capacity
    for i in range(self._size):
        # i-th element in logical order, starting at the front:
        new_data[i] = self._data[(self._front + i) % self._capacity]
    self._data = new_data
    self._capacity = new_capacity
    self._front = 0             # the logical order is "unrolled" from 0

The key is the index (self._front + i) % self._capacity: it walks the elements in true FIFO order, even when they are split into two physical stretches (end of the array + beginning). Copying the array as-is (self._data[:]) would be a mistake: it would leave empty slots mixed in the middle and break the order.

Conclusion

The circular queue solves the fixed-memory queue problem: two indices advancing with modular arithmetic ((i + 1) % capacity), a counter that removes the full/empty ambiguity, and every operation in O(1) without ever shifting an element. It is the "array" version of the idea we already saw with links in the CircularList, and it is the structure behind the ring buffers that power drivers, streaming, and activity logs — including our EventLog of TaskFlow's last N events. So far, all our queues share one dogma: the oldest comes out. But TaskFlow has priority 1 tasks that cannot wait their turn behind twenty routine tasks. It is time to break the dogma sensibly: in the next lesson, the priority queue, where dequeuing means "give me the most urgent" — and where we will finally extract what the min-stack from module 3 could only look at.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved