622. Design Circular Queue

1. 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 use the space to store new values.
Implementation 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.

2. Example

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

3. Constraints

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

4. Solutions

My Accepted Solution

Time complexity: O(1)
Space complexity: O(k)

// array
// Using an array is better than using a list, we don't need to new and delete a class node.
class MyCircularQueue {
public:
    MyCircularQueue(int k) : size(0), capacity(k), headIndex(0), tailIndex(0) {
        values = vector<int>(k);
    }

    bool enQueue(int value) {
        if (isFull()) {
            return false;
        } else {
            ++size;

            values[tailIndex] = value;
            tailIndex = (tailIndex + 1) % capacity;

            return true;
        }
    }

    bool deQueue() {
        if (isEmpty()) {
            return false;
        } else {
            --size;

            headIndex = (headIndex + 1) % capacity;

            return true;
        }
    }

    int Front() {
        if (isEmpty()) {
            return -1;
        } else {
            return values[headIndex];
        }
    }

    int Rear() {
        if (isEmpty()) {
            return -1;
        } else {
            return values[(tailIndex + capacity - 1) % capacity];
        }
    }

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

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

private:
    int size;
    int capacity;
    int headIndex;  // headIndex is the index of the first value in the queue
    int tailIndex;  // tailIndex is the index to hold the next value

    vector<int> values;
};