A Brief Introduction to Queue In C++ With Illustration.

The queue is a basic data structure just like a stack. In contrast to stack that uses the LIFO
approach, queue uses the FIFO (first in, first out) approach. With this approach, the first item
that is added to the queue is the first item to be removed from the queue. Just like Stack, the
queue is also a linear data structure.

In a real-world analogy, we can imagine a bus queue where the passengers wait for the bus in
a queue or a line. The first passenger in the line enters the bus first as that passenger happens
to be the one who had come first.

Queue In C++

In software terms, the queue can be viewed as a set or collection of elements as shown below.
The elements are arranged linearly.

We have two ends i.e. “front” and “rear” of the queue. When the queue is empty, then both
the pointers are set to -1.

The “rear” end pointer is the place from where the elements are inserted in the queue. The
operation of adding /inserting elements in the queue is called “enqueue”.

The “front” end pointer is the place from where the elements are removed from the queue.
The operation to remove/delete elements from the queue is called “dequeue”.

When the rear pointer value is size-1, then we say that the queue is full. When the front is
null, then the queue is empty.

Why we want to implement Queue using linked list?

The major problem with the queue implemented using array is, it will work for only fixed
number of data values. That means, the amount of data must be specified in the beginning
itself.
Queue using array is not suitable when we do not know the size of data which we are
going to use.
A queue data structure can be implemented using linked list data structure. The queue
which is implemented using linked list can work for unlimited number of values.
That means, queue using linked list can work for variable size of data (No need to fix the size
at beginning of the implementation). The Queue implemented using linked list can organize
as many data values as we want.

We will implement Queue using linked list. Queues maintain two data pointers:

 FRONT: to know first inserted element

 REAR to know last inserted element.

Queue is very simple data structure; you only have to manipulate FRONT and REAR to get
Queue property.

Basic Operations

Following are basic operations of Queue:

Main Queue Operations

1)EnQueue(): Inserts an element at the rear of the Queue.

2)DeQueue(): Remove and return the front element of the Queue.
Auxiliary Queue operation

1)Front(): Display the data front of the Queue.

2)QueueSize(): Returns the number of elements stored in the Queue.
3)display(): Display elements of queue.
There are many different operations that we can implement.
For ex.: - Merging of Two Queue, Sorting of Queue etc.

 Let's see implementation of Queue and its operations, with example.

For linked list we will make structure of Node using struct keyword. In which we here
taking int data and one pointer of that struct to point another Node.

 First, we will take two pointers of that struct Node, front=NULL and rear=NULL.

Enqueue

In this process, the following steps are performed:

 Check if the queue is full.
 If full, produce overflow error and exit.
 Else, increment ‘rear’.
 Add an element to the location pointed by ‘rear’.
 Return success.
Dequeue

Dequeue operation consists of the following steps:

 Check if the queue is empty.
 If empty, display an underflow error and exit.
 Else, the access element is pointed out by ‘front’.
 Increment the ‘front’ to point to the next accessible data.
 Return success.
Next, we will see a detailed illustration of insertion and deletion operations in queue.
Illustration

This is an empty queue and thus we have rear and empty set to -1.

Next, we add 1 to the queue and as a result, the rear pointer moves ahead by one location.

In the next figure, we add element 2 to the queue by moving the rear pointer ahead by another
increment.

In the following figure, we add element 3 and move the rear pointer by 1.

At this point, the rear pointer has value 2 while the front pointer is at the 0th location.
Next, we delete the element pointed by the front pointer. As the front pointer is at 0, the
element that is deleted is 1.
Thus, the first element entered in the queue i.e. 1 happens to be the first element removed
from the queue. As a result, after the first dequeue, the front pointer now will be moved ahead
to the next location which is 1.

#include <iostream>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node* front = NULL;
struct node* rear = NULL;
struct node* temp;
void Insert() {
int val;
cout<<"Insert the element in queue : "<<endl;
cin>>val;
if (rear == NULL) {
rear = (struct node *)malloc(sizeof(struct node));
rear->next = NULL;
rear->data = val;
front = rear;
} else {
temp=(struct node *)malloc(sizeof(struct node));
rear->next = temp;
temp->data = val;
temp->next = NULL;
rear = temp;
}
}
void Delete() {
temp = front;
if (front == NULL) {
cout<<"Underflow"<<endl;
return;
}
else
if (temp->next != NULL) {
temp = temp->next;
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = temp;
} else {
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = NULL;
rear = NULL;
}
}
void Display() {
temp = front;
if ((front == NULL) && (rear == NULL)) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are: ";
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}
int main() {
int ch;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : "<<endl;
cin>>ch;
switch (ch) {
case 1: Insert();
break;
case 2: Delete();
break;
case 3: Display();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);
return 0;
}

 In the above program, the function Insert () inserts an element into the queue. If rear is
NULL,then the queue is empty and a single element is inserted. Otherwise, a node is
inserted after rear with the required element and then that node is set to rear.
 In the function Delete(), if there are no elements in queue then it is underflow
condition. If there is only one element in the queue that is deleted and front and rear
are set to NULL. Otherwise, the element at front is deleted and front points to next
element.
 In the function display(), if front and rear are NULL then queue is empty. Otherwise,
all the queue elements are displayed using a while loop with the help of temp
variable.
 The function main() provides a choice to the user if they want to insert, delete or
display the queue. According to the user response, the appropriate function is called
using switch. If the user enters an invalid response, then that is printed.

Output

The output of the above program is as follows

1) Insert element to queue

2) Delete element from queue
3) Display all the elements of queue
4) Exit

Enter your choice : 1

Insert the element in queue : 4
Enter your choice : 1
Insert the element in queue : 3
Enter your choice : 1
Insert the element in queue : 5
Enter your choice : 2
Element deleted from queue is : 4
Enter your choice : 3
Queue elements are : 3 5
Enter your choice : 7
Invalid choice
Enter your choice : 4
Exit