Circular Queue Design

January 2, 2024

Problem #

Design a circular queue using arrays. The user should be able to enqueue and dequeue elements. The queue should dynamically adjust its size to accommodate more elements when it’s full.

Solution: #

Designing a circular queue using arrays involves implementing a data structure that utilizes an array to store elements in a first-in-first-out (FIFO) manner, with the ability to wrap around to the beginning of the array when the end is reached. This approach effectively utilizes the array’s space and allows for constant-time operations for enqueueing and dequeueing elements.

Solution Approach #

1. Initialize: Create an array of a fixed size. Maintain two pointers, front and rear, and a variable size to track the number of elements in the queue. Initially, front, rear, and size are set to -1, -1, and 0, respectively.

2. Enqueue (Add Element):

   • If the queue is full (i.e., size equals the array length), dynamically increase the size of the array.
   • Increment rear (circularly) and place the new element at the rear position.
   • If adding the first element, set front to 0.
   • Increment size.

3. Dequeue (Remove Element):

   • If the queue is empty (i.e., size is 0), return an error or null.
   • Retrieve the element at front.
   • Increment front (circularly).
   • Decrement size.

4. Dynamic Array Resizing: When the array is full and a new element is to be added, create a new array with double the size, copy the elements from the old array to the new one, and then replace the old array with the new array.

Algorithm Steps #

1. Enqueue

   • Check if the queue is full. If full, resize the array.
   • Add element to the rear.
   • Update rear and size.

2. Dequeue

   • Check if the queue is empty. If empty, return an error.
   • Remove element from the front.
   • Update front and size.

3. Resize Array

   • Double the size of the array.
   • Copy old elements to the new array.
   • Adjust front and rear pointers accordingly.

Python Code #

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = self.rear = -1
        self.size = 0

    def isFull(self):
        return self.size == self.capacity

    def isEmpty(self):
        return self.size == 0

    def enqueue(self, value):
        if self.isFull():
            self.resize()
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = value
        if self.front == -1:
            self.front = self.rear
        self.size += 1

    def dequeue(self):
        if self.isEmpty():
            raise Exception("Queue is empty")
        value = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        if self.size == 0:
            self.front = self.rear = -1
        return value

    def resize(self):
        new_capacity = 2 * self.capacity
        new_queue = [None] * new_capacity
        for i in range(self.size):
            new_queue[i] = self.queue[(self.front + i) % self.capacity]
        self.queue = new_queue
        self.front = 0
        self.rear = self.size - 1
        self.capacity = new_capacity

# Example Usage
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.dequeue()

% self.capacity #

The expression % self.capacity is used to implement the circular behavior in the queue. In a circular queue, when we reach the end of the underlying array and there’s still space at the beginning of the array (due to earlier dequeue operations), we wrap around to the beginning of the array to utilize that unused space.

Using the modulus operator % with self.capacity (which is the size of the array) achieves this wrapping effect. Here’s how it works:

• For rear: When we enqueue an element, rear is incremented. If rear reaches the end of the array (rear == self.capacity - 1), incrementing it further would go out of bounds of the array. Instead, we want rear to go back to the beginning of the array (index 0). Using self.rear = (self.rear + 1) % self.capacity ensures that after reaching the end, rear will loop back to 0.

• For front: Similarly, when we dequeue an element, front is incremented. If front reaches the end of the array, we want it to loop back to the beginning. Using self.front = (self.front + 1) % self.capacity ensures this circular movement.

This use of the modulus operator is a key part of implementing a circular queue in an array. It enables the queue to utilize the entire array efficiently, avoiding the need to shift elements, which would be inefficient.

Time Complexity #

• Enqueue: O(1) on average. O(n) when resizing is needed.
• Dequeue: O(1).

Space Complexity #

• Overall: O(n), where n is the number of elements in the queue. The space complexity dynamically changes with the resizing of the array.