Circular linked list queue

Circular Queue | Set 2 (Circular Linked List Implementation)

Prerequisite – Circular Singly Linked List

We have discussed basics and how to implement circular queue using array in set 1.
Circular Queue | Set 1 (Introduction and Array Implementation)

In this post another method of circular queue implementation is discussed, using Circular Singly Linked List.

Operations on Circular Queue:

Front:Get the front item from queue.
Rear: Get the last item from queue.
enQueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at Rear position.
1. Create a new node dynamically and insert value into it.
2. Check if front==NULL, if it is true then front = rear = (newly created node)
3. If it is false then rear=(newly created node) and rear node always contains the address of the front node.
deQueue() This function is used to delete an element from the circular queue. In a queue, the element is always deleted from front position.
1. Check whether queue is empty or not means front == NULL.
2. If it is empty then display Queue is empty. If queue is not empty then step 3
3. Check if (front==rear) if it is true then set front = rear = NULL else move the front forward in queue, update address of front in rear node and return the element.

Circular Queue

Why was the concept of the circular queue introduced?

There was one limitation in the array implementation of Queue. If the rear reaches to the end position of the Queue then there might be possibility that some vacant spaces are left in the beginning which cannot be utilized. So, to overcome such limitations, the concept of the circular queue was introduced.

As we can see in the above image, the rear is at the last position of the Queue and front is pointing somewhere rather than the 0th position. In the above array, there are only two elements and other three positions are empty. The rear is at the last position of the Queue; if we try to insert the element then it will show that there are no empty spaces in the Queue. There is one solution to avoid such wastage of memory space by shifting both the elements at the left and adjust the front and rear end accordingly. It is not a practically good approach because shifting all the elements will consume lots of time. The efficient approach to avoid the wastage of the memory is to use the circular queue data structure.

What is a Circular Queue?

A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle except that the last position is connected to the first position in a circular queue that forms a circle. It is also known as a Ring Buffer.

Operations on Circular Queue

The following are the operations that can be performed on a circular queue:

Front: It is used to get the front element from the Queue.
Rear: It is used to get the rear element from the Queue.
enQueue(value): This function is used to insert the new value in the Queue. The new element is always inserted from the rear end.
deQueue(): This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end.

Applications of Circular Queue

The circular Queue can be used in the following scenarios:

Memory management: The circular queue provides memory management. As we have already seen that in linear queue, the memory is not managed very efficiently. But in case of a circular queue, the memory is managed efficiently by placing the elements in a location which is unused.
CPU Scheduling: The operating system also uses the circular queue to insert the processes and then execute them.
Traffic system: In a computer-control traffic system, traffic light is one of the best examples of the circular queue. Each light of traffic light gets ON one by one after every jinterval of time. Like red light gets ON for one minute then yellow light for one minute and then green light. After green light, the red light gets ON.

Enqueue operation

The steps of enqueue operation are given below:

First, we will check whether the Queue is full or not.
Initially the front and rear are set to -1. When we insert the first element in a Queue, front and rear both are set to 0.
When we insert a new element, the rear gets incremented, i.e., rear=rear+1.

Scenarios for inserting an element

There are two scenarios in which queue is not full:

If rear != max - 1, then rear will be incremented to mod(maxsize) and the new value will be inserted at the rear end of the queue.
If front != 0 and rear = max - 1, it means that queue is not full, then set the value of rear to 0 and insert the new element there.

There are two cases in which the element cannot be inserted:

When front ==0 && rear = max-1, which means that front is at the first position of the Queue and rear is at the last position of the Queue.
front== rear + 1;

Algorithm to insert an element in a circular queue

Step 1: IF (REAR+1)%MAX = FRONT
Write " OVERFLOW "
Goto step 4
[End OF IF]

Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]

Step 3: SET QUEUE[REAR] = VAL

Step 4: EXIT

Dequeue Operation

The steps of dequeue operation are given below:

First, we check whether the Queue is empty or not. If the queue is empty, we cannot perform the dequeue operation.
When the element is deleted, the value of front gets decremented by 1.
If there is only one element left which is to be deleted, then the front and rear are reset to -1.

