Circular Linked List Implementation of Circular Queue
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); |
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.
Contact Us