Problem Description

You need to design and implement a circular queue data structure. A circular queue is a linear data structure that operates on the First In First Out (FIFO) principle, where the last position connects back to the first position to form a circle (also known as a "Ring Buffer").

The main advantage of a circular queue is that it can reuse the space at the front of the queue. In a regular queue, once it becomes full, you cannot insert new elements even if there's available space at the front (after elements have been removed). A circular queue solves this problem by wrapping around to use that space.

Your implementation should create a class MyCircularQueue with the following operations:

• MyCircularQueue(k): Constructor that initializes the circular queue with a maximum size of k.
• int Front(): Returns the front element in the queue. If the queue is empty, return -1.
• int Rear(): Returns the last element in the queue. If the queue is empty, return -1.
• boolean enQueue(int value): Adds an element to the rear of the queue. Returns true if successful, false if the queue is full.
• boolean deQueue(): Removes an element from the front of the queue. Returns true if successful, false if the queue is empty.
• boolean isEmpty(): Returns true if the queue is empty, false otherwise.
• boolean isFull(): Returns true if the queue is full, false otherwise.

You must implement this without using any built-in queue data structure from your programming language.

The solution uses an array of fixed size k to store elements, a front pointer to track the position of the first element, and a size variable to track the current number of elements. The circular nature is achieved using modulo arithmetic - when inserting at position (front + size) % capacity and when moving the front pointer as (front + 1) % capacity, the indices wrap around to the beginning of the array when they reach the end.

Intuition

The key insight for implementing a circular queue is recognizing that we need to efficiently utilize a fixed-size array by treating it as if it wraps around - when we reach the end, we continue from the beginning.

Think of it like seats arranged in a circle. When people leave from the front seats, those spaces become available for new people joining at the rear. But how do we keep track of where the front and rear are when they keep moving around the circle?

The challenge is managing two main aspects:

1. Where to insert new elements - This depends on where the queue currently starts (front) and how many elements are already in it (size).
2. How to wrap around - When our indices go beyond the array boundary, they need to circle back to the beginning.

The modulo operator (%) becomes our best friend here. It naturally handles the wrap-around behavior. For any index i, computing i % capacity ensures we stay within the valid array bounds [0, capacity-1].

Instead of maintaining both front and rear pointers (which can be tricky to manage, especially determining when the queue is full vs empty), we can simplify by tracking:

• front: The index of the first element
• size: The number of elements currently in the queue

With these two values, we can always calculate where the rear is: (front + size - 1) % capacity. Similarly, when inserting a new element, it goes to position (front + size) % capacity.

This approach elegantly handles all edge cases:

• Empty queue: size = 0
• Full queue: size = capacity
• Wrap-around: Automatic through modulo arithmetic
• Dequeue: Simply move front forward by 1 (with modulo) and decrease size
• Enqueue: Place at calculated position and increase size

The beauty of this solution is that it avoids the classic problem of distinguishing between a full and empty queue when using just front and rear pointers (where front == rear could mean either state).

Learn more about Queue and Linked List patterns.

Solution Approach

We implement the circular queue using an array-based approach with careful index management through modulo arithmetic.

Data Structure Setup

We initialize our circular queue with:

• q: An array of size k to store the elements
• front: A pointer indicating the index of the front element (initially 0)
• size: A counter tracking the current number of elements (initially 0)
• capacity: The maximum capacity k

Core Operations Implementation

1. EnQueue Operation

When inserting a new element:

• First check if the queue is full by verifying if size == capacity
• If not full, calculate the insertion position: (front + size) % capacity
  • This formula works because front is where the queue starts, and size tells us how many positions to skip
  • The modulo ensures we wrap around to the beginning if needed
• Place the value at the calculated position
• Increment size by 1
• Return true for successful insertion

2. DeQueue Operation

When removing an element:

• Check if the queue is empty (size == 0)
• If not empty, move the front pointer forward: front = (front + 1) % capacity
  • The modulo ensures that if front was at the last position, it wraps to position 0
• Decrement size by 1
• Return true for successful removal

3. Front Operation

To get the front element:

• If the queue is empty (size == 0), return -1
• Otherwise, return q[front] directly

4. Rear Operation

To get the rear element:

• If the queue is empty, return -1
• Otherwise, calculate the rear position: (front + size - 1) % capacity
  • We subtract 1 because size tells us the count, but we need the index of the last element
  • The modulo handles wrap-around cases
• Return the element at the calculated position

5. isEmpty and isFull Operations

These are straightforward checks:

• isEmpty(): Return size == 0
• isFull(): Return size == capacity

Why This Works

The elegance of this solution lies in how size and front work together:

• size tells us exactly how many elements we have, eliminating ambiguity between full and empty states
• front marks our starting position in the circular array
• All positions are calculated relative to front using size, with modulo arithmetic handling the circular nature

For example, if capacity = 5, front = 3, and size = 3, the elements occupy positions [3, 4, 0] in the array. The rear element is at position (3 + 3 - 1) % 5 = 0, and a new element would be inserted at (3 + 3) % 5 = 1.

This approach achieves O(1) time complexity for all operations and uses O(k) space for the array storage.

Example Walkthrough

Let's walk through a sequence of operations with a circular queue of capacity 3 to see how the solution works in practice.

Initial State:

• Create MyCircularQueue(3)
• Array: [_, _, _] (size = 3)
• front = 0, size = 0

Operation 1: enQueue(1)

