Design Circular Queue

Problem Description

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 store the next element in those spaces.

Implementation the MyCircularQueue class:

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

You must solve the problem without using any built-in queue libraries.

Examples

Constraints

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

Array with Head and Tail Pointers

A circular queue can be implemented using a fixed-size array of capacity k and two index pointers: head and count (number of active elements in the queue). Using count instead of a tail pointer simplifies checking if the queue is empty (count == 0) or full (count == k).

• To find the rear element’s index: (head + count - 1) % k.
• To enqueue: compute the next write index (head + count) % k, store the value, and increment count.
• To dequeue: advance head = (head + 1) % k and decrement count. All operations execute in O(1) time with O(k) space.

Solution 1: Array-Based Ring Buffer

Utilize index arithmetic modulo k to recycle array slots.

class MyCircularQueue {
    private int[] data;
    private int head;
    private int count;
    private int capacity;

    public MyCircularQueue(int k) {
        data = new int[k];
        head = 0;
        count = 0;
        capacity = k;
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        data[(head + count) % capacity] = value;
        count++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % capacity;
        count--;
        return true;
    }

    public int Front() {
        if (isEmpty()) return -1;
        return data[head];
    }

    public int Rear() {
        if (isEmpty()) return -1;
        return data[(head + count - 1) % capacity];
    }

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

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

class MyCircularQueue:
    def __init__(self, k: int):
        self.data = [0] * k
        self.head = 0
        self.count = 0
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[(self.head + self.count) % self.capacity] = value
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.capacity
        self.count -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[self.head]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[(self.head + self.count - 1) % self.capacity]

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.capacity

#include <vector>

class MyCircularQueue {
private:
    std::vector<int> data;
    int head;
    int count;
    int capacity;

public:
    MyCircularQueue(int k) {
        data.resize(k);
        head = 0;
        count = 0;
        capacity = k;
    }

    bool enQueue(int value) {
        if (isFull()) return false;
        data[(head + count) % capacity] = value;
        count++;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % capacity;
        count--;
        return true;
    }

    int Front() {
        if (isEmpty()) return -1;
        return data[head];
    }

    int Rear() {
        if (isEmpty()) return -1;
        return data[(head + count - 1) % capacity];
    }

    bool isEmpty() {
        return count == 0;
    }

    bool isFull() {
        return count == capacity;
    }
};

Complexity Analysis

• Time Complexity: O(1) for all operations since array reads/writes take constant time.
• Space Complexity: O(k) auxiliary space to store elements in the pre-allocated array.

Where It Breaks

If the queue capacity must grow dynamically (unlike the fixed parameter k), we must reallocate the array and copy elements, raising the enqueue cost of resizing steps to O(n).

Common Mistakes

• Incorrect rear calculation: Computing rear as (head + count) % k instead of (head + count - 1) % k.
• Race conditions in counts: Incrementing count before writing the data value, which can write to an incorrect slot if concurrent threads access the queue.

← All Problems