Implementation of a Circular Queue Using a Linked List

The linked list implementation of a circular queue begins with the declaration of a node and pointer variables. For the creation of a node, you will use structure in C as follows:

// Declaration of node using structure in C programming    struct node     {   int data;   struct node *next;     };     struct node *front=-1;     struct node *rear=-1;

Implement circular queue operation now.

1.  First, you must implement Enqueue() operation. In this function, you will allocate the memory for a new node using the following snippet of code:

void enqueue(int x)     {   struct node *newnode;  newnode=(struct node *)malloc(sizeof(struct node));  //malloc function helps in allocating memory

After creating a new node, you must also insert values into both data and reference fields. Data will be an argument provided by the user, and the reference field will be set to null initially.

newnode->data=x;      newnode->next=0;

There are two conditions for inserting a new node into the linked circular queue.

In the first condition, you will insert a new node into an empty queue. In this case, both the front and rear pointer must be Null. You must check it using the condition rear == -1. If it is true, the new element will be added as the first element of the queue, and both the front and the rear pointer will also be updated to point to this new node. 

if(rear == -1){   front = rear = newnode;   Rear->next = front      }

In the second case, the queue already contains over one data element. Now, the condition rear == -1 becomes false. In this scenario, you will just update the rear pointer to point to the new node. You should also change the address field of the previous node to establish a new link.

else   {         rear->next=newnode;         rear=newnode;         rear->next=front;    }

2. The dequeue() operation is accountable for deleting the data element from the front node of a queue. While implementing this operation, you will first check if the queue is empty as you cannot delete the element if there is no element in a queue.

void dequeue()      {      struct node *temp;   // declaration of pointer node      temp=front;      if((front==-1)&&(rear==-1))        {           printf("\nQueue is empty");       }

Further, if there is only one element in the queue, you must set both the front and the rear pointer to NULL.

else if(front==rear)      {          front=rear=-1;          free(temp);      }

Otherwise, you must update the value of the front pointer to point to the next node. And it will =deallocate the memory of deleted node with the help of the free() function in C.

else      {          front=front->next;          rear->next=front;          free(temp);      }

The linked list implementation of a circular queue using the C programming language is given below. The program contains one additional function named Display().  In this function, you have initialized the temp pointer pointing to the front node. And with the help of the while condition, you will traverse through the whole circular linked queue.

Program in C:

#include <stdio.h>  #include<stdlib.h>    struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int x)   {       struct Node* newnode =  (struct Node*)malloc(sizeof(struct Node));     newnode->data=x;       newnode->next=0;       if(rear== NULL)        {           front=rear=newnode;           rear->next=front;       }       else       {           rear->next=newnode;           rear=newnode;           rear->next=front;       }   }   void dequeue()   {       struct Node* temp = front;       if((front==NULL)&&(rear==NULL))         {           printf("\nQueue is empty");       }       else if(front==rear)      {           front=rear=NULL;           free(temp);       }       else       {           front=front->next;           rear->next=front;           free(temp);       }   }    int peek()   {       if((front==NULL) &&(rear==NULL))       {           printf("\nQueue is empty");       }       else       {           printf("\nThe front element is %d", front->data);       }   }     void display()   {       struct Node* temp = front;       printf("\n The elements in a Queue are : ");       if((front==NULL) && (rear==NULL))       {           printf("Queue is empty");       }          else        {           while(temp->next!=front)           {               printf("%d,", temp->data);               temp=temp->next;           }           printf("%d", temp->data);       }   }   int main()   {       enqueue(34);        enqueue(10);       enqueue(23);       display();        dequeue();        peek();   }

Output:

Applications of a Circular Queue

• Buffer in Computer Systems: Computer systems supply a holding area for maintaining communication between two processes, two programs, or even two systems. This memory area is also known as a ring buffer.

• CPU Scheduling: In the Round-Robin Scheduling Algorithm, a circular queue is utilized to maintain processes that are in a ready state.

• Traffic System: Circular queue is also utilized in traffic systems that are controlled by computers. Each traffic light turns ON in a circular incrementation pattern in a constant interval of time.

Conclusion

In this tutorial, you explored the circular queues in a data structure. A circular queue resolves memory wastage drawback, which is faced in the implementation of a linear queue. You also went through the steps to implement primary circular queue operations. Following this, you understood the development of queue operations with the help of a drive-through coding explanation. You also encountered the coding implementation of queue, using a linked list and an array with the help of the C programming language.

On that note, do you have any questions related to this tutorial on a circular queue? If you do, please don’t hesitate to place them as comments at the end of this page; we will respond to them soon!