Can queue be implemented using circular linked list?

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.
  Steps:
  
  
  
  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.
  Steps:
  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.


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.

---

How would you implement a queue using circular linked list?

Steps for Implementing Circular Queue using Linked List in C

1. Create a struct node type node.
2. Insert the given data in the new node data section and NULL in address section.
3. If Queue is empty then initialize front and rear from new node.
4. Queue is not empty then initialize rear next and rear from new node.

Why do we use circular queue?

Advantages. Circular Queues offer a quick and clean way to store FIFO data with a maximum size. Conserves memory as we only store up to our capacity (opposed to a queue which could continue to grow if input outpaces output.)

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)); 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 22, 202210214


Table of Contents

View More

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



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 :

1. The first Node is the Head for any Linked List.
2. When a new Linked List is instantiated, it just has the Head, which is Null.
3. Else, the Head holds the pointer to the fisrt Node of the List.
4. When we want to add any Node at the front, we must make the head point to it.
5. 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.
6. 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 :

1. If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
2. 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 →

---