Circular Queue

Circular queues are the queues implemented in circular form rather than in a straight line. Circular queues overcome the problem of unutilized space in linear queue implemented as an array.

In a normal Queue Data Structure, we can insert elements until queue becomes full. But once if queue becomes full, we cannot insert the next element until all the elements are deleted from the queue. For example consider the queue below.

After inserting all the elements into the queue is Full.

Now consider the following situation after deleting three elements from the queue.

This situation also says that Queue is Full and we cannot insert the new element because 'rear' is still at last position. In above situation, even though we have empty positions in the queue we cannot make use of them to insert the new element. This is the major problem in normal queue data structure. To overcome this problem we use circular queue data structure.

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.

Graphical representation of a circular queue is as follows.

Implementation of Circular Queue

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

Step 1: Include all the header files which are used in the program and define a constant ‘SIZE’ with specific value.

Step 2: Declare all user defined functions used in circular queue implementation.

Step3: Create a one dimensional array with above defined SIZE (int cQueue[SIZE])

Step4: Define two integer variables ‘front’ and ‘rear’ and initialize both with ‘-1’. (int front = -1, rear = -1)

Step 5: Implement main method by displaying menu of operations list and make suitable function calls to perform operations selected by the user on circular queue.

Operations on Circular Queue:

enQueue(value) - Inserting value into the Circular Queue

Step 1: Check whether queue is FULL. (rear ==SIZE-1 && front ==0) || (front == rear+1))

Step 2: If it is FULL, then display “Queue is FULL !! Insertion is not possible” and terminate the function.

Step 3: If it is NOT FULL, then check rear == SIZE – 1&& front !=0 if it is TRUE, then set rear = -1.

Step 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. The deQueue() function doesn't take any value as parameter. We can use the following steps to delete an element from the circular queue.

Step 1: Check whether queue is EMPTY. (front == -1 && rear == -1)

Step 2: If it is EMPTY, then display “Queue is EMPTY ! Deletion is not possible !” and terminate the function.

Step 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 -1and 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

Step 1: Check whether queue is EMPTY. (front == -1)

Step2 : If it is EMPTY, then display “Queue is EMPTY!!!” and terminate the function.

Step 3: If it is NOT EMPTY, then define an integer variable ‘i’ and set ‘i=front’.

Step 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.

Step 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.

Step 6: Set i to 0;

Step 7: Again display ‘cqueue[i]’ value and increment I value by one (i++) . Repeat the same until ‘i<= rear’ becomes FALSE.

Listing: Following program is showing the implementation of circular queue.

#include<stdio.h>
#include<stdlib.h>

/* structure for a node */
struct node
{
int data;
struct node *next;
};

/* Function to insert a node at the begining of a Circular
linked list */
void push(struct node **head_ref, int data)
{
struct node *ptr1 = (struct node *)malloc(sizeof(struct node));
struct node *temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;

/* If linked list is not NULL then set the next of last node */
if (*head_ref != NULL)
{
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */

*head_ref = ptr1;
}

/* Function to print nodes in a given Circular linked list */
void printList(struct node *head)
{
struct node *temp = head;
if (head != NULL)
{
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while (temp != head);
}
}

/* program to test above functions */
int main()
{
/* Initialize lists as empty */
struct node *head = NULL;

/* Created linked list will be 12->56->2->11 */
push(&head, 12);
push(&head, 56);
push(&head, 2);
push(&head, 11);

printf("Contents of Circular Linked List\n ");
printList(head);

return 0;
}

Output:
Contents of Circular Linked List
11 2 56 12