algoadvance

Leetcode 622. Design Circular Queue Sure. Let’s break down the solution to the problem “622. Design Circular Queue” from LeetCode step by step.

Problem Statement

Design your implementation of a 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”.

Implement the MyCircularQueue class:

• MyCircularQueue(k) Initializes the object with the size of the queue to be k.
• bool enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
• bool deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
• 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.
• bool isEmpty() Checks whether the circular queue is empty or not.
• bool isFull() Checks whether the circular queue is full or not.

Clarifying Questions

Before diving into the code, let’s clarify some points:

1. Should the implemented queue handle only integer values? (Yes, the problem statement implies handling integers.)
2. Is the size of the queue fixed once initialized? (Yes, as suggested by the constructor parameter k.)

Strategy

We will use an array to implement the circular queue. The key components of the implementation will include:

• Two pointers or indices to keep track of the front and rear of the queue.
• An array to store the elements.
• A variable to maintain the current size of the queue.

Upon initialization, the front and rear pointers will be set to -1 (indicating the queue is empty). While performing operations, these pointers will be updated appropriately to ensure the circular nature of the queue.

Code

Here is the implementation in C++:

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

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

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

    bool deQueue() {
        if (isEmpty()) return false;
        if (head == tail) {  // Queue is becoming empty
            head = -1;
            tail = -1;
        } else {
            head = (head + 1) % capacity;
        }
        count--;
        return true;
    }

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

    int Rear() {
        if (isEmpty()) return -1;
        return data[tail];
    }

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

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

Time Complexity

The time complexity for each operation is as follows:

• enQueue(): O(1) - Direct insertion/update using index.
• deQueue(): O(1) - Direct deletion/update using index.
• Front(): O(1) - Direct access using index.
• Rear(): O(1) - Direct access using index.
• isEmpty(): O(1) - Direct comparison.
• isFull(): O(1) - Direct comparison.

These constant time complexities ensure that the circular queue operations are efficient and suitable for real-time use cases.

Feel free to ask if you have any further questions or need additional clarifications!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?