Go4Expert

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 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.

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
 
You need to sort your 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.........

thanks in advance,
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.


All times are GMT +5.5. The time now is 23:30.