1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

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

    priprity queues are good but for implementing them we should be thorough with our purpose
     
  3. rahul.mca2001

    rahul.mca2001 New Member

    i agree
     
  4. programming girl

    programming girl New Member

    yes , I used it in my solution in homework :)
     
  5. rawah

    rawah New Member

    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

    You need to sort your linked list
     
  7. rawah

    rawah New Member

    hello shabbir,

    yes i mean sort the list
     
  8. shabbir

    shabbir Administrator Staff Member

    Search the forum and you will find that too.
     
  9. siya

    siya New Member

    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

    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

    Re: data in order by maximum

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

    hkp819 New Member

    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

    thank you so much
     
  14. Sneha Mohan

    Sneha Mohan New Member

    same here thanks :)tis helped me in scoring good marks:)
     
  15. hj9c

    hj9c New Member

    very nice :D !! thnx mate :) !
     
  16. sushiln

    sushiln New Member

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

    Niten
     
  17. Salman786

    Salman786 New Member

    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

    Great sharing
     

Share This Page