Explain what are circular queues? Write down routines required for inserting and deleting elements from a circular queue implemented using arrays.
Circular queue: Static queues have a very big disadvantage that once the queue is
FULL, even though we delete or remove few elements from the "front" and relieve some occupied space, even then we are not able to add anymore elements as the "rear" has already reached the Queue's rear most position.
The solution lies in a type of queue in which the moment "rear" reaches its end; the "first" element will automatically become the queue's new "rear". This type of queue is well known as circular queue possessing a structure like this in which, once the Queue is full the "First" element of the Queue becomes the "Rear" most element, if and only if the "Front" of it has moved forward;
Circular Queue using an array:-
insert(queue,n,front,rear,item)
This procedure inserts an element item into a queue.
1. If front = 1 and rear = n, or if front = rear
+ 1, then:
Write: overflow, and return
2. [find new value of rear]
If front = NULL , then : [queue initially empty.]
Set front = 1 and rear=1. Else if rear = n, then:
Set rear=1.
Else:
Set rear = rear + 1. [end of structure.]
3. Set queue[rear] = item. [this inserts new
element.]
4.Return .
delete(queue,n,front,rear,item)
This procedure deletes an element from a queue and assigns it to the variable item.
1. [queue already empty?] If front = NULL , then:
Write: underflow, and return.
2. Set item = queue[front].
3. [find new value of front]
If front = rear , then : [queue has only one element to start].
Set front = NULL and rear = NULL. Else if front = n, then:
Set front=1.
Else:
Set front = front + 1. [end of structure.]
4. Return .