# Priority Queue implementation using Linked List

Discussion in 'C++' started by shabbir, Oct 15, 2006.

Joined:
Jul 12, 2004
Messages:
15,376
388
Trophy Points:
83

### 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 *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;
}
// Function Finding Maximum Priority Element
int PriorityQueue::Maximum(void)
{
int Temp;
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;
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
{
struct Node *mynode,*temp;

if(NumOfNodes==1)
{
cout<<"Cannot Delete the only Node"<<endl;
return FALSE;
}
{
/***  Checking condition for deletion of first node  ***/
temp=ptr;
ptr=ptr->Next;
ptr->Previous=NULL;
//delete temp;
NumOfNodes--;
return(TRUE);
}
else
{
while(ptr->Next->Next!=NULL)
{
/***  Checking condition for deletion of   ***/
/*** all nodes except first and last node  ***/
{
mynode=ptr;
temp=ptr->Next;
mynode->Next=mynode->Next->Next;
mynode->Next->Previous=ptr;
delete temp;
NumOfNodes--;
return(TRUE);
}
ptr=ptr->Next;
}
{
/***  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)
{

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)
{
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 */
{
}
}
//Main Function
void main()
{
PriorityQueue PQ;
int choice;
int DT;

while(1)
{
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<<"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:
}
}
}```

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

File size:
1.5 KB
Views:
1,226
2. ### aisha.ansari84New Member

Joined:
Feb 13, 2008
Messages:
82
1
Trophy Points:
0
priprity queues are good but for implementing them we should be thorough with our purpose

3. ### rahul.mca2001New Member

Joined:
Feb 13, 2008
Messages:
103
0
Trophy Points:
0
i agree

4. ### programming girlNew Member

Joined:
Apr 24, 2008
Messages:
8
0
Trophy Points:
0
yes , I used it in my solution in homework

5. ### rawahNew Member

Joined:
Apr 23, 2008
Messages:
7
0
Trophy Points:
0
hello

that is great

i want to ask u shabbir
if i want to insert the data in order by maximum node how can i do that in this function that i have it

Code:
```// ------------- Insert ----------------//
template <class type>
void priorityqueue<type>::insert(type datain)
{
if(numberofnodes==0)
{
node<type> *current;
current=new node<type>;
current->previous=NULL;
current->next=NULL;
current->data=datain;
}
else
if(numberofnodes>0)
{
node<type> *pnew;
pnew= new node<type>;
pnew->data=datain;
while(ptr->next!=NULL)
ptr=ptr->next;
if(ptr->next==NULL)
{
pnew->next=ptr->next;
ptr->next=pnew;
}
}
numberofnodes++;
}```
NOTE: i want the nodes ordered by maximum

------------------------------------------------------------------------------------------
another question
your display function is good but if i want it print the all nodes from maximum to minimum node
what is the modification ?????

thanx

Last edited by a moderator: Apr 30, 2008

Joined:
Jul 12, 2004
Messages:
15,376
388
Trophy Points:
83

7. ### rawahNew Member

Joined:
Apr 23, 2008
Messages:
7
0
Trophy Points:
0
hello shabbir,

yes i mean sort the list

Joined:
Jul 12, 2004
Messages:
15,376
388
Trophy Points:
83
Search the forum and you will find that too.

9. ### siyaNew Member

Joined:
Oct 15, 2008
Messages:
2
0
Trophy Points:
0
hi shabbir,

Thanks for your immediate reply......the code is actually a bouncer to me....i forgot to mention in my post that i dont require the code....a simple explanation of how to execute that would be enough.......it would be helpful if you can explain the whole thing in simple language.........

siya

10. ### ban1414New Member

Joined:
Oct 25, 2008
Messages:
3
0
Trophy Points:
0
data in order by maximum

that is great

i want to ask u shabbir
if i want to insert the data in order by maximum node how can i do that in this function that i have it.

Joined:
Jul 12, 2004
Messages:
15,376
388
Trophy Points:
83
Re: data in order by maximum

What you mean by order of maximum node?

12. ### hkp819New Member

Joined:
Dec 4, 2008
Messages:
59
1
Trophy Points:
0
this program is very helpful for me. But same question is for you that if i want to insert the data order by maximum to minimum node than what would be the function.

13. ### salyNew Member

Joined:
Jan 4, 2010
Messages:
1
0
Trophy Points:
0
thank you so much

14. ### Sneha MohanNew Member

Joined:
Apr 25, 2010
Messages:
1
0
Trophy Points:
0
same here thanks tis helped me in scoring good marks

15. ### hj9cNew Member

Joined:
Oct 30, 2010
Messages:
1
0
Trophy Points:
0
Occupation:
Software Engineering
Location:
Pakistan
very nice !! thnx mate !

16. ### sushilnNew Member

Joined:
Nov 9, 2010
Messages:
1
0
Trophy Points:
0
Is "Current" an integer variable? It is not initialized in the beginning of your code.

Niten

17. ### Salman786New Member

Joined:
Jan 11, 2011
Messages:
1
0
Trophy Points:
0
Salam to all , im new here , would i'll get answer for every questions on programming knowledge here?

Joined:
Feb 16, 2011
Messages:
4