Data structure tutorial 9: Circular Queues Data structure introduction and Implementation using arrays.

In this chapter we shall learn about below topics:

In the previous chapter we have seen the implementation of simple queue using Array and Linked List [LL]. But we have also seen a disadvantage while using simple queue is that we will not be able to fully utilise the empty spaces. Hence to utilise the space efficiently we should Circular Queues.

Definition:

A circular linked list, the elements in the queue can be inserted in the empty spaces at the front of the queue hence using the empty spaces efficiently.

In circular queue, the front will be pointing at 0 and rear pointer will be pointing at the maximum index size of the queue. We will be using modulus “%” operator to know the empty spaces that have left.

When an element is inserted at the rear end, we use below formula to calculate it’s index.

Similarly, when an element is deleted from front_ end we use below formula it’s calculate the index:

Assume MAX_QUEUE_SIZE = 4;

Initially:
	front_ end will be at index 0
	rear_ end will be at index 3

Enter 10:
	front_ end will be at index 0
	rear_ end = [ 3 + 1] % 4 = 0

	Hence element will be inserted at index 0

 [10, , , ]
 
Enter 20:
	front_ end will be at index 0
	rear_ end = [ 0 + 1] % 4 = 1

	Hence element will be inserted at index 1

 [10, 20, , ]
 
Enter 30:
	front_ end will be at index 0
	rear_ end = [ 1+ 1] % 4 = 2

	Hence element will be inserted at index 2

 [10, 20, 30, ]
 
Enter 40:
	front_ end will be at index 0
	rear_ end = [ 2 + 1] % 4 = 3

	Hence element will be inserted at index 3

 [10, 20, 30, 40]

Delete 10

front_ end will be at index 0 = [0 + 1] % 4 = 0
Element at index 0 will de deleted.

	rear_ end will be at index 3

	Hence element will be inserted at index 3

 [ , 20, 30, 40]

Enter 50:
	front_ end will be at index 1
	rear_ end = [ 3 + 1] % 4 = 0
	Check if there is any element at index '0'. If no element enters 50.
	Hence element will be inserted at index 0
 
 [50, 20, 30, 40]

depending upon the result, the rear pointer will update accordingly.

Below are the operations that we shall be using

This function is used to insert elements into the queue.

This function is used to delete element from the queue.

In this function we will display the queue elements.

Hence by using circular queue we will be utilizing the space efficiently.

#include<stdio.h>
#include<stdlib.h>
 
#define QUEUE_SIZE	5
 
int rear_end; /* a variable to insert element at rear end */
int front_end; /* a variable to delete element at front end */
int queue_elements [10]; /* An array to hold queue elements */
int queue_item; /* a variable to hold the item to be inserted */
int element_count; /* it holds the number of elements presently in the queue*/
 
//function to insert into the queue
void InsertQueue()
{
	if(element_count == QUEUE_SIZE)
	{
		printf("Queue is full\n");
		return;
	}
 
	// we use this formula to get the exact location to insert element
	rear_end = (rear_end + 1) % QUEUE_SIZE;
	queue_elements[rear_end] = queue_item;
	element_count ++;
}
 
//this function is used to delete element from the queue.
int DeleteQueue()
{
	if (element_count == 0)
		return -1;
 
	queue_item = queue_elements[front_end];
 
	//we use this formula to get element from front end 
	front_end = (front_end + 1) % QUEUE_SIZE;
	element_count -= 1;
 
	return queue_item;
}
 
 
//this function is used to display the content of the queue
void DisplayQueue()
{
	int front = front_end;
	if (element_count == 0)
	{
		printf("Queue is empty\n");
		return;
	}
 
	printf("The Queue Elements\n");
 
 
	for (int i = 1; i <= element_count; i++)
	{
		printf("%d\n",queue_elements[front] );
		front = (front + 1) % QUEUE_SIZE;
	}
}
 
int main()
{
	int choice = 0;
 
	front_end = 0;
	rear_end = -1;
	element_count = 0;
 
 
	for( ; ; )
	{
		printf("1. Insert \n2. Delete \n3. Display \n4. Exit\n");
 
		scanf("%d", &choice);
 
		switch(choice)
		{
			case 1:
				printf("\nEnter the item to be inserted\n");
				scanf("%d", &queue_item);
 
				InsertQueue();
			break;
 
			case 2:
				queue_item = DeleteQueue();
 
				if(queue_item == -1)
					{
						printf("Queue is empty\n");
					}
					else
					{
						printf("Deleted Item = %d\n",queue_item );
					}
			break;
 
			case 3:
				DisplayQueue();
				break;
 
			default:
				exit(0);
		}
	}
 
	return 0;
}