Design Circular Queue

Problem Statement

The task is to design and implement a MyCircularQueue class, a linear data structure called a circular queue or ring buffer. Unlike a regular queue, a circular queue has its end connected to its beginning, forming a loop. This enables it to efficiently use spaces that become available at the front of the queue once elements are dequeued.

The circular queue operates on the FIFO (First In, First Out) principle with enhanced functionality to utilize free spaces even after reaching its initial capacity, provided elements have been dequeued. The design should include methods for operations like enqueue (insertion), dequeue (deletion), checking if the queue is empty or full, and fetching the front and rear element.

Key operations to be implemented are:

• MyCircularQueue(k): Constructor method initializing the queue of size k.
• int Front(): Retrieves the front item of the queue. Returns -1 if the queue is empty.
• int Rear(): Retrieves the rear item of the queue. Returns -1 if the queue is empty.
• boolean enQueue(int value): Adds an item to the queue. Returns true on successful addition.
• boolean deQueue(): Removes an item from the queue. Returns true on successful removal.
• boolean isEmpty(): Checks whether the queue is empty.
• boolean isFull(): Checks whether the queue is full.

This custom implementation cannot use the built-in queue data structures provided in programming languages.

Examples

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

Constraints

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

Approach and Intuition

Based on the constraints and operations required by the MyCircularQueue:

1. Initialize Structure: Use an array of size k to store the queue elements, along with two pointers (front and rear) indicating the current positions of the front and the rear elements. Also, track the count of current elements to simplify checks for empty or full states.

2. Enqueue Operation:

   • If the queue is full (count == k), return false.
   • Insert the element at the position pointed by rear.
   • Update rear to the next position using modular arithmetic: (rear + 1) % k.
   • Increase the element count.

3. Dequeue Operation:

   • If the queue is empty (count == 0), return false.
   • Update front to the next position: (front + 1) % k.
   • Decrease the element count.

4. Front and Rear Operations:

   • For Front(), if the queue is empty, return -1; otherwise, return the element at the front position.
   • For Rear(), if the queue is empty, return -1; similarly, return the element at the previous position to rear considering circular nature (i.e., (rear - 1 + k) % k).

5. Empty and Full Checks:

   • The queue is empty if the count is 0, and full if the count reaches k.

The circular nature of this queue primarily benefits from unlimited starts over as front and rear indices wrap around the end of the stored array using modular arithmetic, making the queue efficient in re-utilizing freed up space from earlier operations.

Solutions

class Element {
  public int data;
  public Element next;

  public Element(int data) {
    this.data = data;
    this.next = null;
  }
}

class CircularQueue {

  private Element first, last;
  private int size;
  private int limit;

  public CircularQueue(int k) {
    this.limit = k;
  }

  public boolean enqueue(int data) {
    if (this.size == this.limit)
      return false;

    Element newElement = new Element(data);
    if (this.size == 0) {
      first = last = newElement;
    } else {
      last.next = newElement;
      last = newElement;
    }
    this.size += 1;
    return true;
  }

  public boolean dequeue() {
    if (this.size == 0)
      return false;
    this.first = this.first.next;
    this.size -= 1;
    return true;
  }

  public int getFront() {
    if (this.size == 0)
      return -1;
    else
      return this.first.data;
  }

  public int getRear() {
    if (this.size == 0)
      return -1;
    else
      return this.last.data;
  }

  public boolean isEmpty() {
    return (this.size == 0);
  }

  public boolean isFull() {
    return (this.size == this.limit);
  }
}