A  Queue is a FIFO list that means FIRST IN FIRST OUT. In this type of data structure the element  inserted  first is to be taken out first.
The element in the  Queue are added at the one end which is called rear end and the element removed from the other is called the front end.

Types of Queues
1. Circular Queue
2. De-Queue
3.Priority Queue
4.Multiple Queue

1. Circular Queue:-
When we want to insert a new element  in the queue ,where the space is available but overflow condition also exist that means REAR= n-1 it is the main drawback of Liner Queue

(a).To resolve this problem  we can choose two situation shift the element  to the left to the left to   fill   the vacant space .
(b). Use of circular queue where first index  (front)  comes right after the index (rear).

2. De-Queue :-
It is the list in which the element can be inserted or deleted  either from front or rear it is also known  as Head -Tail linked list.

There are two type of  De -Queue:

1. Input restricted De-queue:- In  this De -queue insertion can be done by only one end but  deletion can be done by both end.
2. Output restricted :- In this,Queue deletion can be done at only one end but insertion at both end.
3.Priority Queue :-
It is a special type of data structure in which each element assigned with it's priority.
The element with higher priority will processed before an element  which has lower priority,
when two element with same priority then FCFS rule is applied.

4.Multiple Queue :-
To consesrve memory it is better  efficient to use  a multiple Queue where more than one queue  can be used in the same array.

Applications of Queue:
There are following fields where  queue  are applied:-
1. They are widely used as waiting list for single share resources like printer ,disk,plotter,cpu.
2. Queues are also used in  playlist for adding songs to the end and play from front of list.
3.Queues are used in O.S for handling interception.

#include<stdio.h>
#include<conio.h>

// structure creation

struct Node
{
int data;
struct Node *next;
}

*front = NULL,*rear = NULL;
//prototype

void insert(int);
void del();
void display();

void main()
{
int choice, value;
clrscr();
printf("\n:: Queue Implementation using Linked List ::\n");
while(1){
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
insert(value);
break;
case 2: del(); break;
case 3: display(); break;
case 4: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void insert(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode -> next = NULL;
if(front == NULL)
front = rear = newNode;
else{
rear -> next = newNode;
rear = newNode;
}
printf("\nInsertion is Success!!!\n");
}

void del()
{
if(front == NULL)
printf("\nQueue is Empty!!!\n");
else{
struct Node *temp = front;
front = front -> next;
printf("\nDeleted element: %d\n", temp->data);
free(temp);

}
}
void display()
{
if(front == NULL)
printf("\nQueue is Empty!!!\n");
else{
struct Node *temp = front;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL\n",temp->data);
}
}

'

Algorithm to insert an element in the Queue:

STEP 1 Allocate memory for newnode and name it as ptr
STEP 2. Set ptr->data=val

STEP 3.   If(ptr->next=NULL)
Then
Set F=R=ptr
Set F->next=R->next=NULL
Else
Set R->next=ptr
Set R=ptr
Set R->next=NULL
[end of if]

STEP 4. EXIT

Algorithm to display Queue:

STEP 1. [initilize] Front=-1,Rear=-1,ptr=NULL
STEP 2. If ptr->Front=NULL or ptr->Front>ptr->Rear
Print OVERFLOW
GOTO STEP 3
ELSE
While(ptr!=NULL)
Print ptr->data
Set ptr=ptr->front

STEP 3.   EXIT

Algorithm to delete an element in Queue

STEP 1. [initilize] Front=-1,rear=-1,ptr=NULL
STEP 2. If ptr->front=NULL orptr->front>ptr->rear
Print Empty
GOTO STEP 5
[END OF IF]
STEP 3.  Set ptr=front
STEP 4. Set front=front->next
STEP 5.free(ptr)
STEP 6.EXIT

QUEUE IMPLEMENATATION USING ARRAY

Int arr   int rear=-1; int front=-1;

Initial when the queue is empty, the  value of both front and rear will be -1

For insertion ,the value of rear is incremented by 1 and the element is inserted at the rear
position

We can implement Queue with the help of array data structure by using two variable front and rear suppose an array with size 10 at initial stage FRONT=REAR=0
When  inserted any value then rear is incremented by one and value could be stored at the position pointed by rear but the front is unchanged

But in the delete operation  the front will be incremented by one

#include<conio.h>
#include<stdio.h>
//macro #define  MAX 10
//global variable
int q[MAX];

int r=-1,f=-1;
//user defined functions prototype
void insert(void);
void display(void);

int del(void);

int peek(void);
//drive code
void main()

{
int option ,val;
clrscr();

do{
printf("\n1:INSERT");
printf("\n2:DISPLAY");
printf("\n3:DELETE");
printf("\n4:PEEP");
printf("\n5:EXIT");

scanf("%d",&option);
switch(option)
{

case 1: insert();
break;
case 2: display();
break;
case 3: val=del();

if(val!=-1)
printf("%d delete from queue ",val);
break;

case 4:val=peep();

if(val!=1)

printf("%d element found on front of queue",val);

break;

case 5:    exit(0);

default :
printf("not a correct option") ;

}

}
while(option!=5);

getch();
}

// definition of user defined function
void insert(void)
{
int val;
printf("enter element ");
scanf("%d",&val);

if(r==MAX-1)
{
printf("overflow");
}

else

if(r==-1&&f==-1)
f=r=0;

else

{
r++;

q[r]=val;

}

}
// definition of user defined function
void display(void)
{
int i;

if(f==-1||f>r)
printf("underflow");

else
{

for(i=f;i<r;i++)
{
printf("%d",q[i]);
}
}
}

//definition of user defined function
int del(void)
{

int val;

if(f==-1||f>r)
{
printf("under flow");

return -1;
}

else

{
val=q[f];

f++;

if(f>r)
{
printf("all elements deleted");

f=r=-1;
}
return(val);

}
}

int peep(void)
{
if(f==-1||f>r)
{
printf("under flow");
return -1;
}
else

return q[f];
}

Algorithm to insert  an element

STEP 1. [initialize] front=-1,rear=-1
STEP 2. Rear=-1
Print  OVERFLOW
GO TO STEP 5
[end of if]
STEP 3. If front =-1 and rear=-1
Set front=rear=0
[end of if]
STEP 4. Set  q[rear]=Val
STEP 5. EXIT

Algorithm to Display  Queue

STEP 1. [initialize] front=-1,rear=-1, MAX=10
STEP 2. If front=-1 orfront>MAX-1
Print UNDERFLOW
GOTO STEP 4
[end of if]
STEP 3.   Set Val=Q[front]
Set front=front+1
STEP 4. EXIT

Algorithm to delete an element in Queue

STEP 1. [initilize] Front=-1,rear=-1,MAX=0

STEP 2. If front=-1 or front >MAX-1

Print UNDERFLOW

ELSE

Val=Q[Front]
Front=Font+1
If front>Rear
Print All element deleted
Front =Rear=-1
[END OF IF]

STEP 3.  EXIT