Implement a Queue using an Array

• Circular queue (ring buffer) – a fixed-size array where front and rear index pointers wrap around using the modulo operator, reusing freed slots.
• Enqueue – writes the element at items[rear], then advances rear = (rear + 1) % capacity.
• Dequeue – reads the element at items[front], then advances front = (front + 1) % capacity.
• O(1) enqueue and dequeue – no shifting of elements is ever needed.
• Count variable – a separate count resolves the ambiguity when front == rear, which could mean empty or completely full.

What is an array-backed queue?

A queue is a first-in, first-out (FIFO) data structure. An array-backed queue stores elements in a fixed-size array and uses two index pointers, front and rear, to track the head and tail of the line. Enqueue adds at the rear; dequeue removes from the front.

Why use a circular design instead of shifting?

A naive array queue removes from the front by shifting every remaining element one step left, which costs O(n) per dequeue. The circular queue avoids shifting by advancing the front pointer instead, wrapping around with modulo so freed slots at the front are reused by the rear.

Naive (shift on dequeue):   [_, B, C, D] → shift → [B, C, D, _]  O(n)
Circular (advance pointer):  front moves 0→1→2→...→wrap  O(1)

How do you implement it? (with code)

package com.bank.service;

import java.math.BigDecimal;
import java.util.NoSuchElementException;

public class ChequeQueue {

    private final BigDecimal[] items;
    private final int capacity;
    private int front;
    private int rear;
    private int count;

    public ChequeQueue(int capacity) {
        this.capacity = capacity;
        this.items = new BigDecimal[capacity];
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }

    public void enqueue(BigDecimal amount) {
        if (count == capacity) {
            throw new IllegalStateException("Queue full: cannot accept more cheques");
        }
        items[rear] = amount;
        rear = (rear + 1) % capacity;
        count++;
    }

    public BigDecimal dequeue() {
        if (count == 0) {
            throw new NoSuchElementException("Queue empty: no cheques to process");
        }
        BigDecimal value = items[front];
        items[front] = null;  // help GC
        front = (front + 1) % capacity;
        count--;
        return value;
    }

    public BigDecimal peek() {
        if (count == 0) {
            throw new NoSuchElementException("Queue empty");
        }
        return items[front];
    }

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

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

    public int size() {
        return count;
    }

    public static void main(String[] args) {
        ChequeQueue queue = new ChequeQueue(3);
        queue.enqueue(new BigDecimal("5000"));
        queue.enqueue(new BigDecimal("12000"));
        queue.enqueue(new BigDecimal("7500"));

        System.out.println("Dequeued: " + queue.dequeue());
        System.out.println("Peek: " + queue.peek());
        queue.enqueue(new BigDecimal("9000"));  // reuses freed slot
        System.out.println("Size: " + queue.size());
    }
}

Dequeued: 5000
Peek: 12000
Size: 3

Why keep a separate count variable?

When front == rear, you cannot tell if the queue is empty or completely full just from the pointers. A separate count removes that ambiguity cleanly. An alternative is to waste one slot (capacity minus one usable slots), but the count approach is simpler and wastes no space.

| Approach | Empty check | Full check | Slots usable |
|---|---|---|---|
| Count variable | count == 0 | count == capacity | All slots |
| Waste one slot | front == rear | (rear+1) % cap == front | capacity - 1 |

How does the modulo wrap-around work?

The modulo operator % maps any integer back into the range [0, capacity). When rear is at the last slot (index capacity - 1), (rear + 1) % capacity wraps it back to 0. This is what makes the array behave like a ring.

Capacity = 4, slots: [0, 1, 2, 3]

rear at 3: (3 + 1) % 4 = 0 → wraps to slot 0
front at 3: (3 + 1) % 4 = 0 → wraps to slot 0

What about a resizable queue?

If the queue must grow beyond the fixed capacity, double the backing array and copy elements in their logical order (from front to rear, unwrapping the ring). This gives amortized O(1) enqueue, similar to ArrayList's growth strategy.

What are the edge cases?

• Enqueue on full queue – throw IllegalStateException.
• Dequeue on empty queue – throw NoSuchElementException.
• Single element – enqueue and dequeue work; front and rear both advance.
• Wrap-around – after several enqueue/dequeue cycles, front and rear cross the array boundary correctly.

What should a senior engineer know?

In production, this exact ring buffer design is used in logging frameworks (like LMAX Disruptor) and network buffers because it never allocates after construction, which avoids garbage collection pauses. Setting the element to null on dequeue helps the garbage collector reclaim the object, which matters for long-lived queues holding large objects.

What are common interview follow-up questions?

• Can you implement a deque (double-ended queue)? – Yes, add methods to enqueue at front and dequeue from rear, both using modulo.
• What about thread safety? – Use locks or atomic operations on the count, front, and rear.
• Why not use LinkedList? – Array is more cache-friendly and avoids per-node allocation overhead.