Queue: Circular Queue Implementation
A Queue is a linear, ordered collection of items or data structure in which the operations are performed in First In First Out fashion . Meaning, it is always the first item to be put into the queue, and first item is to be removed first .
In the previous article, we discussed about linear queue and also we implemented linear queue using c++. If you haven’t gotten into that, check that out.
Problems With Linear Queue
Both the rear and front indices are increase but never decreased. As items are removed from the queue, the storage space at the beginning of the array is discarded and never used again. Wastage of the space is the main problem with linear queue.
In this article, we are going to talk about circular queue, which is going to remove the limitation of linear queue, mentioned above.
What is Circular Queue ?
It is the circular array implementation in which we view array as circle rather than linear . In this implementation, the first element of array is immediately followed by its last element. By increment either rear or front index, we can always insert an item unless the array is fully occupied.
Algorithm For Insertion
front = 0 rear = 0
2. Check if queue is full or not
if((rear + 1) % QUEUE_SIZE) = front) print "queue is full"
rear = (rear + 1) % QUEUE_SIZE read data and store in rear position
Algorithm For Deletion
2.Check if queue is empty or not
if(rear = front) print "queue is full"
front = (front + 1) % QUEUE_SIZE