Algorithm to delete an element from the circular queue

Step 1: IF FRONT = -1
Write " UNDERFLOW "
Goto Step 4
[END of IF]

Step 2: SET VAL = QUEUE[FRONT]

Step 3: IF FRONT = REAR
SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]

Step 4: EXIT

Let's understand the enqueue and dequeue operation through the diagrammatic representation.

Implementation of circular queue using Array

Output:

Implementation of circular queue using linked list

As we know that linked list is a linear data structure that stores two parts, i.e., data part and the address part where address part contains the address of the next node. Here, linked list is used to implement the circular queue; therefore, the linked list follows the properties of the Queue. When we are implementing the circular queue using linked list then both the enqueue and dequeue operations take O(1) time.

Output:

Next TopicDS Deque

← prev next →

Circular Queue using Linked List in C Programming

February 6, 2022

Circular Linked List

Circular Linked List is little more complicated linked data structure. In the circular linked list we can insert elements anywhere in the list whereas in the array we cannot insert element anywhere in the list because it is in the contiguous memory. In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element. The elements points to each other in a circular way which forms a circular chain. The circular linked list has a dynamic size which means the memory can be allocated when it is required.

Application of Circular Linked List

The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends.
Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.

Implementing Circular Linked List

Implementing a circular linked list is very easy and almost similar to linear linked list implementation, with the only difference being that, in circular linked list the last Node will have it's next point to the Head of the List. In Linear linked list the last Node simply holds NULL in it's next pointer.

So this will be oue Node class, as we have already studied in the lesson, it will be used to form the List.

