Problem Description

The "Design Circular Queue" problem asks you to implement a circular queue data structure that supports the following operations:

• MyCircularQueue(k): Constructor to initialize the queue with a maximum capacity of k.
• enQueue(value): Insert an element into the circular queue. Returns true if the operation is successful.
• deQueue(): Delete an element from the circular queue. Returns true if the operation is successful.
• Front(): Get the front item from the queue. If the queue is empty, return -1.
• Rear(): Get the last item from the queue. If the queue is empty, return -1.
• isEmpty(): Checks whether the circular queue is empty and returns true or false.
• isFull(): Checks whether the circular queue is full and returns true or false.

The circular queue must use a fixed-size array and wrap around when reaching the end. All operations should run in constant time (O(1)).

Thought Process

At first glance, one might think of using a regular array or list and shifting elements on enqueue or dequeue. However, shifting elements is inefficient and leads to O(n) time for some operations.

To achieve constant time for all operations, we need to avoid shifting. A circular queue (or ring buffer) solves this by using two pointers (or indices): one for the front and one for the rear. When either pointer reaches the end of the array, it wraps around to the beginning, hence "circular."

The main challenge is handling the wrap-around and distinguishing between an empty and a full queue, since both situations can result in the front and rear pointers being equal. There are a few classic solutions, such as keeping a separate size variable or leaving one slot unused.

Solution Approach

Let's walk through the steps to design the circular queue:

1. Data Structure:
   • Use a fixed-size array of length k to store the elements.
   • Maintain two pointers (indices): front and rear.
   • Optionally, keep a size variable to track the number of elements.
2. Enqueue Operation (enQueue):
   • Check if the queue is full (i.e., size == k).
   • If not full, insert the value at rear, then increment rear (with wrap-around using modulo).
   • Increment size.
3. Dequeue Operation (deQueue):
   • Check if the queue is empty (i.e., size == 0).
   • If not empty, increment front (with wrap-around using modulo).
   • Decrement size.
4. Front and Rear Operations:
   • Front(): Return the value at front if not empty; otherwise, return -1.
   • Rear(): Return the value at (rear - 1 + k) % k if not empty; otherwise, return -1.
5. isEmpty and isFull:
   • isEmpty(): Return true if size == 0.
   • isFull(): Return true if size == k.

Using a size variable makes the logic straightforward and avoids ambiguity between empty and full states.

Example Walkthrough

Let's use a queue of size k = 3 and perform the following operations:

• enQueue(1)
• enQueue(2)
• enQueue(3)
• isFull()
• deQueue()
• enQueue(4)
• Rear()

Step-by-step:

1. After enQueue(1): queue = [1, _, _], front = 0, rear = 1, size = 1
2. After enQueue(2): queue = [1, 2, _], front = 0, rear = 2, size = 2
3. After enQueue(3): queue = [1, 2, 3], front = 0, rear = 3 (wraps to 0), size = 3
4. isFull(): returns true (size = 3)
5. deQueue(): removes 1, front = 1, rear = 0, size = 2
6. enQueue(4): inserts at index 0 (wrap-around), queue = [4, 2, 3], front = 1, rear = 1, size = 3
7. Rear(): returns 4 (at index (1-1+3)%3 = 0)

This demonstrates how the pointers wrap around and maintain the queue's circular nature.

Time and Space Complexity

Brute-force approach: Using a dynamic array and shifting elements for each enqueue or dequeue would result in O(n) time per operation, which is inefficient.

Optimized circular queue:

• Time Complexity: All operations (enQueue, deQueue, Front, Rear, isEmpty, isFull) run in O(1) time because they involve only pointer arithmetic and simple checks.
• Space Complexity: O(k), where k is the maximum queue size, since we use a fixed-size array.

Summary

The circular queue is an elegant data structure that efficiently uses space and time by employing a fixed-size array and pointer arithmetic. By carefully managing the front and rear indices and a size variable, we achieve constant-time operations for all queue methods. This approach avoids unnecessary element shifting and leverages the circular property to wrap around the array, making it ideal for scenarios where a bounded queue is required.

Code Implementation

class MyCircularQueue:

    def __init__(self, k: int):
        self.queue = [0] * k
        self.max_size = k
        self.front = 0
        self.rear = 0
        self.size = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.queue[self.rear] = value
        self.rear = (self.rear + 1) % self.max_size
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.max_size
        self.size -= 1
        return True

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

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[(self.rear - 1 + self.max_size) % self.max_size]

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

    def isFull(self) -> bool:
        return self.size == self.max_size
    

class MyCircularQueue {
private:
    vector<int> queue;
    int max_size;
    int front;
    int rear;
    int size;
public:
    MyCircularQueue(int k) {
        queue.resize(k);
        max_size = k;
        front = 0;
        rear = 0;
        size = 0;
    }
    
    bool enQueue(int value) {
        if (isFull()) return false;
        queue[rear] = value;
        rear = (rear + 1) % max_size;
        size++;
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % max_size;
        size--;
        return true;
    }
    
    int Front() {
        if (isEmpty()) return -1;
        return queue[front];
    }
    
    int Rear() {
        if (isEmpty()) return -1;
        return queue[(rear - 1 + max_size) % max_size];
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    bool isFull() {
        return size == max_size;
    }
};
    

class MyCircularQueue {
    private int[] queue;
    private int maxSize;
    private int front;
    private int rear;
    private int size;

    public MyCircularQueue(int k) {
        queue = new int[k];
        maxSize = k;
        front = 0;
        rear = 0;
        size = 0;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) return false;
        queue[rear] = value;
        rear = (rear + 1) % maxSize;
        size++;
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % maxSize;
        size--;
        return true;
    }
    
    public int Front() {
        if (isEmpty()) return -1;
        return queue[front];
    }
    
    public int Rear() {
        if (isEmpty()) return -1;
        return queue[(rear - 1 + maxSize) % maxSize];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == maxSize;
    }
}
    

var MyCircularQueue = function(k) {
    this.queue = new Array(k);
    this.maxSize = k;
    this.front = 0;
    this.rear = 0;
    this.size = 0;
};

MyCircularQueue.prototype.enQueue = function(value) {
    if (this.isFull()) return false;
    this.queue[this.rear] = value;
    this.rear = (this.rear + 1) % this.maxSize;
    this.size++;
    return true;
};

MyCircularQueue.prototype.deQueue = function() {
    if (this.isEmpty()) return false;
    this.front = (this.front + 1) % this.maxSize;
    this.size--;
    return true;
};

MyCircularQueue.prototype.Front = function() {
    if (this.isEmpty()) return -1;
    return this.queue[this.front];
};

MyCircularQueue.prototype.Rear = function() {
    if (this.isEmpty()) return -1;
    return this.queue[(this.rear - 1 + this.maxSize) % this.maxSize];
};

MyCircularQueue.prototype.isEmpty = function() {
    return this.size === 0;
};

MyCircularQueue.prototype.isFull = function() {
    return this.size === this.maxSize;
};