Design Circular Queue

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implement the MyCircularQueue class:

• MyCircularQueue(k) Initializes the object with the size of the queue to be k.
• int Front() Gets the front item from the queue. If the queue is empty, return -1.
• int Rear() Gets the last item from the queue. If the queue is empty, return -1.
• boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
• boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
• boolean isEmpty() Checks whether the circular queue is empty or not.
• boolean isFull() Checks whether the circular queue is full or not.

You must solve the problem without using the built-in queue data structure in your programming language.

Example 1:

Input [“MyCircularQueue”, “enQueue”, “enQueue”, “enQueue”, “enQueue”, “Rear”, “isFull”, “deQueue”, “enQueue”, “Rear”] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 3, true, true, true, 4]

Explanation MyCircularQueue myCircularQueue = new MyCircularQueue(3); myCircularQueue.enQueue(1); // return True myCircularQueue.enQueue(2); // return True myCircularQueue.enQueue(3); // return True myCircularQueue.enQueue(4); // return False myCircularQueue.Rear(); // return 3 myCircularQueue.isFull(); // return True myCircularQueue.deQueue(); // return True myCircularQueue.enQueue(4); // return True myCircularQueue.Rear(); // return 4

Constraints:

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

Approach: Array with Circular Indices (Optimal Solution)

Algorithm

1. Use a fixed-size array of length k to store values
2. Track front (index of the front element) and rear (index where the next element will be inserted)
3. Track size to distinguish empty from full without wasting a slot
4. enQueue: if not full, store at rear, advance rear = (rear + 1) % k, increment size
5. deQueue: if not empty, advance front = (front + 1) % k, decrement size
6. Front/Rear read from the appropriate indices when not empty

Key Insight

Wrapping indices modulo k makes the array circular. Keeping an explicit size counter lets the array be fully utilized: both front and rear point to real slots, and the queue can hold exactly k elements.

Time & Space Complexity

• Time Complexity: O(1) for every operation
• Space Complexity: O(k) - fixed array of size k

Java Implementation

public class MyCircularQueue {

    private int[] queue;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    /** Initialize the queue with a fixed size. */
    public MyCircularQueue(int k) {
        this.capacity = k;
        this.queue = new int[k];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    /** Insert an element into the queue. Return true if successful. */
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        queue[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    /** Delete an element from the queue. Return true if successful. */
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    /** Get the front item. */
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return queue[front];
    }

    /** Get the last item. */
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        // rear points to the next free slot, so the last element is at (rear - 1 + k) % k
        return queue[(rear - 1 + capacity) % capacity];
    }

    /** Check whether the queue is empty. */
    public boolean isEmpty() {
        return size == 0;
    }

    /** Check whether the queue is full. */
    public boolean isFull() {
        return size == capacity;
    }

    // Test method
    public static void main(String[] args) {
        MyCircularQueue q = new MyCircularQueue(3);
        System.out.println("enQueue(1): " + q.enQueue(1)); // Expected: true
        System.out.println("enQueue(2): " + q.enQueue(2)); // Expected: true
        System.out.println("enQueue(3): " + q.enQueue(3)); // Expected: true
        System.out.println("enQueue(4): " + q.enQueue(4)); // Expected: false
        System.out.println("Rear(): " + q.Rear());         // Expected: 3
        System.out.println("isFull(): " + q.isFull());     // Expected: true
        System.out.println("deQueue(): " + q.deQueue());   // Expected: true
        System.out.println("enQueue(4): " + q.enQueue(4)); // Expected: true
        System.out.println("Rear(): " + q.Rear());         // Expected: 4
    }
}

Example Walkthrough

For k = 3:

1. enQueue(1): queue=[1,,], front=0, rear=1, size=1
2. enQueue(2): queue=[1,2,_], rear=2, size=2
3. enQueue(3): queue=[1,2,3], rear=0, size=3
4. enQueue(4): full, returns false
5. Rear(): queue[(2+3)%3]=queue[2]=3
6. deQueue(): front=1, size=2. Now slot 0 is free
7. enQueue(4): queue[0]=4, rear=1, size=3
8. Rear(): queue[(0+3)%3]=queue[0]=4

The circular nature reuses slot 0 that was freed by the deQueue.

Key Insights

1. Circular Wrapping: % capacity reuses freed front slots, solving the wasted-space problem
2. Size Counter: Distinguishes empty from full since front and rear can occupy any slots
3. Rear Calculation: Because rear is the next free slot, the last element is (rear - 1 + capacity) % capacity
4. Constant Time: All seven operations run in O(1) time

The circular array implementation is the optimal solution, providing O(1) operations with O(k) space.