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 firstinfirstout (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 constanttime operations for enqueueing and dequeueing elements.
Solution Approach #

Initialize: Create an array of a fixed size. Maintain two pointers,
front
andrear
, and a variablesize
to track the number of elements in the queue. Initially,front
,rear
, andsize
are set to 1, 1, and 0, respectively. 
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 therear
position.  If adding the first element, set
front
to 0.  Increment
size
.
 If the queue is full (i.e.,

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
.
 If the queue is empty (i.e.,

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 #

Enqueue
 Check if the queue is full. If full, resize the array.
 Add element to the rear.
 Update
rear
andsize
.

Dequeue
 Check if the queue is empty. If empty, return an error.
 Remove element from the front.
 Update
front
andsize
.

Resize Array
 Double the size of the array.
 Copy old elements to the new array.
 Adjust
front
andrear
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. Ifrear
reaches the end of the array (rear == self.capacity  1
), incrementing it further would go out of bounds of the array. Instead, we wantrear
to go back to the beginning of the array (index 0). Usingself.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. Iffront
reaches the end of the array, we want it to loop back to the beginning. Usingself.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.