Why Circular Queue is implemented?

Share

Circular queue is a linear data structure in which the operation are performed based on FIFO(First In First Out) principle and the last position is connected back to the first position to make circle like structure. Hence, it is also called ring buffer.

Fig: Circular Queue Implementation

Implementation of linear queue brings drawbacks of memory wastage. As items are removed from the queue(i.e. dequeue), the storage space at the beginning of the array is discarded. Additionally, this newly created empty space can be never re-utilized as the rear pointer reaches the end of queue.

If we furthermore want to add element in above queue(i.e. enqueue). It is considered full, even though the space at the beginning is vacant. Hence, the concept of circular queue is introduced to overcome this limitation.

As shown in figure above, the rear pointer arrives at the beginning of a queue with the help of a circular link to resolve a problem of memory wastage in queue implementation. Thus, this queue is considered the best version of queue data structure.

Circular Queue Operations(Array implementation)

The circular queue opeartions are as follows:

  • Two pointers FRONT and REAR
  • FRONT tracks, the first element of the queue
  • REAR track last elements of the queue
  • It is initialized as, FRONT=REAR=MAXSIZE-1

Enqueue Operations

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.

Algorithm for Enqueue() operation

  1. Start
  2. Initialize REAR=FRONT=MAXSIZE-1
  3. If (FRONT==(REAR+1)%MAXSIZE)
    • Display Queue is full
    • else
    • REAR=(REAR+1)%MAXSIZE
  4. Queue[rear]=item
  5. End

Dequeue Operations

Dequeue() This function is used to delete an element from a circular queue. In a circular queue, the element is always deleted from FRONT positions

Algorithm for Dequeue() operation

  1. Start
  2. Initialize REAR=FRONT=MAXSIZE-1
  3. If(REAR==FRONT)
    • Display Queue is empty and exit
  4. FRONT=(FRONT+1)%MAXSIZE
  5. item=Queue[FRONT]
  6. Display item
  7. End

C Program for Circular Queue

#include <stdio.h>
#define size 5
struct queue
{
	int item[size];
	int front;
	int rear;
} q;
void enqueue(struct queue *q, int num)
{

	if (q->front == (q->rear + 1) % size)
	{
		printf("\nQueue is overflow\n");
	}
	else
	{
		q->rear = (q->rear + 1) % size;
		q->item[q->rear] = num;
	}
}
void dequeue(struct queue *q)
{
	int dq;
	if ((q->rear) == (q->front))
	{
		printf("\nQueue is Empty\n");
	}
	else
	{
		q->front = (q->front + 1) % size;
		dq = q->item[q->front];
		printf("\nDequeu item is:%d", dq);
	}
}
void display(struct queue *q)
{
	int i = 1;
	if (q->rear == -1)
	{
		printf("\nQueue is empty");
	}
	else
	{
		printf("\nThe content of queue is\n");
		for (i = (q->front + 1) % size; i <= q->rear; i = (i + 1) % size)
		{
			printf("\n| %d |", q->item[i]);
		}
	}
}
int main()
{
	int num, choice;
	q.front = size - 1;
	q.rear = size - 1;
	printf("\n1.Enqueue\n2.Dequeue\n3.Display\n4.Exit");
	while (1)
	{
		printf("\nEnter your choice:");
		scanf("%d", &choice);
		switch (choice)
		{
		case 1:
			printf("\nEnter the number you want to add:");
			scanf("%d", &num);
			enqueue(&q, num);
			break;
		case 2:
			dequeue(&q);
			break;
		case 3:
			display(&q);
			break;
		case 4:
			exit(0);
		}
	}
	return 0;
}

Complexity Analysis

The complexity of the enqueue and dequeue operations of a circular queue is O(1) for array implementation.

Applications of Circular Queue

  • Memory Management: The unused memory locations in the case of ordinary queues can be utilized in circular queues.
  • Traffic system: In computer controlled traffic system, circular queues are used to switch on the traffic lights one by one repeatedly as per the time set.
  • CPU Scheduling: Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.

Know more about:Priority Queue, Tree traversal, Linked List

Share
%d bloggers like this: