Building a Circular Queue in Java: Array Ring Buffers and Modulo Math

Suppose you are building the virtual waiting room for a high-demand concert ticket sale.

100,000 fans join the queue simultaneously. Fairness demands First-In-First-Out (FIFO) processing: the fan who joined at 10:00:00 AM gets to purchase tickets before the fan who joined at 10:00:01 AM.

If you store fans inside a simple array and process each ticket purchase by removing index 0 (array.remove(0)), every single ticket transaction forces the server to copy and shift all remaining 99,999 array elements left by one slot.

Your ticket service CPU hits 100% utilization, and processing 100,000 tickets takes hours instead of seconds.

To process items in $O(1)$ constant time without shifting elements, high-performance systems use circular array ring buffers.

---

Why You Need This in Real Life

FIFO queues drive modern asynchronous infrastructure:

• Message Queues: Systems like RabbitMQ, Kafka partition channels, and AWS SQS buffer message tasks between microservices.
• Thread Pool Work Queues: Java’s ThreadPoolExecutor stores pending Runnable tasks inside a queue until worker threads become available.
• Network Packet Buffers: Router network interface cards queue incoming TCP/IP packets in hardware ring buffers.

---

FIFO Queue Mental Model

Elements enter at the tail index pointer and exit from the head index pointer.

ENQUEUE "A", "B", "C"                      DEQUEUE
                                              ^
  head                             tail       |
   |                                |      Returns "A"
   v                                v
+------+------+------+------+------+
| "A"  | "B"  | "C"  | null | null |
+------+------+------+------+------+

---

How Ring Buffers Fix Array Shifts

Instead of shifting elements left when index 0 is dequeued, a ring buffer leaves remaining elements in place and advances the head index pointer.

After dequeuing "A":

              head                 tail
               |                    |
               v                    v
+------+------+------+------+------+
| null | "B"  | "C"  | null | null |
+------+------+------+------+------+

When tail reaches the last index slot of the array, it wraps around to index 0 using modulo arithmetic:

$\text{nextIndex} = (\text{currentIndex} + 1) \pmod{\text{capacity}}$

WRAP-AROUND STATE (Capacity 5):

  tail                              head
   |                                 |
   v                                 v
+------+------+------+------+------+
| "E"  | null | null | "C"  | "D"  |
+------+------+------+------+------+

---

Building MyCircularQueue<T> Code

Here is our circular array queue implementation:

import java.util.NoSuchElementException;

public class MyCircularQueue<T> {
    private Object[] elements;
    private int head = 0;
    private int tail = 0;
    private int size = 0;
    private int capacity;

    public MyCircularQueue(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("Capacity must be positive");
        }
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }

    public boolean enqueue(T item) {
        if (isFull()) {
            return false; // Ring buffer at max capacity
        }
        elements[tail] = item;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        T item = (T) elements[head];
        elements[head] = null; // Clear reference for GC!
        head = (head + 1) % capacity;
        size--;
        return item;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return (T) elements[head];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public int size() {
        return size;
    }
}

---

Expanding Wrapped Ring Buffers

To make a circular queue dynamic (unbounded), enqueue can resize the backing array when full.

However, copying wrapped elements to a expanded array requires care. You cannot use a simple System.arraycopy(oldArray, 0, newArray, 0, size) if tail has wrapped around behind head.

You must unroll the circular buffer sequentially:

private void resize() {
    int newCapacity = capacity * 2;
    Object[] newElements = new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[(head + i) % capacity];
    }
    this.elements = newElements;
    this.head = 0;
    this.tail = size;
    this.capacity = newCapacity;
}

---

Quick Summary

• Simple array queues suffer $O(N)$ shift costs on dequeue operations.
• Ring buffers eliminate element shifting by advancing head and tail pointers via modulo arithmetic.
• Dynamic ring buffers must unroll wrapped pointer indices when expanding array capacity.

References & Further Reading

1. OpenJDK Repository. OpenJDK 21 Source Code: java.util.HashMap. GitHub.
2. Cormen, T. H., et al. (2022). Introduction to Algorithms (4th Edition) — Chapter 11: Hash Tables. MIT Press.
3. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (Hashing). Addison-Wesley.

---