Circular Queue :
- In a standard queue, re-buffering problem occurs for each dequeue operation. To solve this problem, we join the front and rear ends of a queue to make the queue as a circular queue.
- In this ,the last node is connected back to the first node to make a circle.
- It follows FIFO principle.
- It can be implemented by either circular linked list or array.
- In array implementation, FRONT>REAR in circular queue whereas FRONT<REAR(always) in simple queue.
- In circular list implementation, FRONT=REAR=START & deletion is performed at rear and insertion at front.
OVERFLOW : Overflow occurs when the queue is full to it’s maximum size and further insertion can’t be done. Conditions are:
- FRONT=0 and REAR=Max
UNDERFLOW : Underflow occurs when Queue is having zero elements and a deletion is performed on it. Conditions for underflow are:
Algorithms for Insertion and Deletion in Circular Queue :
1. [CHECK OVERFLOW] if (FRONT=0 and REAR=max) or (front=rear+1)
PRINT Overflow and EXIT
2. if rear=-1
else if rear=9
3. SET queue[rear]=item
1. [CHECK UNDERFLOW] if front=rear=-1
PRINT Underflow and EXIT
2. if front=rear
else if front=Max