Circular Queue

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.

Implementation of Circular Queue
To implement a circular queue data structure using array, we first perform the following steps before we implement actual operations.

1. Create a one dimensional array with size SIZE (int cQueue[SIZE])
2. Define two integer variables ‘front’ and ‘rear’ and initialize both with ‘-1’. (int front = -1, rear = -1)

enQueue(value) – Inserting value into the Circular Queue
In a circular queue, enQueue() is a function which is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at rear position.We can use the following steps to insert an element into the circular queue

1. Check whether queue is FULL. ((rear == SIZE-1 && front == 0) || (front == rear+1))
   Second condition will arise when elements were removed from the queue.
2. If it is FULL, then display “Queue is FULL!!! Insertion is not possible!!!” and terminate the function.
3. If it is NOT FULL, then check rear == SIZE – 1 && front != 0 if it is TRUE, then set rear = -1.
   This case will arise when element are removed from the queue. In this case front will be non zero due to removal of element from the head of the queue.
4. Increment rear value by one (rear++), set queue[rear] = value and check ‘front == -1’ if it is TRUE, then set front = 0.

deQueue() – Deleting a value from the Circular Queue
In a circular queue, deQueue() is a function used to delete an element from the circular queue. In a circular queue, the element is always deleted from front position. We can use the following steps to delete an element from the circular queue…

1. Check whether queue is EMPTY. (front == -1 && rear == -1)
2. If it is EMPTY, then display “Queue is EMPTY!!! Deletion is not possible!!!” and terminate the function.
3. If it is NOT EMPTY, then display queue[front] as deleted element and increment the front value by one (front ++). Then check whether front == SIZE, if it is TRUE, then set front = 0. Then check whether both front – 1 and rear are equal (front -1 == rear), if it TRUE, then set both front and rear to ‘-1’ (front = rear = -1).

display() – Displays the elements of a Circular Queue
We can use the following steps to display the elements of a circular queue…

1. Check whether queue is EMPTY. (front == -1)
2. If it is EMPTY, then display “Queue is EMPTY!!!” and terminate the function.
3. If it is NOT EMPTY, then define an integer variable ‘i’ and set ‘i = front’.
4. Check whether ‘front <= rear’, if it is TRUE, then display ‘queue[i]’ value and increment ‘i’ value by one (i++). Repeat the same until ‘i <= rear’ becomes FALSE.
5. If ‘front <= rear’ is FALSE, then display ‘queue[i]’ value and increment ‘i’ value by one (i++). Repeat the same until’i <= SIZE – 1′ becomes FALSE.
6. Set i to 0. Again display ‘cQueue[i]’ value and increment i value by one (i++). Repeat the same until ‘i <= rear’ becomes FALSE.