1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Priority Queue implementation using Linked List

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

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

    Attached Files:

  2. aisha.ansari84

    aisha.ansari84 New Member

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

    rahul.mca2001 New Member

    Joined:
    Feb 13, 2008
    Messages:
    103
    Likes Received:
    0
    Trophy Points:
    0
    i agree
     
  4. programming girl

    programming girl New Member

    Joined:
    Apr 24, 2008
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    yes , I used it in my solution in homework :)
     
  5. rawah

    rawah New Member

    Joined:
    Apr 23, 2008
    Messages:
    7
    Likes Received:
    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;
    		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
     
    Last edited by a moderator: Apr 30, 2008
  6. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    You need to sort your linked list
     
  7. rawah

    rawah New Member

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

    yes i mean sort the list
     
  8. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    Search the forum and you will find that too.
     
  9. siya

    siya New Member

    Joined:
    Oct 15, 2008
    Messages:
    2
    Likes Received:
    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.........

    thanks in advance,
    siya
     
  10. ban1414

    ban1414 New Member

    Joined:
    Oct 25, 2008
    Messages:
    3
    Likes Received:
    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.
     
  11. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    Re: data in order by maximum

    What you mean by order of maximum node?
     
  12. hkp819

    hkp819 New Member

    Joined:
    Dec 4, 2008
    Messages:
    59
    Likes Received:
    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. saly

    saly New Member

    Joined:
    Jan 4, 2010
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    thank you so much
     
  14. Sneha Mohan

    Sneha Mohan New Member

    Joined:
    Apr 25, 2010
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    same here thanks :)tis helped me in scoring good marks:)
     
  15. hj9c

    hj9c New Member

    Joined:
    Oct 30, 2010
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Software Engineering
    Location:
    Pakistan
    very nice :D !! thnx mate :) !
     
  16. sushiln

    sushiln New Member

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

    Niten
     
  17. Salman786

    Salman786 New Member

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

    Naveed Marwat New Member

    Joined:
    Feb 16, 2011
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0

Share This Page