Queue using linked list c++

In this post, you will learn how to implement a Queue using C++ programming language.

A queue is a linear data structure where insertion of element is done from one end and deletion from the other end. The queue is like a line of person at polling booth where the first person in the line is first voted. This is called First-In-First-Out (FIFO). Insertion of the element is done from the one end called FRONT end and deletion is done from the other end called REAR.

Queue Operations

These are the operations performed by a queue.

Enqueue - The element to add in a queue. If the queue is full, then it is said to be an overflow condition.
Dequeue - The element to delete in a queue. If the queue is empty, then it is said to be an underflow condition.
Peek - Retrieve the element from the front end of the queue without removing it from the queue.
IsEmpty - Check if the queue is empty or not.
Size - Return the total number of elements present in the queue.
Front - Get the front item from queue.
Rear - Get the last item from queue.

Algorithm to Insert Element in a Queue

Step 1: IF REAR = MAX-1
	print('Queue Overflow')
	return
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT

In the above algorithm, we have checked the existence of space in the queue. If there is no space then print 'Queue Overflow' and the code is exited and if not then, we check the element at the FRONT and REAR, if both are empty then set both to 0 else increase REAR with one and insert element from the REAR end and return.

Algorithm to Delete Element in a Queue

Step 1: IF FRONT = -1 OR FRONT > REAR
	print('Queue Underflow')
	return
ELSE
SET FRONT = FRONT + 1
[END OF IF]
Step 2: EXIT

In the above algorithm, we have checked the existence of elements in the queue. If there is no any element, then print 'Queue Underflow' and the code is exited and if not, then FRONT is increased by one and point to the next element in the queue.

Queue Implementation using linked list in C++

The linked list is a non primitive data structure which is free from fixed memory size restriction. It is static free and user can add any number of elements when required. We can use this to create other data structures, like stacks, queues, etc. It allows the insertion and deletion of nodes at any point in the list.

The function enqueue() inserts an element into the queue. Initially it checks, 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 dequeue(), firstly check if the queue is empty. If it is, then print the result as "Queue Underflow". 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 the next element.

In the function show(), if front and rear are NULL then queue is empty. Otherwise, using while loop print all the queue elements starting from front to rear with the help of temp variable.

#include <iostream>
using namespace std;
struct node {
   int data;
   struct node *next;
};
struct node* front = NULL;
struct node* rear = NULL;
struct node* temp;

void enqueue() {
   int val;
   cout<<"Enter value to inset in queue : ";
   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 dequeue() {
   temp = front;
   if (front == NULL) {
      cout<<"QUEUE UNDERFLOW!"<<endl;
      return;
   }
   else
   if (temp->next != NULL) {
      temp = temp->next;
      cout<<"Element deleted from queue : "<<front->data<<endl;
      free(front);
      front = temp;
   } else {
      cout<<"Element deleted from queue : "<<front->data<<endl;
      free(front);
      front = NULL;
      rear = NULL;
   }
}
void show() {
   temp = front;
   if ((front == NULL) && (rear == NULL)) {
      cout<<"QUEUE UNDERFLOW!"<<endl;
      return;
   }
   while (temp != NULL) {
      cout<<temp->data<<" ";
      temp = temp->next;
   }
   cout<<endl;
}
int main() {
   int choice;
   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 : ";
      cin<<choice;
      switch (choice) {
         case 1: enqueue();
         break;
         case 2: dequeue();
         break;
         case 3: show();
         break;
         case 4: cout<<"Exit"<<endl;
         break;
         default: cout<<"Invalid choice"<<endl;
      }
   } while(choice!=4);
   return 0;
}

Output of the above code:

1) Insert element to queue
2) Delete element from queue
3) Display all the elements of queue
4) Exit
Enter your choice : 1
Enter value to inset in queue : 39
Enter your choice : 1
Enter value to inset in queue : 90
Enter your choice : 3
39 90 
Enter your choice : 2
Element deleted from queue : 39
Enter your choice : 3
90 
Enter your choice :

Implementation of queue using array in C
Queue implementation in Python
Queue Implementation in C
Capitalize first letter of each word Java
Convert binary to decimal in Java
Convert array to list Python
Python take screenshot of specific window
Web scraping Python BeautifulSoup
Check if two strings are anagrams Python
Python program to add two numbers
Print new line python
Prime factors of a number in c
Armstrong number program in c
Write a program to check leap year in c
C program to find area of rectangle
C program to convert celsius to fahrenheit
Fibonacci series program in C using recursion
Write a program to find area of circle in C
C program to convert Decimal to Octal
C program to convert decimal to binary
C program to check whether a number is even or odd