Circular Queue | Set 2 (Circular Linked List Implementation)

Circular Queue

It is a linear data structure that works on the principle of FIFO (First in First out). In this type of queue element can be added in any position or can be deleted from any position in the array but we have to maintain the pointers which will point towards the front and rear end of the queue. In this queue, the rear end can be at any point in the array.

Operations on Circular Queue

  • Front: This function returns the front item from the queue.

  • Rear: This function returns the last item from the queue.

  • Enqueue(item): This function is used to insert the item into the circular queue. In this type of queue, we always insert the new item at the Rear position.

    1. Create a new node and insert the value of the item in it.
    2. Check if front==NULL, if this condition is true then front = rear = (new node).
    3. If the above condition is false then rear = (new node) and rear node always contains the address of the front node.
  • Dequeue(): This function is used to remove the item from the circular queue. In this type of queue, the item present on the front position will be deleted.

    1. Check whether the queue is empty or not i.e. front == NULL.
    2. If the above condition is true then the display queue is empty.
    3. If the above condition is false then Check if (front == rear) if this condition is true then set front = rear = NULL else move the front pointer forward in the queue, update address of front in rear node and return the element.

#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) {
		printf("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;
	printf("\nElements in Circular Queue are: ");
	while (temp->link != q->front) {
		printf("%d ", temp->data);
		temp = temp->link;
	}
	printf("%d", temp->data);
}

int main()
{
	Queue* q = new Queue;
	q->front = q->rear = NULL;

	enQueue(q, 14);
	enQueue(q, 24);
	enQueue(q, 26);

	displayQueue(q);

	printf("\nDeleted value = %d", deQueue(q));
	printf("\nDeleted value = %d", deQueue(q));

	displayQueue(q);

	enQueue(q, 9);
	enQueue(q, 20);
	displayQueue(q);

	return 0;
}
import java.util.*;

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, 24);
		enQueue(q, 26);

		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);
	}
}
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, 24)
	enQueue(q, 26)

	displayQueue(q)

	print("Deleted value = ", deQueue(q))
	print("Deleted value = ", deQueue(q))

	displayQueue(q)

	enQueue(q, 9)
	enQueue(q, 20)
	displayQueue(q)

Time Complexity: The time complexity of Enqueue() and Dequeue() functions will be O(1) as there is no loop in any of the functions.

Note: In case of linked list implementation, a queue is easily implemented without being circular. However, in case of array implementation, we need a circular queue for saving the space.

This article tried to discuss the concept of Circular Queue, Circular Linked List Implementation. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming at Prepbytes

Leave a Reply

Your email address will not be published. Required fields are marked *