Priority Queue implementation using Linked List

Introduction - What is priority Queue

A priority queue is an abstract data type (ADT) supporting the following three operations:

1. Add an element to the queue with an associated priority
2. Remove the element from the queue that has the highest priority, and return it
3. (optionally) peek at the element with highest priority without removing it

The Code

Code:

#include <iostream.h>
#include <stdlib.h>

enum{FALSE=0,TRUE=-1};

/////////////////////////////////
///// Implements Priority Queue
/////////////////////////////////

class PriorityQueue		// Class Prioriry Queue
{
private:
	struct Node			// Node of Priority Queue
	{
		struct Node *Previous;
		int Data;
		struct Node *Next;
	}Current;
	struct Node *head;	// Pointer to Head
	struct Node *ptr;	
		// Pointer for travelling through Queue
	static int NumOfNodes;
		// Keeps track of Number of nodes
public:
	PriorityQueue(void);
	int Maximum(void);
	int Minimum(void);
	void Insert(int);
	int Delete(int);
	void Display(void);
	int Search (int);
	~PriorityQueue(void);
};
// First Nodes Created With Constructor
int PriorityQueue::NumOfNodes=1;
// Constructor
PriorityQueue::PriorityQueue(void)
{
	Current.Previous=NULL;
	cout<<"Enter First Element of Queue"<<endl;
	cin>>Current.Data;
	Current.Next=NULL;
	head=&Current;
	ptr=head;
}
// Function Finding Maximum Priority Element
int PriorityQueue::Maximum(void)
{
	int Temp;
	ptr=head;
	Temp=ptr->Data;

	while(ptr->Next!=NULL)
	{
		if(ptr->Data>Temp)
			Temp=ptr->Data;
		ptr=ptr->Next;
	}
	if(ptr->Next==NULL && ptr->Data>Temp)
		Temp=ptr->Data;
	return(Temp);
}
// Function Finding Minimum Priority Element
int PriorityQueue::Minimum(void)
{
	int Temp;
	ptr=head;
	Temp=ptr->Data;

	while(ptr->Next!=NULL)
	{
		if(ptr->Data<Temp)
			Temp=ptr->Data;
		ptr=ptr->Next;
	}
	if(ptr->Next==NULL && ptr->Data<Temp)
		Temp=ptr->Data;
	return(Temp);
}
// Function inserting element in Priority Queue
void PriorityQueue::Insert(int DT)
{
	struct Node *newnode;
	
	newnode=new Node;

	newnode->Data=DT;

	while(ptr->Next!=NULL)
		ptr=ptr->Next;
	if(ptr->Next==NULL)
	{
		newnode->Next=ptr->Next;
		ptr->Next=newnode;
	}
	NumOfNodes++;
}
// Function deleting element in Priority Queue
int PriorityQueue::Delete(int DataDel)
{
	struct Node *mynode,*temp;

	ptr=head;
	
	if(NumOfNodes==1)
	{
		cout<<"Cannot Delete the only Node"<<endl;
		return FALSE;
	}
	if(ptr->Data==DataDel)
	{
		/***  Checking condition for deletion of first node  ***/
		temp=ptr;
		ptr=ptr->Next;
		ptr->Previous=NULL;
		//delete temp;
		head=ptr;
		NumOfNodes--;
		return(TRUE);
	}
	else
	{
		while(ptr->Next->Next!=NULL)
		{
			/***  Checking condition for deletion of   ***/
			/*** all nodes except first and last node  ***/
			if(ptr->Next->Data==DataDel)
			{
				mynode=ptr;
				temp=ptr->Next;
				mynode->Next=mynode->Next->Next;
				mynode->Next->Previous=ptr;
				delete temp;
				NumOfNodes--;
				return(TRUE);
			}
			ptr=ptr->Next;
		}
		if(ptr->Next->Next==NULL && ptr->Next->Data==DataDel)
		{
			/***  Checking condition for deletion of last node  ***/
			temp=ptr->Next;
			delete temp;
			ptr->Next=NULL;
			NumOfNodes--;
			return(TRUE);
		}
	}
	return(FALSE);
}
// Function Searching element in Priority Queue
int PriorityQueue::Search(int DataSearch)
{
	ptr=head;

	while(ptr->Next!=NULL)
	{
		if(ptr->Data==DataSearch)
			return ptr->Data;
		ptr=ptr->Next;
	}
	if(ptr->Next==NULL && ptr->Data==DataSearch)
		return ptr->Data;
	return(FALSE);
}
// Function Displaying elements of Priority Queue
void PriorityQueue::Display(void)
{
	ptr=head;
	cout<<"Priority Queue is as Follows:-"<<endl;
	while(ptr!=NULL)
	{
		cout<<ptr->Data<<endl;
		ptr=ptr->Next;
	}
}
// Destructor of Priority Queue
PriorityQueue::~PriorityQueue(void)
{
	struct Node *temp;                      /* Temporary variable */
	while(head->Next!=NULL)
	{
		temp=head->Next;
//		delete head;
		head=temp;
	}
	if(head->Next==NULL)
		delete head;
}
//Main Function
void main()
{
	PriorityQueue PQ;
	int choice;
	int DT;

	while(1)
	{
		cout<<"Enter your choice"<<endl;
		cout<<"1. Insert an element"<<endl;
		cout<<"2. Display a priorty Queue"<<endl;
		cout<<"3. Delete an element"<<endl;
		cout<<"4. Search an element"<<endl;
		cout<<"5. Exit"<<endl;
		cin>>choice;
		switch(choice)
		{
		case 1:
			cout<<"Enter a Data to enter Queue"<<endl;
			cin>>DT;
			PQ.Insert(DT);
			break;
		case 2:
			PQ.Display();
			break;
		case 3:
			{
				int choice;
				cout<<"Enter your choice"<<endl;
				cout<<"1. Maximum Priority Queue"<<endl;
				cout<<"2. Minimum Priority Queue"<<endl;
				cin>>choice;
				switch(choice)
				{
				case 1:
					PQ.Delete(PQ.Maximum());
					break;
				case 2:
					PQ.Delete(PQ.Minimum());
					break;
				default:
					cout<<"Sorry Not a correct choice"<<endl;
				}
			}
			break;
		case 4:
			cout<<"Enter a Data to Search in Queue"<<endl;
			cin>>DT;
			if(PQ.Search(DT)!=FALSE)
				cout<<DT<<" Is present in Queue"<<endl;
			else
				cout<<DT<<" is Not present in Queue"<<endl;
			break;
		case 5:
			exit(0);
		default:
			cout<<"Cannot process your choice"<<endl;
		}
	}
}

Dont copy but you can download the file as an attachment.

This is the priority Queue implementation and the Queue implementation can be refered here - Queue implementation using Linked List.

 

You need to sort your linked list

 

Search the forum and you will find that too.

 

Re: data in order by maximum

What you mean by order of maximum node?