Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/articles/cpp-tutorials/)
-   -   Priority Queue implementation using Linked List (http://www.go4expert.com/articles/priority-queue-implementation-using-t1633/)

 shabbir 15Oct2006 14:30

Priority Queue implementation using Linked List

1 Attachment(s)

### 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: CPP

`#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 nodespublic:    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 Constructorint PriorityQueue::NumOfNodes=1;// ConstructorPriorityQueue::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 Elementint 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 Elementint 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 Queuevoid 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 Queueint 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 Queueint 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 Queuevoid 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 QueuePriorityQueue::~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 Functionvoid 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;        }    }}`

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

 aisha.ansari84 5Mar2008 18:53

Re: Priority Queue implementation using Linked List

priprity queues are good but for implementing them we should be thorough with our purpose

 rahul.mca2001 6Mar2008 13:18

Re: Priority Queue implementation using Linked List

Quote:
 Originally Posted by aisha.ansari84 priprity queues are good but for implementing them we should be thorough with our purpose
i agree

 programming girl 28Apr2008 23:27

Re: Priority Queue implementation using Linked List

yes , I used it in my solution in homework :)

 rawah 30Apr2008 13:07

Re: Priority Queue implementation using Linked List

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;                 head=current;                 ptr=head;         } 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

 shabbir 30Apr2008 17:54

Re: Priority Queue implementation using Linked List

 rawah 30Apr2008 21:49

Re: Priority Queue implementation using Linked List

hello shabbir,

yes i mean sort the list

 shabbir 1May2008 11:25

Re: Priority Queue implementation using Linked List

Search the forum and you will find that too.

 siya 15Oct2008 20:27

Re: Priority Queue implementation using Linked List

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

 ban1414 25Oct2008 13:32

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.

 shabbir 25Oct2008 15:51

Re: data in order by maximum

Quote:
 Originally Posted by ban1414 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.
What you mean by order of maximum node?

 hkp819 5Dec2008 15:15

Re: Priority Queue implementation using Linked List

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.

 saly 5Jan2010 01:13

Re: Priority Queue implementation using Linked List

thank you so much

 Sneha Mohan 25Apr2010 14:42

Re: Priority Queue implementation using Linked List

Quote:
 Originally Posted by programming girl (Post 27911) yes , I used it in my solution in homework :)
same here thanks :)tis helped me in scoring good marks:)

 hj9c 30Oct2010 19:29

Re: Priority Queue implementation using Linked List

very nice :D !! thnx mate :) !

 sushiln 9Nov2010 08:27

Re: Priority Queue implementation using Linked List

Is "Current" an integer variable? It is not initialized in the beginning of your code.

Niten

 Salman786 17Jan2011 12:39

Re: Priority Queue implementation using Linked List

Salam to all , im new here , would i'll get answer for every questions on programming knowledge here?

 Naveed Marwat 1Mar2011 12:01

Re: Priority Queue implementation using Linked List

Great sharing

 All times are GMT +5.5. The time now is 10:31.