C - Programming

Haven't you realised that the regular, static queues we saw have a very big drawback that once the queue is FULL, even though we delete few elements from the "front" and relieve some occupied space, 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 queue in which the moment "rear" reaches the Queue's watermark, the "first" element will become the queue's new "rear".

As the name suggests, this Queue is not straight but circular; meaning, you got to have 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" has moved forward; otherwise it will again be a "Queue overflow" state.....Hope! the sky hasn't fallen as yet.

Here, as you can see, the "front" value is 0 and the "rear" value is 5.

Initially, when such a queue is empty, the "front" and the "rear" values are 0 & -1 respectively; and the queue has a NULL value for all its element. Every time we add an element to the queue, the "rear" value increments by 1 till the time it reaches the upper limit of queue; after which it starts all over again from 0. Similarly, every time we delete an element from queue, the "front" value increments by 1 till the time it reaches the upper limit of queue; after which it starts all over again from 0.

Algorithm for Insertion:-
Step-1: If "rear" of the queue is pointing to the last position then go to step-2 or else step-3
Step-2: make the "rear" value as 0
Step-3: increment the "rear" value by one
Step-4: a. if the "front" points where "rear" is pointing and the queue holds a not NULL value
for it, then its a "queue overflow" state, so quit; else go to step-b
b. insert the new value for the queue position pointed by the "rear"

C implementation:-
int max; /*the maximum limit has already been set*/
static int queue[max];
int front=0, rear=-1; /*queue is initially empty*/
..
..
main( )
{
..
..
addval(23);
..
addval(45);
..
addval(47);
..
}

addval( int new)
{
if(rear == max-1) /*step-1*/
rear = 0; /*step-2*/
else
rear = rear + 1; /*step-3*/
if( front == rear && queue[front] != NULL) /*step-4*/
printf("Queue Overflow"); /*step-a*/
else
queue[rear] = new; /*step-b*/
}

Note:- I have implemented this topic using arrays only as Circular queues are used only when limited memory space is there and static implementation is required, so that one can optimally utilize the allocated memory space.