Circular Linked List Implementation of Circular Queue
Last Updated :
22 Feb, 2023
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.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...