Circular Queue

A circular queue is an abstract data type that contains a collection of data which allows addition of data at the end of the queue and removal of data at the beginning of the queue. Circular queues have a fixed size.
Circular queue follows FIFO principle. Queue items are added at the rear end and the items are deleted at front end of the circular queue.



queues



Algorithm for Insertion in a circular queue


Insert CircularQueue ( )

1. If (FRONT == 1 and REAR == N) or (FRONT == REAR + 1) Then

2. 	Print: Overflow

3. Else

4. 	If (REAR == 0) Then [Check if QUEUE is empty]

		(a) Set FRONT = 1

		(b) Set REAR = 1

5. Else If (REAR == N) Then [If REAR reaches end if QUEUE]

6. 		Set REAR = 1

7. Else

8. 		Set REAR = REAR + 1 [Increment REAR by 1]

   [End of Step 4 If]

9. Set QUEUE[REAR] = ITEM

10. Print: ITEM inserted

[End of Step 1 If]

11. Exit




Implementation of insertion in circular queue


#include<stdio.h>

#include<string.h>

#include<conio.h>

#include<ctype.h>

#include<stdlib.h>

#define size 8



int rear, front;

int no;

int q[size];

int rear=-1;

int front=-1;



/* Function to create queue */

void Insert_queue()

{

	char ans;

	printf("\n Enter 'n' for break:-");

	ans=getch();

	while(ans!='n')

	{

		printf("\n Input the Element  : ");

		scanf("%d",&no);



		if((front==0) && (rear==size-1))

		{

			printf("\n Queue is Overflow");

			return;

		}



		else if(rear==front-1)

		{

			printf("\n Queue is overflow");

			return;

		}



		else if(front < 0) /* Insert First Element */

		{

			front=0;

			rear=0;

			q[rear]=no;

		}



		else if(rear==size-1)

		{

			rear=0;

			q[rear]=no;

		}

		else

		{

			rear++;

			if(rear==front)

			{

				printf("\n Queue is overflow ");

				return;

			}

			else

			{

				q[rear]=no;

			}

		}

		printf("\n Enter 'n' for break:-");

		ans = getch();

	}



}

void Display_queue()

{

	int i;

	if(front < 0)

	{

		printf("\n Queue is underflow");

		return;

	}

	printf("\nItems are:\n");

	if(rear>=front)

	{

		for(i=front; i<=rear; i++)

		{

			printf("\n q[%d] = %d",i,q[i]);

		}

	}

	else

	{

		for(i=front;i < size; i++)

		{

			printf("\n l-2 q[%d] = %d",i,q[i]);

		}



		for(i=0;i<=rear;i++)

		{

			printf("\n l-3 q[%d] = %d",i,q[i]);

		}

	}

}

/* Function main */

void main()

{

	clrscr();

	Insert_queue();

	Display_queue();

	getch();

}







Algorithm for Deletion in a circular queue


Delete CircularQueue ( )

1. If (FRONT == 0) Then [Check for Underflow]

2. 	Print: Underflow

3. Else

4. 	ITEM = QUEUE[FRONT]

5. 		If (FRONT == REAR) Then [If only element is left]

			(a) Set FRONT = 0

			(b) Set REAR = 0

6. Else If (FRONT == N) Then [If FRONT reaches end if QUEUE]

7. 			Set FRONT = 1

8. Else

9. 			Set FRONT = FRONT + 1 [Increment FRONT by 1]

		[End of Step 5 If]

10. Print: ITEM deleted

		[End of Step 1 If]

11. Exit




C fuction of deletion in circular queue


void Delete_queue()

{

	if(front < 0)                                                             

	{

		printf("\n Queue is Underflow");

		return;

	}

	no=q[front];

	q[front]=NULL;

	printf("\n Element deleted : ",no);

	if(front==rear)

	{

		front=-1;

		rear=-1;

	}

	else if(front==size-1)

	{

		front=0;

	}

	else

	{

		front++;

	}

}





Quantitative Aptitude
Reasoning
Programming
Interview