Implement Queue using Linked list in C++ Algorithm

Implement Queue Linked Lists C++

Introduction:

Implementing Queues using Linked Lists or Pointers is an effective way of the utilization of memory.

The queue is a Linear Data Structure like Arrays and Stacks.
It is a homogenous ( similar ) collection of elements in which new elements are inserted at one end Called the Rear end, and the existing elements are deleted from the other end called the Front end.

A Queue is logically a First in First Out ( FIFO ) type of data structure.
Or Queue simply means a line and follows FIFO logical design, which means the element inserted first will be deleted first.

There are two main ways to implement queues.

1. Queue Using Arrays.
2. Queue Using Linked Lists.

Implement Queue Linked Lists in C++ | Dynamic Queue.

Implementing Queues using Pointers is an effective way of the utilization of memory.
Since it is dynamic therefore you don’t need to worry about the size of the queue It will grow and shrink at the run time.

In Arrays, if you want to add or delete elements in the middle then you have to shift all the existing elements.

But in Linked Lists, You only have to insert a new node and adjust the links of the newly inserted node with the rest of the nodes.

C++ Program Queue using Linked lists

// Wikkihut.com
	//Queue Using Linked Lists
	
#include<iostream>
#include<stdio.h>
#include<conio.h>	
#include<process.h>

using namespace std;

struct queue
{
	int data;
	queue *next;
};

	
 class QueueList
{
	public:
	queue *Front,*Rear;

	void enque();
	int deque();
	void display();
	QueueList()
	{
			Front=NULL;
			Rear=NULL;
	}
};

void QueueList::enque()
{	
 int n;
 queue *temp;
 temp=new queue;
  temp->data=n;
 temp->next=NULL;

	if(Rear==NULL && Front==NULL)
	{
		Rear=temp;
		Front=temp;
	}
	else
	{
		Rear->next=temp;
		Rear=temp;
	}
	delete temp;
 }
 
 
 int QueueList::deque()
 {
	queue *temp=new queue;
	int element;
	if(Front==NULL)
	{
		cout<<"Queue empty";
		return -1;
	}
	else
	{
		temp=Front;
		Front=Front->next;
		element=temp->data;
		delete temp;
	}
	return element;
 }
 
 void QueueList::display()
 {
	queue *temp;
	if(Front==NULL)
	{
		cout<<"Queue empty:";
 }
 else
 {
	temp=Front;
	cout<<"elements of queue are: /t";

	while(temp!=NULL)
	{
		cout<<temp->data;
		temp=temp->next;
	}
	delete temp;
}
}

 int main()
 {
	QueueList q;
	int ch, element;
			cout<<" Press 1 to Enque \n";
			cout<<" Press 2 to Deque: \n";
			cout<<" Press 3 for Display: \n";
			cout<<" Press 4 for Exit: \n";
		  	cout<<"\t enter choice \t";
		  cin>>ch;
		   switch(ch)
		 {
		 	case 1:
		 		q.enque();
		 		break;
			case 2:
				element=q.deque();
				cout<<"Element dequed  is "<<element<<endl;
				break;
			case 3:
				q.display();
				break;
			case 4:
				return 0;
			default:
				cout<<"Invalid choice:";
		 }
		 return 0;
	//techindetail.com
	}Code language: C++ (cpp)

Algorithm & Design

Note: There may be a slight difference in variable names and functions.

Let Queue be a Structure whose declaration will look like.

Algorithm for Insertion

First Create two nodes Ptr and temp
.

Algorithm for Deletion

.

Advantages of Queue using linked lists

Memory efficient

Linked representation of queues is the effective and proper utilization of memory.

There is no memory wasted in linked lists because the data elements are stored at distant places in the memory whose addresses are linked by pointers.

Time efficient

There is no need to worry about deleting the element in the middle because it requires same amount of time to Insert at front and middle.

It is a very useful data structure that is used in various aspects of programming fields and in the software development process.

Types of Queues

• Circular Queue.
• Double-ended Queue ( de-queue ).
• Priority Queue.

1. Circular Queue

A circular queue overcomes the problem of unutilized space in linear or simple queues implemented by arrays.

In the circular queue, the insertion of a new element is done at the very first location of the queue if the last location is full.

2. Double Ended Queue

It is also a similar list of elements in which insertion and deletion operations are performed from both ends.

That is, we can insert elements from the Rear as well as at the Front end, and we can delete from both Front and Rear end.

3. Priority Queue

In some Situations, the items added to the queue have a priority associated with them.

So this priority determines the order in which they are served or the highest priority items are removed first. This situation arises most often in Process Control Systems.