# Queue

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:-

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

Implementation:

1. using Array

## Queue using array

This method is never used for practical purposes.

### Steps

1. We declare an array que.
2. We initialize 2 variables front and rear, front stores the index of the beginning and rear stores index of the end of the queue.
3. For enqueue operation, we increment rear and insert data at que[rear].
4. 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;
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{
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 data: 100
Enter data: 150
Enter data: 50
100 removed from the queue
150 removed from the queue
Enter data: 400
Enter data: 300
Element at front of queue is: 50
Queue is not Empty

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

• 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.

### Steps

1. Initialize 2 nodes, front, and rear. front point to the beginning and rear point to the node at the end of the queue.
2. To enqueue,
1. Initialize a new node temp.
2. Store temp address in the rear.
3. Make temp the new rear.
3. 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{
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 data: 100
Enter data: 400
Enter data: 200
100 removed form the queue
400 removed form the queue
Element at front of queue is: 200
Enter data: 500
200 removed form the queue
Element at front of queue is: 500
Queue is not Empty

• The number of nodes is equal to the number of elements in the queue. No need to allocated more memory than required, unlike arrays.