Queue is a linear data structure. It follows **First In First Out** **(FIFO)**. In other words, the item which is inserted first is **accessed/deleted** first.

For example, when you go to cashier in a mall, then the person first in line is served first. This is a queue.

Basic Operations:-

**enqueue/push:**Insert item in the queue.**dequeue/pop:**pops/deletes an item from the queue.**peek/front**: access the element in front.

**Implementation:**

- using Array
- using LinkedList

## Queue using array

This method is never used for practical purposes.

### Steps

- We declare an array
**que**. - We initialize 2 variables
**front**and**rear**,**front**stores the index of the beginning and**rear**stores index of the end of the**queue**. - For
**enqueue**operation, we increment**rear**and insert data at**que[rear]**. - For
**dequeue**operation, we increment**front**.

### Code

```
#include<stdio.h>
/*
First, we declare 4 global variables
que: stores the queue elements
size: maximum size of the que
front: index of first element of que
rear: index of last element of que
*/
int que[100];
int size = 100;
int rear = -1;
int front = 0;
/*
The qneueue(x) function pushes the value 'x' at the end of the queue
If the queue is full, "OverFlow" message is printed on screen else
*/
void enqueue(int x){
// check if queue is full or not
if(rear==size-1){
printf("OverFlow \n");
}
else{
++rear;
que[rear] = x;
}
}
/* returns true if queue is empty */
int isEmpty(){
if(front>rear)
return 1;
else
return 0;
}
/*
Returns front elemnt of the queue
*/
int peek(){
// check if stack is empty or not
if(isEmpty()){
printf("UnderFlow \n");
return -1;
}
else{
return que[front];
}
}
/*
removes front element from the queue
*/
void dequeue(){
// check if stack is empty or not
if(isEmpty()){
printf("UnderFlow \n");
}
else{
printf("%d removed from the queue\n",que[front]);
++front;
}
}
int main()
{
int choice,x;
printf("1 to enqueue\n2 to dequeue\n3 to see front element of queue\n4 to check if queue is empty\n");
do{
printf("ENTER YOUR CHOICE: ");
scanf("%d",&choice);
switch(choice){
case 1:
printf("Enter data: ");
scanf("%d",&x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
printf("Element at front of queue is: %d\n",peek());
break;
case 4:
if(isEmpty()) printf("Queue is Empty\n");
else printf("Queue is not Empty\n");
}
}while(choice>=1&&choice<=4);
}
```

#### Output

```
1 to enqueue
2 to dequeue
3 to see front element of queue
4 to check if queue is empty
ENTER YOUR CHOICE: 1
Enter data: 100
ENTER YOUR CHOICE: 1
Enter data: 150
ENTER YOUR CHOICE: 1
Enter data: 50
ENTER YOUR CHOICE: 2
100 removed from the queue
ENTER YOUR CHOICE: 2
150 removed from the queue
ENTER YOUR CHOICE: 1
Enter data: 400
ENTER YOUR CHOICE: 1
Enter data: 300
ENTER YOUR CHOICE: 3
Element at front of queue is: 50
ENTER YOUR CHOICE: 4
Queue is not Empty
ENTER YOUR CHOICE: 0
```

### Advantages

- Easy to implement.
- No need to store the address of the next element.

### Disadvantages

- Suppose we have an array of size 100. Due to repeated dequeue, enqueue operations, the front and rear become 99. This means there’s only 1 element in the queue. We want to enqueue again. Even tho the array is mostly empty, we won’t be able to enqueue because of
**rear == size-1**.

To perform enqueue, we will need to shift data from the end to the front of the array. This increases the complexity from O(1) to O(N), where N is the size of the array.

To overcome this problem, we use a**circular queue**.

## Queue using LinkedList

### Steps

- Initialize 2 nodes,
**front,**and**rear**.**front**point to the beginning and**rear**point to the node at the end of the queue. - To enqueue,
- Initialize a new node
**temp**. - Store
**temp**address in the**rear**. - Make
**temp**the new**rear**.

- Initialize a new node
- To dequeue, make the node next to
**front**the new**front**.

### Code

```
#include<stdio.h>
#include<stdlib.h>
struct node{
int v; // value to be store in queue
struct node *next; // to store address os the next node
};
// points to the top of the stack
struct node *front,*rear;
/*
The push(x) function pushes the value 'x' at the end of the queue
*/
void enqueue(int x){
struct node *temp = (struct node*)malloc(sizeof(struct node));
if(temp==NULL){
printf("failed to allocated memory\n");
return;
}
temp->v = x;
temp->next = NULL;
if(front==NULL){
// this block will run if queue is empty
front = rear = temp;
}
else{
rear->next = temp;
rear = temp;
}
}
/*
Returns front node value of the queue
*/
int peek(){
if(front==NULL){
printf("UnderFlow \n");
return -1;
}
else{
return front->v;
}
}
/*
deletes the front node of the queue
*/
void dequeue(){
if(front==NULL){
printf("UnderFlow \n");
}
else{
printf("%d removed form the queue\n",front->v);
// initialize temp with front node address
node *temp = front;
// Set Top to node just below it
front = front->next;
// release memory of popped element
// since it is no longer of out use
// if memory is not released
// then at one point system will have no memory left
// and operations which may required new memory
// will fail, like creation of new node
free(temp);
}
}
int isEmpty(){
if(front==NULL)
return 1;
else
return 0;
}
int main()
{
front = rear = NULL;
int choice,x;
printf("1 to enqueue\n2 to dequeue\n3 to see front element of queue\n4 to check if queue is empty\n");
do{
printf("ENTER YOUR CHOICE: ");
scanf("%d",&choice);
switch(choice){
case 1:
printf("Enter data: ");
scanf("%d",&x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
printf("Element at front of queue is: %d\n",peek());
break;
case 4:
if(isEmpty()) printf("Queue is Empty\n");
else printf("Queue is not Empty\n");
}
}while(choice>=1&&choice<=4);
return 0;
}
```

#### Output

```
1 to enqueue
2 to dequeue
3 to see front element of queue
4 to check if queue is empty
ENTER YOUR CHOICE: 1
Enter data: 100
ENTER YOUR CHOICE: 1
Enter data: 400
ENTER YOUR CHOICE: 1
Enter data: 200
ENTER YOUR CHOICE: 2
100 removed form the queue
ENTER YOUR CHOICE: 2
400 removed form the queue
ENTER YOUR CHOICE: 3
Element at front of queue is: 200
ENTER YOUR CHOICE: 1
Enter data: 500
ENTER YOUR CHOICE: 2
200 removed form the queue
ENTER YOUR CHOICE: 3
Element at front of queue is: 500
ENTER YOUR CHOICE: 4
Queue is not Empty
ENTER YOUR CHOICE: 0
```

### Advantages

- The number of nodes is equal to the number of elements in the queue. No need to allocated more memory than required, unlike arrays.
- LinkedList can easily grow/shrink.

### Disadvantages

- Complex as compared to arrays.
- Extra memory required to store the address of the next node.

## Applications

- It is used to implement
**First Come First Serve (FCFS)**algorithms. - In the operating system, the interrupts of equal priority are served on a first-come basis.
- It is used by some network protocols like Token-Bucket, to handle packets.

## References

https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues#Linked_List_Implementation_2