circular_queue.py

# Implementation of Circular Queue (using Python lists)


classCircularQueue:
"""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
 <data_structures.queues.circular_queue.CircularQueue object at ...
 >>> cq.array
 ['A', None, None, None, None]
 >>> len(cq)
 1
 """
returnself.size

defis_empty(self) ->bool:
"""
 Checks whether the queue is empty or not
 >>> cq = CircularQueue(5)
 >>> cq.is_empty()
 True
 >>> cq.enqueue("A").is_empty()
 False
 """
returnself.size==0

deffirst(self):
"""
 Returns the first element of the queue
 >>> cq = CircularQueue(5)
 >>> cq.first()
 False
 >>> cq.enqueue("A").first()
 'A'
 """
returnFalseifself.is_empty() elseself.array[self.front]

defenqueue(self, data):
"""
 This function inserts an element at the end of the queue using self.rear value
 as an index.
 >>> cq = CircularQueue(5)
 >>> cq.enqueue("A") # doctest: +ELLIPSIS
 <data_structures.queues.circular_queue.CircularQueue object at ...
 >>> (cq.size, cq.first())
 (1, 'A')
 >>> cq.enqueue("B") # doctest: +ELLIPSIS
 <data_structures.queues.circular_queue.CircularQueue object at ...
 >>> cq.array
 ['A', 'B', None, None, None]
 >>> (cq.size, cq.first())
 (2, 'A')
 """
ifself.size>=self.n:
raiseException("QUEUE IS FULL")

self.array[self.rear] =data
self.rear= (self.rear+1) %self.n
self.size+=1
returnself

defdequeue(self):
"""
 This function removes an element from the queue using on self.front value as an
 index and returns it
 >>> 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
 """
ifself.size==0:
raiseException("UNDERFLOW")

temp=self.array[self.front]
self.array[self.front] =None
self.front= (self.front+1) %self.n
self.size-=1
returntemp