# 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.
• ## 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 ` `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; ` `} `

## Java

 `// Java program for insertion and  ` `// deletion in Circular Queue  ` `import` `java.util.* ; ` ` `  `class` `Solution ` `{ ` `   `  `// Structure of a Node  ` `static` `class` `Node  ` `{  ` `    ``int` `data;  ` `     ``Node  link;  ` `} ` `   `  `static` `class` `Queue  ` `{  ` `     ``Node  front,  rear;  ` `} ` `   `  `// Function to create Circular queue  ` `static` `void` `enQueue(Queue  q, ``int` `value)  ` `{  ` `     ``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  ` `static`  `int` `deQueue(Queue  q)  ` `{  ` `    ``if` `(q .front ==  ``null``)  ` `    ``{  ` `        ``System.out.printf (``"Queue is empty"``);  ` `        ``return` `Integer.MIN_VALUE;  ` `    ``}  ` `   `  `    ``// If this is the last node to be deleted  ` `    ``int` `value; ``// Value to be dequeued  ` `    ``if` `(q .front == q .rear)  ` `    ``{  ` `        ``value = q .front .data;  ` `        ``q .front =  ``null``;  ` `        ``q .rear =  ``null``;  ` `    ``}  ` `    ``else`  `// There are more than one nodes  ` `    ``{  ` `         ``Node  temp = q .front;  ` `        ``value = temp .data;  ` `        ``q .front = q .front .link;  ` `        ``q .rear .link= q .front;  ` `    ``}  ` `   `  `    ``return` `value ;  ` `}  ` `   `  `// Function displaying the elements of Circular Queue  ` `static` `void` `displayQueue( Queue  q)  ` `{  ` `     ``Node  temp = q .front;  ` `    ``System.out.printf(````" Elements in Circular Queue are: "````);  ` `    ``while` `(temp .link != q .front)  ` `    ``{  ` `        ``System.out.printf(``"%d "``, temp .data);  ` `        ``temp = temp .link;  ` `    ``}  ` `    ``System.out.printf(``"%d"``, temp .data);  ` `}  ` `   `  `/*  Driver of the program  */` `public` `static` `void` `main(String args[]) ` `{  ` `    ``// 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  ` `    ``System.out.printf(````" Deleted value = %d"````, deQueue(q));  ` `    ``System.out.printf(````" Deleted value = %d"````, deQueue(q));  ` `   `  `    ``// Remaining elements in Circular Queue  ` `    ``displayQueue(q);  ` `   `  `    ``enQueue(q, ``9``);  ` `    ``enQueue(q, ``20``);  ` `    ``displayQueue(q);  ` `   `  `}  ` `} ` ` `  `// This code is contributed ` `// by Arnab Kundu `

## Python3

 `# Python3 program for insertion and  ` `# deletion in Circular Queue  ` ` `  `# Structure of a Node  ` `class` `Node: ` `    ``def` `__init__(``self``): ` `        ``self``.data ``=` `None` `        ``self``.link ``=` `None` ` `  `class` `Queue: ` `    ``def` `__init__(``self``): ` `        ``front ``=` `None` `        ``rear ``=` `None` ` `  `# Function to create Circular queue  ` `def` `enQueue(q, value): ` `    ``temp ``=` `Node()  ` `    ``temp.data ``=` `value  ` `    ``if` `(q.front ``=``=` `None``):  ` `        ``q.front ``=` `temp  ` `    ``else``: ` `        ``q.rear.link ``=` `temp  ` ` `  `    ``q.rear ``=` `temp  ` `    ``q.rear.link ``=` `q.front ` ` `  `# Function to delete element from  ` `# Circular Queue  ` `def` `deQueue(q): ` `    ``if` `(q.front ``=``=` `None``): ` `        ``print``(``"Queue is empty"``)  ` `        ``return` `-``999999999999` ` `  `    ``# If this is the last node to be deleted  ` `    ``value ``=` `None` `# Value to be dequeued  ` `    ``if` `(q.front ``=``=` `q.rear): ` `        ``value ``=` `q.front.data ` `        ``q.front ``=` `None` `        ``q.rear ``=` `None` `    ``else``: ``# There are more than one nodes  ` `        ``temp ``=` `q.front  ` `        ``value ``=` `temp.data  ` `        ``q.front ``=` `q.front.link  ` `        ``q.rear.link``=` `q.front ` ` `  `    ``return` `value  ` ` `  `# Function displaying the elements  ` `# of Circular Queue  ` `def` `displayQueue(q): ` `    ``temp ``=` `q.front  ` `    ``print``(``"Elements in Circular Queue are: "``,  ` `                                   ``end ``=` `" "``)  ` `    ``while` `(temp.link !``=` `q.front): ` `        ``print``(temp.data, end ``=` `" "``)  ` `        ``temp ``=` `temp.link ` `    ``print``(temp.data) ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `'__main__'``: ` ` `  `    ``# Create a queue and initialize ` `    ``# front and rear  ` `    ``q ``=` `Queue()  ` `    ``q.front ``=` `q.rear ``=` `None` ` `  `    ``# 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  ` `    ``print``(``"Deleted value = "``, deQueue(q))  ` `    ``print``(``"Deleted value = "``, deQueue(q))  ` ` `  `    ``# Remaining elements in Circular Queue  ` `    ``displayQueue(q)  ` ` `  `    ``enQueue(q, ``9``)  ` `    ``enQueue(q, ``20``)  ` `    ``displayQueue(q) ` ` `  `# This code is contributed by PranchalK `

