Circular Linked List Implementation of Circular Queue

Read

Discuss

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.

Create a new node dynamically and insert value into it.

Check if front==NULL, if it is true then front = rear = (newly created node)

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.

Check whether queue is empty or not means front == NULL.

If it is empty then display Queue is empty. If queue is not empty then step 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.

Below is the implementation of the 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) {
        cout << "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;
    cout << endl << "Elements in Circular Queue are: ";
    while (temp->link != q->front) {
        cout << temp->data << " ";
        temp = temp->link;
    }
    cout << 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
    cout << endl << "Deleted value = " << deQueue(q);
    cout << endl << "Deleted value = " << 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.io.*;
import java.util.*;
 
public 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(
            "\nElements 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("\nDeleted value = %d",
                          deQueue(q));
        System.out.printf("\nDeleted 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("\nElements 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("\nDeleted value = {0:D}",
                      deQueue(q));
        Console.Write("\nDeleted 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

Javascript

// Javascript program for insertion and deletion in Circular Queue
 
      // Structure of a Node
      class Node {
        constructor() {
          this.data;
          this.node;
        }
      }
 
      class Queue {
        constructor() {
          this.front;
          this.rear;
        }
      }
 
      // Function to create Circular queue
      function enQueue(q, value) {
        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
      function deQueue(q) {
        if (q.front == null) {
          console.log("Queue is empty");
          return Number.MIN_VALUE;
        }
 
        // If this is the last node to be deleted
        let value; // Value to be dequeued
        if (q.front == q.rear) {
          value = q.front.data;
          q.front = null;
          q.rear = null;
        } // There are more than one nodes
        else {
          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
      function displayQueue(q) {
        temp = q.front;
        console.log("Elements in Circular Queue are: ");
        while (temp.link != q.front) {
          console.log(temp.data);
          temp = temp.link;
        }
        console.log(temp.data);
      }
 
      /* Driver of the program */
 
      // Create a queue and initialize front and rear
      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
      console.log("Deleted value = " + deQueue(q));
      console.log("Deleted value = " + deQueue(q));
 
      // Remaining elements in Circular Queue
      displayQueue(q);
 
      enQueue(q, 9);
      enQueue(q, 20);
      displayQueue(q);

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.
Auxiliary Space: O(n) where n is the maximum number of elements that can be stored in the queue.

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.

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 22 Feb, 2023