class Node { public: int data; //pointer to the next node node* next; node() { data = 0; next = NULL; } node(int x) { data = x; next = NULL; } }

Circular Linked List

Circular Linked List class will be almost same as the Linked List class that we studied in the previous lesson, with a few difference in the implementation of class methods.

class CircularLinkedList { public: node *head; //declaring the functions //function to add Node at front int addAtFront(node *n); //function to check whether Linked list is empty int isEmpty(); //function to add Node at the End of list int addAtEnd(node *n); //function to search a value node* search(int k); //function to delete any Node node* deleteNode(int x); CircularLinkedList() { head = NULL; } }

Insertion at the Beginning

Steps to insert a Node at beginning :

The first Node is the Head for any Linked List.
When a new Linked List is instantiated, it just has the Head, which is Null.
Else, the Head holds the pointer to the fisrt Node of the List.
When we want to add any Node at the front, we must make the head point to it.
And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL(in case of new List) or the pointer to the first Node of the List.
The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.

int CircularLinkedList :: addAtFront(node *n) { int i = 0; /* If the list is empty */ if(head == NULL) { n->next = head; //making the new Node as Head head = n; i++; } else { n->next = head; //get the Last Node and make its next point to new Node Node* last = getLastNode(); last->next = n; //also make the head point to the new first Node head = n; i++; } //returning the position where Node is added return i; }

Insertion at the End

Steps to insert a Node at the end :

If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
If the Linked List is not empty then we find the last node, and make it' next to the new Node, and make the next of the Newly added Node point to the Head of the List.

int CircularLinkedList :: addAtEnd(node *n) { //If list is empty if(head == NULL) { //making the new Node as Head head = n; //making the next pointer of the new Node as Null n->next = NULL; } else { //getting the last node node *last = getLastNode(); last->next = n; //making the next pointer of new node point to head n->next = head; } }

Searching for an Element in the List

In searhing we do not have to do much, we just need to traverse like we did while getting the last node, in this case we will also compare the data of the Node. If we get the Node with the same data, we will return it, otherwise we will make our pointer point the next Node, and so on.

node* CircularLinkedList :: search(int x) { node *ptr = head; while(ptr != NULL && ptr->data != x) { //until we reach the end or we find a Node with data x, we keep moving ptr = ptr->next; } return ptr; }

Deleting a Node from the List

Deleting a node can be done in many ways, like we first search the Node with data which we want to delete and then we delete it. In our approach, we will define a method which will take the data to be deleted as argument, will use the search method to locate it and will then remove the Node from the List.

To remove any Node from the list, we need to do the following :

If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next element from the Node to be deleted. And update the next pointer of the Last Node as well.
If the Node is in the middle somewhere, then find the Node before it, and make the Node before it point to the Node next to it.
If the Node is at the end, then remove it and make the new last node point to the head.

node* CircularLinkedList :: deleteNode(int x) { //searching the Node with data x node *n = search(x); node *ptr = head; if(ptr == NULL) { cout << "List is empty"; return NULL; } else if(ptr == n) { ptr->next = n->next; return n; } else { while(ptr->next != n) { ptr = ptr->next; } ptr->next = n->next; return n; } }

← Prev
Next →

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Below is the implementation of above approach:

C++

//C++ program for insertion and

// deletion in Circular Queue

#include <bits/stdc++.h>

using namespace std;

// Structure of a Node

struct Node

{

int data;

struct Node* link;

};

struct Queue

{

struct Node *front, *rear;

};

// Function to create Circular queue

void enQueue(Queue *q,int value)

{

struct Node *temp =new Node;

temp->data = value;

if (q->front == NULL)

q->front = temp;

else

q->rear->link = temp;

q->rear = temp;

q->rear->link = q->front;

}

// Function to delete element from Circular Queue

int deQueue(Queue *q)

{

if (q->front == NULL)

{

printf ("Queue is empty");

return INT_MIN;

}

// If this is the last node to be deleted

int value;// Value to be dequeued

if (q->front == q->rear)

{

value = q->front->data;

free(q->front);

q->front = NULL;

q->rear = NULL;

}

else // There are more than one nodes

{

struct Node *temp = q->front;

value = temp->data;

q->front = q->front->link;

q->rear->link= q->front;

free(temp);

}

return value ;

}

// Function displaying the elements of Circular Queue

void displayQueue(struct Queue *q)

{

struct Node *temp = q->front;

printf(" Elements in Circular Queue are: ");

while (temp->link != q->front)

{

printf("%d ", temp->data);

temp = temp->link;

}

printf("%d", temp->data);

}

/* Driver of the program */

int main()

{

// Create a queue and initialize front and rear

Queue *q =new Queue;

q->front = q->rear = NULL;

// Inserting elements in Circular Queue

enQueue(q, 14);

enQueue(q, 22);

enQueue(q, 6);

// Display elements present in Circular Queue

displayQueue(q);

// Deleting elements from Circular Queue

printf(" Deleted value = %d", deQueue(q));

// Remaining elements in Circular Queue

displayQueue(q);

enQueue(q, 9);

enQueue(q, 20);

displayQueue(q);

return 0;

}

Circular Queue in Data Structure: Overview, Implementation Using Array and Linked List

By SimplilearnLast updated on Feb 7, 20229944

It is common to use circular queues in a data structure in operating systems. It is used to manage the execution of computing processes or programs. You use a circular queue as a buffer to store the processes in order of their insertion and then remove them at the time of resource allocation or execution. In this tutorial, you will explore a circular queue in a data structure along with its implementation and applications.

Why Was the Concept of Circular Queue Introduced?

Implementation of a linear queue brings the drawback of memory wastage. However, memory is a crucial resource that you should always protect by analyzing all the implications while designing algorithms or solutions. In the case of a linear queue, when the rear pointer reaches the MaxSize of a queue, there might be a possibility that after a certain number of dequeue() operations, it will create an empty space at the start of a queue.

Additionally, this newly created empty space can never be re-utilized as the rear pointer reaches the end of a queue. Hence, experts introduced the concept of the circular queue to overcome this limitation.

As shown in the figure above, the rear pointer arrives at the beginning of a queue with the help of a circular link to re-utilize the empty space to insert a new element. This simple addition of a circular link resolves the problem of memory wastage in the case of queue implementation. Thus, this particular type of queue is considered the best version of a queue data structure.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course

Queue using circular linked list

Write aC Program to implement queue using circular linked list.Here’s simpleProgram to implement queue using circular linked list in C Programming Language.