algoadvance

Leetcode 622. Design Circular Queue

Problem Statement

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.

Your implementation should support following operations:

• MyCircularQueue(k): Constructor, set the size of the queue to be k.
• 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.
• enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
• deQueue: Delete 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.

Clarifying Questions

1. Can the elements in the queue be non-integer values?
   • For the purpose of this problem, we will assume the queue holds integer values.
2. Do we need to handle concurrency?
   • No, assume all operations are performed sequentially.
3. Should we perform input validation for the methods?
   • Assume valid inputs (e.g., enQueue will only receive integer values).

Strategy

1. Use an array to store the elements of the queue.
2. Maintain two pointers, front and rear, to indicate the start and end of the queue.
3. Keep a count of the current number of elements in the queue to determine when it’s full or empty.

Methods:

• Constructor (MyCircularQueue): Initialize the queue array and pointers.
• enQueue: Add an element at the rear and update the rear pointer and count.
• deQueue: Remove an element from the front and update the front pointer and count.
• Front: Return the element at the front if not empty.
• Rear: Return the element just before the rear if not empty.
• isEmpty: Check if count is zero.
• isFull: Check if count equals the queue size.

Time Complexity

• Constructor: O(1)
• enQueue: O(1)
• deQueue: O(1)
• Front: O(1)
• Rear: O(1)
• isEmpty: O(1)
• isFull: O(1)

Let’s implement this:

Code

public class MyCircularQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int count;
    private int capacity;

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

This code covers all the required operations for the circular queue with time complexities as mentioned.

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?