## C#

 `// C# program for insertion and  ` `// deletion in Circular Queue  ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `public` `class` `GFG ` `{ ` ` `  `// Structure of a Node  ` `public` `class` `Node ` `{ ` `    ``public` `int` `data; ` `    ``public` `Node link; ` `} ` ` `  `public` `class` `LinkedList ` `{ ` `    ``public` `Node front, rear; ` `} ` ` `  `// Function to create Circular queue  ` `public` `static` `void` `enQueue(LinkedList q,  ` `                           ``int` `value) ` `{ ` `    ``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  ` `public` `static` `int` `deQueue(LinkedList q) ` `{ ` `    ``if` `(q.front == ``null``) ` `    ``{ ` `        ``Console.Write(``"Queue is empty"``); ` `        ``return` `int``.MinValue; ` `    ``} ` ` `  `    ``// If this is the last node to be deleted  ` `    ``int` `value; ``// Value to be dequeued ` `    ``if` `(q.front == q.rear) ` `    ``{ ` `        ``value = q.front.data; ` `        ``q.front = ``null``; ` `        ``q.rear = ``null``; ` `    ``} ` `    ``else` `// There are more than one nodes ` `    ``{ ` `        ``Node temp = q.front; ` `        ``value = temp.data; ` `        ``q.front = q.front.link; ` `        ``q.rear.link = q.front; ` `    ``} ` ` `  `    ``return` `value; ` `} ` ` `  `// Function displaying the elements  ` `// of Circular Queue  ` `public` `static` `void` `displayQueue(LinkedList q) ` `{ ` `    ``Node temp = q.front; ` `    ``Console.Write(````" Elements in Circular Queue are: "````); ` `    ``while` `(temp.link != q.front) ` `    ``{ ` `        ``Console.Write(``"{0:D} "``, temp.data); ` `        ``temp = temp.link; ` `    ``} ` `    ``Console.Write(``"{0:D}"``, temp.data); ` `} ` ` `  `// Driver Code ` `public` `static` `void` `Main(``string``[] args) ` `{ ` `    ``// Create a queue and initialize ` `    ``// front and rear  ` `    ``LinkedList q = ``new` `LinkedList(); ` `    ``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  ` `    ``Console.Write(````" Deleted value = {0:D}"````, ` `                                ``deQueue(q)); ` `    ``Console.Write(````" Deleted value = {0:D}"````,  ` `                                ``deQueue(q)); ` ` `  `    ``// Remaining elements in Circular Queue  ` `    ``displayQueue(q); ` ` `  `    ``enQueue(q, 9); ` `    ``enQueue(q, 20); ` `    ``displayQueue(q); ` `} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output:

```Elements in Circular Queue are: 14 22 6
Deleted value = 14
Deleted value = 22
Elements in Circular Queue are: 6
Elements in Circular Queue are: 6 9 20
```

Time Complexity: Time complexity of enQueue(), deQueue() operation is O(1) as there is no loop in any of the operation.

Note: In case of linked list implementation, a queue can be easily implemented without being circular. However, in the case of array implementation, we need a circular queue to save space.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

code

load comments