• Check if full: size (0) == capacity (3)? No
• Insert position: (front + size) % capacity = (0 + 0) % 3 = 0
• Array: [1, _, _]
• Update: size = 1
• Returns: true

Operation 2: enQueue(2)

• Check if full: size (1) == capacity (3)? No
• Insert position: (0 + 1) % 3 = 1
• Array: [1, 2, _]
• Update: size = 2
• Returns: true

Operation 3: enQueue(3)

• Check if full: size (2) == capacity (3)? No
• Insert position: (0 + 2) % 3 = 2
• Array: [1, 2, 3]
• Update: size = 3
• Returns: true

Operation 4: deQueue()

• Check if empty: size (3) == 0? No
• Remove from front = 0
• Update: front = (0 + 1) % 3 = 1, size = 2
• Array: [_, 2, 3] (logically, position 0 is now "empty")
• Returns: true

Operation 5: enQueue(4)

• Check if full: size (2) == capacity (3)? No
• Insert position: (front + size) % capacity = (1 + 2) % 3 = 0
• Array: [4, 2, 3]
• Update: size = 3
• Returns: true
• Note: We wrapped around and reused position 0!

Operation 6: Rear()

• Check if empty: size (3) == 0? No
• Rear position: (front + size - 1) % capacity = (1 + 3 - 1) % 3 = 0
• Returns: 4 (the element at position 0)

Operation 7: Front()

• Check if empty: size (3) == 0? No
• Returns: q[front] = q[1] = 2

Current logical queue: [2, 3, 4] where:

• Position 1 holds the front element (2)
• Position 2 holds the middle element (3)
• Position 0 holds the rear element (4)

This demonstrates how the circular queue efficiently reuses space. After removing element 1 from position 0, we were able to insert element 4 at that same position, treating the array as circular. The modulo arithmetic automatically handles the wrap-around, and tracking size separately from the pointers eliminates any ambiguity about whether the queue is full or empty.

Solution Implementation

Time and Space Complexity

Time Complexity: All operations (enQueue, deQueue, Front, Rear, isEmpty, isFull) have a time complexity of O(1). Each operation performs a constant number of operations:

• enQueue: Calculates the insertion position using (self.front + self.size) % self.capacity and assigns the value - constant time
• deQueue: Updates self.front using (self.front + 1) % self.capacity and decrements size - constant time
• Front: Direct array access at index self.front - constant time
• Rear: Calculates position using (self.front + self.size - 1) % self.capacity and returns the value - constant time
• isEmpty: Simple comparison self.size == 0 - constant time
• isFull: Simple comparison self.size == self.capacity - constant time

Space Complexity: O(k), where k is the capacity of the circular queue. The space is used by:

• The array self.q which stores exactly k elements
• A constant amount of additional space for the instance variables (self.size, self.capacity, self.front)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Full vs Empty States Without Size Variable

Pitfall: A common mistake is trying to determine if the queue is full or empty using only front and rear pointers without a size variable. When front == rear, it's ambiguous whether the queue is completely full or completely empty.

Example of problematic approach:

class MyCircularQueue:
    def __init__(self, k):
        self.queue = [0] * k
        self.front = 0
        self.rear = 0  # Using rear pointer instead of size
        self.capacity = k
  
    def isEmpty(self):
        # When front == rear, is it empty or full?
        return self.front == self.rear  # AMBIGUOUS!

Solution: Always maintain a size counter or waste one slot in the array to differentiate between full and empty states. The provided solution correctly uses a size variable to eliminate this ambiguity.

2. Incorrect Rear Position Calculation

Pitfall: Calculating the rear element's position incorrectly, especially forgetting to subtract 1 or not handling the modulo properly.

Common mistakes:

def Rear(self):
    if self.isEmpty():
        return -1
    # WRONG: This gives the position where next element would be inserted
    return self.queue[(self.front + self.size) % self.capacity]
  
    # WRONG: Forgetting modulo can cause index out of bounds
    return self.queue[self.front + self.size - 1]

Solution: The correct formula is (self.front + self.size - 1) % self.capacity. Remember that size represents the count of elements, so we need to subtract 1 to get the last element's index.

3. Not Updating Front Pointer Correctly in DeQueue

Pitfall: Forgetting to apply modulo when moving the front pointer forward, causing index out of bounds errors.

Incorrect implementation:

def deQueue(self):
    if self.isEmpty():
        return False
    # WRONG: Will cause index error when front reaches capacity-1
    self.front = self.front + 1  # Missing modulo!
    self.size -= 1
    return True

Solution: Always use modulo arithmetic: self.front = (self.front + 1) % self.capacity

4. Mixing Zero-Based and One-Based Logic

Pitfall: Confusion between array indices (0-based) and element count (1-based), leading to off-by-one errors.

Example mistake:

def enQueue(self, value):
    if self.isFull():
        return False
    # WRONG: Using size+1 instead of size for calculating position
    rear_index = (self.front + self.size + 1) % self.capacity
    self.queue[rear_index] = value
    self.size += 1
    return True

Solution: Remember that when you have size elements starting at front, the next available position is at (front + size) % capacity, not (front + size + 1) % capacity.

5. Not Handling Edge Cases in Front/Rear Methods

Pitfall: Accessing array elements without checking if the queue is empty first, leading to returning incorrect values.

Problematic code:

def Front(self):
    # WRONG: Returns whatever garbage value is at front position
    return self.queue[self.front]  # What if queue is empty?

Solution: Always check isEmpty() first and return -1 for empty queue cases, as shown in the correct implementation.