circular queue Algorithm
The circular queue algorithm is a linear data structure that follows the First-In-First-Out (FIFO) principle, where the first element added to the queue will be the first one to be removed. Unlike a traditional linear queue, a circular queue treats the front and rear ends as adjacent rather than having a fixed start and end. This allows for more efficient use of memory, as it eliminates the need for shifting elements when an item is dequeued or when the queue becomes full.
A circular queue is implemented using an array with two pointers, front and rear, which are initialized to -1. When an element is enqueued, the rear pointer is incremented and the element is stored in the corresponding array index. When an element is dequeued, the front pointer is incremented and the element is removed from the array. To maintain the circular nature of the queue, the front and rear pointers wrap around the array when they reach the end. This is achieved by using the modulo operator on the array length when incrementing the pointers. Additionally, the algorithm needs to handle cases such as checking if the queue is full (when the rear pointer is one position behind the front pointer), empty (when the front and rear pointers are equal), as well as enqueueing and dequeueing elements.
# Implementation of Circular Queue (using Python lists)
class CircularQueue:
"""Circular FIFO queue with a fixed capacity"""
def __init__(self, n: int):
self.n = n
self.array = [None] * self.n
self.front = 0 # index of the first element
self.rear = 0
self.size = 0
def __len__(self) -> int:
"""
>>> cq = CircularQueue(5)
>>> len(cq)
0
>>> cq.enqueue("A") # doctest: +ELLIPSIS
<circular_queue.CircularQueue object at ...
>>> len(cq)
1
"""
return self.size
def is_empty(self) -> bool:
"""
>>> cq = CircularQueue(5)
>>> cq.is_empty()
True
>>> cq.enqueue("A").is_empty()
False
"""
return self.size == 0
def first(self):
"""
>>> cq = CircularQueue(5)
>>> cq.first()
False
>>> cq.enqueue("A").first()
'A'
"""
return False if self.is_empty() else self.array[self.front]
def enqueue(self, data):
"""
This function insert an element in the queue using self.rear value as an index
>>> cq = CircularQueue(5)
>>> cq.enqueue("A") # doctest: +ELLIPSIS
<circular_queue.CircularQueue object at ...
>>> (cq.size, cq.first())
(1, 'A')
>>> cq.enqueue("B") # doctest: +ELLIPSIS
<circular_queue.CircularQueue object at ...
>>> (cq.size, cq.first())
(2, 'A')
"""
if self.size >= self.n:
raise Exception("QUEUE IS FULL")
self.array[self.rear] = data
self.rear = (self.rear + 1) % self.n
self.size += 1
return self
def dequeue(self):
"""
This function removes an element from the queue using on self.front value as an
index
>>> cq = CircularQueue(5)
>>> cq.dequeue()
Traceback (most recent call last):
...
Exception: UNDERFLOW
>>> cq.enqueue("A").enqueue("B").dequeue()
'A'
>>> (cq.size, cq.first())
(1, 'B')
>>> cq.dequeue()
'B'
>>> cq.dequeue()
Traceback (most recent call last):
...
Exception: UNDERFLOW
"""
if self.size == 0:
raise Exception("UNDERFLOW")
temp = self.array[self.front]
self.array[self.front] = None
self.front = (self.front + 1) % self.n
self.size -= 1
return temp
