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++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* link;
};
struct Queue {
struct Node *front, *rear;
};
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;
}
int deQueue(Queue* q)
{
if (q->front == NULL) {
cout << "Queue is empty" ;
return INT_MIN;
}
int value;
if (q->front == q->rear) {
value = q->front->data;
free (q->front);
q->front = NULL;
q->rear = NULL;
}
else
{
struct Node* temp = q->front;
value = temp->data;
q->front = q->front->link;
q->rear->link = q->front;
free (temp);
}
return value;
}
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;
}
int main()
{
Queue* q = new Queue;
q->front = q->rear = NULL;
enQueue(q, 14);
enQueue(q, 22);
enQueue(q, 6);
displayQueue(q);
cout << endl << "Deleted value = " << deQueue(q);
cout << endl << "Deleted value = " << deQueue(q);
displayQueue(q);
enQueue(q, 9);
enQueue(q, 20);
displayQueue(q);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
public class Solution {
static class Node {
int data;
Node link;
}
static class Queue {
Node front, rear;
}
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;
}
static int deQueue(Queue q)
{
if (q.front == null ) {
System.out.printf( "Queue is empty" );
return Integer.MIN_VALUE;
}
int value;
if (q.front == q.rear) {
value = q.front.data;
q.front = null ;
q.rear = null ;
}
else
{
Node temp = q.front;
value = temp.data;
q.front = q.front.link;
q.rear.link = q.front;
}
return value;
}
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);
}
public static void main(String args[])
{
Queue q = new Queue();
q.front = q.rear = null ;
enQueue(q, 14 );
enQueue(q, 22 );
enQueue(q, 6 );
displayQueue(q);
System.out.printf( "\nDeleted value = %d" ,
deQueue(q));
System.out.printf( "\nDeleted value = %d" ,
deQueue(q));
displayQueue(q);
enQueue(q, 9 );
enQueue(q, 20 );
displayQueue(q);
}
}
|
Python3
class Node:
def __init__( self ):
self .data = None
self .link = None
class Queue:
def __init__( self ):
front = None
rear = None
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
def deQueue(q):
if (q.front = = None ):
print ( "Queue is empty" )
return - 999999999999
value = None
if (q.front = = q.rear):
value = q.front.data
q.front = None
q.rear = None
else :
temp = q.front
value = temp.data
q.front = q.front.link
q.rear.link = q.front
return value
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)
if __name__ = = '__main__' :
q = Queue()
q.front = q.rear = None
enQueue(q, 14 )
enQueue(q, 22 )
enQueue(q, 6 )
displayQueue(q)
print ( "Deleted value = " , deQueue(q))
print ( "Deleted value = " , deQueue(q))
displayQueue(q)
enQueue(q, 9 )
enQueue(q, 20 )
displayQueue(q)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
public class Node {
public int data;
public Node link;
}
public class LinkedList {
public Node front, rear;
}
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;
}
public static int deQueue(LinkedList q)
{
if (q.front == null ) {
Console.Write( "Queue is empty" );
return int .MinValue;
}
int value;
if (q.front == q.rear) {
value = q.front.data;
q.front = null ;
q.rear = null ;
}
else
{
Node temp = q.front;
value = temp.data;
q.front = q.front.link;
q.rear.link = q.front;
}
return value;
}
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);
}
public static void Main( string [] args)
{
LinkedList q = new LinkedList();
q.front = q.rear = null ;
enQueue(q, 14);
enQueue(q, 22);
enQueue(q, 6);
displayQueue(q);
Console.Write( "\nDeleted value = {0:D}" ,
deQueue(q));
Console.Write( "\nDeleted value = {0:D}" ,
deQueue(q));
displayQueue(q);
enQueue(q, 9);
enQueue(q, 20);
displayQueue(q);
}
}
|
Javascript
class Node {
constructor() {
this .data;
this .node;
}
}
class Queue {
constructor() {
this .front;
this .rear;
}
}
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 deQueue(q) {
if (q.front == null ) {
console.log( "Queue is empty" );
return Number.MIN_VALUE;
}
let value;
if (q.front == q.rear) {
value = q.front.data;
q.front = null ;
q.rear = null ;
}
else {
temp = q.front;
value = temp.data;
q.front = q.front.link;
q.rear.link = q.front;
}
return value;
}
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);
}
q = new Queue();
q.front = q.rear = null ;
enQueue(q, 14);
enQueue(q, 22);
enQueue(q, 6);
displayQueue(q);
console.log( "Deleted value = " + deQueue(q));
console.log( "Deleted value = " + deQueue(q));
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.
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!