Circular Queue Set 1 Introduction Array Implementation

Circular queue:

Circular queue is a linear data structure which follows the FIFO(First in first out) property. In this, the last element is connected to the first element to make a ring, which is also known as Ring buffer.

How does the Circular queue work?

Circular queue works in the process of circular increment i.e. when we’ll increment the pointer and reach the end then pointer points to the beginning of the queue.

Operations of circular queue:

  • front(): front is used to track the first element of the queue.

  • rear(): rear is used to track the last element of the queue.

  • Enqueue: This operation is used to Insert an element at the end of the queue.

  • Dequeue: This operation is used to remove and return an element from the front of the queue.

Enqueue:

  • Check if the queue is full.
  • If the queue is full then, print queue is full.
  • If not, check the condition(rear == size -1 && front != 0)
  • If it is true then set the rear = 0 and insert the new element.

Dequeue:

  • Firstly, check whether the queue is empty or not.
  • If the queue is empty then display the queue is empty.
  • If not, check the condition(rear == front)
  • If the condition is true then set front = rear = -1.
  • Else, front == size-1 and return the element.

#include<bits/stdc++.h>
using namespace std;

class Queue
{
	int rear, front;


	int size;
	int *arr;
public:
	Queue(int s)
	{
	front = rear = -1;
	size = s;
	arr = new int[s];
	}

	void enQueue(int value);
	int deQueue();
	void displayQueue();
};


void Queue::enQueue(int value)
{
	if ((front == 0 && rear == size-1) ||
			(rear == (front-1)%(size-1)))
	{
		printf("\nQueue is Full");
		return;
	}

	else if (front == -1)
	{
		front = rear = 0;
		arr[rear] = value;
	}

	else if (rear == size-1 && front != 0)
	{
		rear = 0;
		arr[rear] = value;
	}

	else
	{
		rear++;
		arr[rear] = value;
	}
}

int Queue::deQueue()
{
	if (front == -1)
	{
		printf("\nQueue is Empty");
		return INT_MIN;
	}

	int data = arr[front];
	arr[front] = -1;
	if (front == rear)
	{
		front = -1;
		rear = -1;
	}
	else if (front == size-1)
		front = 0;
	else
		front++;

	return data;
}


void Queue::displayQueue()
{
	if (front == -1)
	{
		printf("\nQueue is Empty");
		return;
	}
	printf("\nElements in Circular Queue are: ");
	if (rear >= front)
	{
		for (int i = front; i <= rear; i++)
			printf("%d ",arr[i]);
	}
	else
	{
		for (int i = front; i < size; i++)
			printf("%d ", arr[i]);

		for (int i = 0; i <= rear; i++)
			printf("%d ", arr[i]);
	}
}

int main()
{
	Queue q(5);

	// Inserting elements in Circular Queue
	q.enQueue(40);
	q.enQueue(22);
	q.enQueue(30);
	q.enQueue(-7);

	q.displayQueue();

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

	q.displayQueue();

	q.enQueue(90);
	q.enQueue(20);
	q.enQueue(5);

	q.displayQueue();

	q.enQueue(20);
	return 0;
}

import java.util.ArrayList;

