# Queue in Data Structure

##### What is Queue?
• Queue is linear data structure.
• Queue works with the principle FIFO(First In First Out). It means the element is inserted first is taken out first.
• The elements in a queue are added at one end called the REAR and removed from the other end called the FRONT.
• In the computer’s memory, queue can be implemented using both array and linked lists.
##### Application of Queue
• Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
• Queues are used as buffers on MP3 players and portable CD players, iPod playlist.
• Queues are used in operating system for handling interrupts.
##### Array representation of Linear Queue

Queue can be easily represented using linear arrays, every queue has front and rear variables that point to the position from where deletion and insertions can be done, respectively.

##### Algorithm for insert an element in a queue
``````Step 1: If Rear=Max-1
write overflow
Goto step 4
Step 2: If Front=-1 and Rear=-1
Set Front=Rear=0
Else
Set Rear=Rear+1
Step 3: Set Queue[Rear]=Num
Step 4: Exit``````
##### Algorithm for delete an element in a queue
``````Step 1: If Front=-1 or Front>Rear
write underflow
else
Set val=Queue[front]
Set Front=Front+1;
Step 2: Exit;``````
##### Program for Linear Queue
``````#include<stdio.h>
#include<stdlib.h>
#define size 4
int queue[size];
int front=-1;
int rear=-1;
void insert()
{
int data;
if(rear==size-1)
{
printf("Queue is full");
}
else
{
if(rear==-1&&front==-1)
front=0;
printf("\nEnter data which you want to insert in queue:");
scanf("%d",&data);
rear=rear+1;
queue[rear]=data;

}
}
void delete1()
{
if((rear==-1&&front==-1)||front>rear)
{
printf("\nQueue is empty");
}
else
{
printf("Deleted element =%d",queue[front]);
front=front+1;
}
}
void show()
{
int i;
for(i=front;i<=rear;i++)
printf("%d,",queue[i]);
}
void main()
{
int choice;
while(1)
{
printf("\nSelect choice:\nPress 1: insert\nPress 2: Delete\nPress 3: Show\nPress 4: Exit ");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete1();
break;
case 3:
show();
break;
case 4:
exit(0);
default:
printf("Invalid choice");
}
}
}

``````

Output:

##### Drawback of Linear Queue

In queue, insertion are always done at one end is called rear and deletion are always done from other end is called front.

Now, if you want to insert another value, it will not be possible because the queue is completely full.

Consider a scenario in which two elements are deleted. Suppose we want to insert a new element in the queue even space is available, we can’t insert because the overflow condition(Rear=max-1) still holds true. This is the drawback of linear queue.

##### Array Representation for Circular Queue

The drawback of linear queue is solved in circular queue. In the circular queue, the first index comes right after the last index. The circular queue will be full when Front=0 and Rear=max-1 or Front=Rear+1. A circular queue is implemented in the same manner as a linear queue is implemented. The only difference will be in the code that performs insertion and deletion operations.

##### Algorithm for insert an element in circular queue
``````Step 1: If Front=0 and Rear=Max-1 or Front=Rear+1
write Overflow
Goto Step 4
Step 2: If Front=-1 and Rear==-1
Set Front=Rear=0
else
Rear=(Rear+1)%Max
Step 3: Set Queue[Rear]=Value
Step 4: End``````
##### Algorithm for Delete an element in circular queue
``````Step 1: If Front=-1 and Rear=-1
write Underflow
Goto Step 4
Step 2: val=Queue[Front]
Step 3: If Front=Rear
Set Front=Rear=-1
else
Front=(Front+1)%Max
Step 4: End``````
##### C Program for Circular Queue
``````#include<stdio.h>
#include<stdlib.h>
#define size 3
int queue[size];
int front=-1;
int rear=-1;
void insertq()
{
int data;
if((front==0&&rear==size-1)||front==rear+1)
{
printf("Queue is full\n");
}
else if(rear==-1&&front==-1)
{
rear=0;
front=0;
printf("\nEnter value which you want to insert in queue:");
scanf("%d",&data);
queue[rear]=data;
}
else{
printf("\nEnter value which you want to insert in queue:");
scanf("%d",&data);
rear=(rear+1)%size;
queue[rear]=data;
}
}
void deleteq()
{
if(rear==-1&&front==-1)
{
printf("\nQueue is empty\n");
}
else if(front==rear)
{
printf("Deleted element =%d\n",queue[front]);
front=-1;
rear=-1;
}
else
{
printf("Deleted element =%d\n",queue[front]);
front=(front+1)%size;
}
}
void show()
{

if(front==-1)
printf("Queue is empty\n");
else
{
int i=front;
printf("Elements of Queue : ");
if(front<=rear)
{
while(i<=rear)
printf("%d,",queue[i++]);
}
else
{
while(i<=size-1)
printf("%d,",queue[i++]);
i=0;
while(i<=rear)
printf("%d,",queue[i++]);
}
printf("\n");
}
}

void main()
{
int choice;
while(1)
{
printf("\nSelect choice:\nPress 1: insert\nPress 2: Delete\nPress 3: Show\nPress 4: Exit");
scanf("%d",&choice);
switch(choice)
{
case 1:
insertq();
break;
case 2:
deleteq();
break;
case 3:
show();
break;
case 4:
exit(0);
default:
printf("Invalid choice\n");
}
}
}

``````

Output :

##### Question of circular Queue

Question : Let COLOURS[0,3] be a circular queue data structure. Note the actual physical capacity of the queue is only 3 despite the declaration of the array ar[0,3]. The operations illustrated below

1. Insert ‘Orange’ into COLOUR[0,3]
2. Insert ‘Blue’ into COLOUR[0,3]
3. Insert ‘White’ into COLOUR[0,3]
4. Insert ‘Red’ into COLOUR[0,3]
5. Delete twice from COLOUR[0,3]
6. Insert ‘Yellow’ into COLOUR[0,3]
7. Insert ‘Violet’ into COLOUR[0,3]

Solution :

``````#include<stdio.h>
#include<stdlib.h>
#define size 4
char queue[size][20];
int front=-1;
int rear=-1;
void insert()
{
if((front==0&&rear==size-1)||front==rear+1)
{
printf("Queue is full\n");
}
else if(rear==-1&&front==-1)
{
rear=0;
front=0;
printf("\nEnter Colour name which you want to insert :");
scanf("%s",queue[rear]);

}
else
{
rear=(rear+1)%size;
printf("\nEnter Colour name which you want to insert :");
scanf("%s",queue[rear]);
}
}
void delete1()
{
if(rear==-1&&front==-1)
{
printf("\nQueue is empty");
}
else if(front==rear)
{
printf("Deleted element =%s\n",queue[front]);
front=-1;
rear=-1;
}
else
{
printf("Deleted element =%s\n",queue[front]);
front=(front+1)%size;
}
}
void show()
{
if(front==-1)
printf("Queue is empty\n");
else
{
int i=front;
printf("Colours in Queue : ");
if(front<=rear)
{
while(i<=rear)
printf("%s,",queue[i++]);
}
else
{
while(i<=size-1)
printf("%s,",queue[i++]);
i=0;
while(i<=rear)
printf("%s,",queue[i++]);
}
printf("\n");
}
}
void main()
{
int choice;
while(1)
{
printf("\nSelect choice:\nPress 1: insert colour\nPress 2: Delete colour\nPress 3: Show colour\nPress 4: Exit");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete1();
break;
case 3:
show();
break;
case 4:
exit(0);
default:
printf("Invalid choice");
}
}
}

``````

Output :