CIRCULAR QUEUE
In a circular queue, both the enqueue and dequeue operations are
performed in a way that the queue behaves as though it is a circular buffer,
where the positions at the ends of the queue wrap around to the beginning. This
makes efficient use of space, especially when elements are continuously added
and removed.
Working process of a Circular Queue
Enqueue and Dequeue operations with the numbers 5,10,15,20,50
Initial Setup:
1. Front and Rear both point to the position of the first element (initially
empty, so both will be -1 until we add elements).
2. When the queue is empty, Front and Rear are both at -1.
Enqueue operation (Inserting elements):
We will Enqueue the numbers one by one.
● Enqueue 5:
o The queue is empty, so Front and Rear both move to position 0
and insert 5.
o Front = 0, Rear = 0.
o Queue: [5, _, _, _, _]
● Enqueue 10:
o We increment Rear (move to next position), which wraps around if
needed. Rear moves to position 1 and inserts 10.
o Front = 0, Rear = 1.
o Queue: [5, 10, _, _, _]
● Enqueue 15:
o Rear moves to position 2 and inserts 15.
o Front = 0, Rear = 2.
o Queue: [5, 10, 15, _, _]
● Enqueue 20:
o Rear moves to position 3 and inserts 20.
o Front = 0, Rear = 3.
o Queue: [5, 10, 15, 20,_]
● Enqueue 50:
o Rear moves to position 4 and inserts 50.
o Front = 0, Rear = 4.
o Queue: [5,10,15,20,50]
At this point, the queue is full, and Front = 0, Rear = 4.
Dequeue operation (Removing elements):
We will now perform Dequeue operations, removing elements from the front of
the queue.
● Dequeue:
o The element at position 0 (which is 5) is removed.
o Front moves to position 1 (since the queue is circular, it moves to
the next position).
o Front = 1, Rear = 4.
o Queue: [_, 10,15,20,50]
● Dequeue:
o The element at position 1 (which is 10) is removed.
o Front moves to position 2.
o Front = 2, Rear = 4.
o Queue: [_, _, 20,50]
● Dequeue:
o The element at position 2 (which is 20) is removed.
o Front moves to position 3.
o Front = 3, Rear = 4.
o Queue: [_, _, _, 20, 50]
● Dequeue:
o The element at position 3 (which is 20) is removed.
o Front moves to position 4.
o Front = 4, Rear = 4.
o Queue: [_, _, _, _, 50]
● Dequeue:
o The element at position 4 (which is 50) is removed.
o Front moves to position 0 (wraps around in a circular manner).
o Front = 0, Rear = 4.
o Queue: [_, _, _, _, _]
Final State:
After all the elements have been dequeued, the queue is empty, and Front =
Rear = -1 (or could be reset to 0 depending on the implementation, but both are
equal and the queue is empty).
Complexity Analysis of Circular Queue Operations
Time
Complexity:
O(1)
Overview: Following is the time Space
and space complexity of the Complexity:
different circular queue Enqueu O(1)
operations. e
Time
Complexity:
O(1)
Space
Complexity:
Dequeu O(1)
e:
Advantages of Circular Queue