class CircularQueue{

private int size, front, rear;

private ArrayList<Integer> queue = new ArrayList<Integer>();


CircularQueue(int size)
{
	this.size = size;
	this.front = this.rear = -1;
}

public void enQueue(int data)
{
	

	if((front == 0 && rear == size - 1) ||
	(rear == (front - 1) % (size - 1)))
	{
		System.out.print("Queue is Full");
	}

	else if(front == -1)
	{
		front = 0;
		rear = 0;
		queue.add(rear, data);
	}

	else if(rear == size - 1 && front != 0)
	{
		rear = 0;
		queue.set(rear, data);
	}

	else
	{
		rear = (rear + 1);
	
		if(front <= rear)
		{
			queue.add(rear, data);
		}
	
		else
		{
			queue.set(rear, data);
		}
	}
}


public int deQueue()
{
	int temp;

	if(front == -1)
	{
		System.out.print("Queue is Empty");
		
		// Return -1 in case of empty queue
		return -1;
	}

	temp = queue.get(front);

	if(front == rear)
	{
		front = -1;
		rear = -1;
	}

	else if(front == size - 1)
	{
		front = 0;
	}
	else
	{
		front = front + 1;
	}
	
	// Returns the dequeued element
	return temp;
}

// Method to display the elements of queue
public void displayQueue()
{
	
	// Condition for empty queue.
	if(front == -1)
	{
		System.out.print("Queue is Empty");
		return;
	}


	System.out.print("Elements in the " +
					"circular queue are: ");

	if(rear >= front)
	{
	
		for(int i = front; i <= rear; i++)
		{
			System.out.print(queue.get(i));
			System.out.print(" ");
		}
		System.out.println();
	}

	else
	{
		
		for(int i = front; i < size; i++)
		{
			System.out.print(queue.get(i));
			System.out.print(" ");
		}

		for(int i = 0; i <= rear; i++)
		{
			System.out.print(queue.get(i));
			System.out.print(" ");
		}
		System.out.println();
	}
}

public static void main(String[] args)
{

	CircularQueue q = new CircularQueue(5);
	
	q.enQueue(14);
	q.enQueue(22);
	q.enQueue(13);
	q.enQueue(-6);
	
	q.displayQueue();

	int x = q.deQueue();

	if(x != -1)
	{
		System.out.print("Deleted value = ");
		System.out.println(x);
	}

	x = q.deQueue();

	if(x != -1)
	{
		System.out.print("Deleted value = ");
		System.out.println(x);
	}

	q.displayQueue();
	
	q.enQueue(9);
	q.enQueue(20);
	q.enQueue(5);
	
	q.displayQueue();
	
	q.enQueue(20);
}
}

class CircularQueue():

	# constructor
	def __init__(self, size):
		self.size = size
		
		self.queue = [None for i in range(size)]
		self.front = self.rear = -1

	def enqueue(self, data):
		
		if ((self.rear + 1) % self.size == self.front):
			print(" Queue is Full\n")
			

		elif (self.front == -1):
			self.front = 0
			self.rear = 0
			self.queue[self.rear] = data
		else:
			
		
			self.rear = (self.rear + 1) % self.size
			self.queue[self.rear] = data
			
	def dequeue(self):
		if (self.front == -1): # condition for empty queue
			print ("Queue is Empty\n")
			

		elif (self.front == self.rear):
			temp=self.queue[self.front]
			self.front = -1
			self.rear = -1
			return temp
		else:
			temp = self.queue[self.front]
			self.front = (self.front + 1) % self.size
			return temp

	def display(self):
	

		if(self.front == -1):
			print ("Queue is Empty")

		elif (self.rear >= self.front):
			print("Elements in the circular queue are:",
											end = " ")
			for i in range(self.front, self.rear + 1):
				print(self.queue[i], end = " ")
			print ()

		else:
			print ("Elements in Circular Queue are:",
										end = " ")
			for i in range(self.front, self.size):
				print(self.queue[i], end = " ")
			for i in range(0, self.rear + 1):
				print(self.queue[i], end = " ")
			print ()

		if ((self.rear + 1) % self.size == self.front):
			print("Queue is Full")

ob = CircularQueue(5)
ob.enqueue(14)
ob.enqueue(22)
ob.enqueue(13)
ob.enqueue(-6)
ob.display()
print ("Deleted value = ", ob.dequeue())
print ("Deleted value = ", ob.dequeue())
ob.display()
ob.enqueue(9)
ob.enqueue(20)
ob.enqueue(5)
ob.display()


Complexity :

Time complexity: O(1)

Applications of circular queue:

  • Circular queue is used in CPU Scheduling.
  • Also used in memory management.

This article tried to discuss the Circular Queue Array Implementation. Hope this blog helps you understand the concept. To practice problems feel free to check MYCODE | Competitive Programming.

Leave a Reply

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