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