Solved

Priority Queues

Posted on 2003-11-19
7
829 Views
Last Modified: 2010-04-01
I am trying to implement a priority queue in c++.  The queue is a list of nodes that have a value and a priority, and a pointer to the next node and a pointer to the previous node in the list.  

I am stuck on how to scan through the list and insert a value into the queue.  

I can set a pointer variable to a node equal to the first node in the list, and then scan through to find the correct place to insert the new node.  However my problem arises here: how do I set the previous nodes next pointer to the node I am trying to insert, as I have already scanned past it?

Ask if you need more
Thanks
Ashley :-)
0
Comment
Question by:ashleycoker
7 Comments
 

Author Comment

by:ashleycoker
ID: 9781565
Here is the code I have already implemented using a singly linked list instead of a doubly linked list explained before.  Please see comments in the insert function for what I am having trouble doing:

#ifndef PRIORITYQUEUE_H
#define PRIORITYQUEUE_H

class list{

      friend class PriorityQueue;
      int data;
      int priority;
      list* next;

      list(int n=0, int t=0);
};
 
class PriorityQueue{
      
private:
      list* tab;
public:
      PriorityQueue();
      ~PriorityQueue();

      void insert(int n, int t);
      int remove();
      int length();
      int elementAt(int p);
      int priorityAt(int p);

};

#endif






#include<iostream>
#include"PriorityQueue.h"
using namespace std;

list::list(int n, int t) // List contructor to create a queue node
{
      data=n;
      priority=t;
      next = NULL;
}

PriorityQueue::PriorityQueue()
{
      tab=NULL;
}

PriorityQueue :: ~PriorityQueue()
{
      list* curr=tab;
      list* after;
      while(curr)
      {
            after=curr->next;
            delete curr;
            curr=after;
      }
}

void PriorityQueue::insert(int n, int t)
{
      list* insertion=new list(n,t);
      if(tab==NULL)
            tab=insertion;
      else
      {
            if(tab->priority>t)
            {
                  insertion->next=tab;
            }
            else
            {
                  // Need to scan through tab and insert "insertion"
                  // into the point in the queue where "t" is smaller
                  // than all the priorities before it.  If the priority
                  // already exists it needs to be inserted after them.
                  list* scan_tab=tab;
                  scan_tab=scan_tab->next;
                  while((scan_tab)&&(scan_tab->priority<=t))
                  {
                        scan_tab=scan_tab->next;
                  }
                  insertion->next=scan_tab;
                  // Need to now add the queue "insertion" to the queue
                  // with the lower priorities
}
      
int PriorityQueue :: remove()
{
      if(tab==NULL)
            return -1;
      else
      {
            int return_value=tab->data;
            tab=tab->next;
            return return_value;
      }
}

int PriorityQueue :: length()
{
      int count=0;
      list* scan_tab;
      // Loops until scan_tab->next==NULL
      for(scan_tab=tab; scan_tab; scan_tab=scan_tab->next)
      {
            count++;
      }
      return count;      
}

int PriorityQueue :: elementAt(int p)
{
      int count=0;
      list* scan_tab;
      for(scan_tab=tab; scan_tab; scan_tab=scan_tab->next)
      {
            count++;
      }
      if(count>=p)
      {
            list* scan_tab=tab;
            for(int i=1; i<p; i++)
            {
                  scan_tab=scan_tab->next;
            }
            return scan_tab->data;
      }
      else
            return -1;
}

int PriorityQueue :: priorityAt(int p)
{
      int count=0;
      list* scan_tab;
      for(scan_tab=tab; scan_tab; scan_tab=scan_tab->next)
      {
            count++;
      }
      if(count>=p)
      {
            list* scan_tab=tab;
            for(int i=1; i<p; i++)
            {
                  scan_tab=scan_tab->next;
            }
            return scan_tab->priority;
      }
      else
            return -1;
}

Thanks again

Ashley
0
 
LVL 86

Expert Comment

by:jkr
ID: 9781589
>>I am trying to implement a priority queue in c++.  

Why not using std::priority_queue? See e.g. ("priority_queue functions (STL Sample)")

#include <iostream>
#include <queue>
#include <deque>
#include <vector>
#include <functional>

using namespace std ;

// Using priority_queue with deque
// Use of function greater sorts the items in ascending order
typedef deque<int> INTDQU;
typedef priority_queue<int> INTPRQUE;

// Using priority_queue with vector
// Use of function less sorts the items in descending order
typedef vector<char> CHVECTOR;
typedef priority_queue<char> CHPRQUE;

void main(void)
{
    int size_q;
    INTPRQUE   q;
    CHPRQUE    p;

    // Insert items in the priority_queue(uses deque)
    q.push(42);
    q.push(100);
    q.push(49);
    q.push(201);

 

    // Output the size of priority_queue
    size_q = q.size();
    cout << "size of q is:" << size_q << endl;

   // Output items in priority_queue using top()
    // and use pop() to get to next item until
    // priority_queue is empty
    while (!q.empty())
    {
        cout << q.top() << endl;
        q.pop();

    }

// Insert items in the priority_queue(uses vector)
    p.push('c');
    p.push('a');
    p.push('d');
    p.push('m');
    p.push('h');

    // Output the item at the top using top()
    cout << p.top() << endl;

    // Output the size of priority_queue
    size_q = p.size();
    cout << "size of p is:" << size_q << endl;

    // Output items in priority_queue using top()
    // and use pop() to get to next item until
    // priority_queue is empty
    while (!p.empty())
    {
        cout << p.top() << endl;
        p.pop();

    }
}

Program Output:

size of q is:4
201
100
49
42
m
size of p is:5
m
h
d
c
a

0
 

Author Comment

by:ashleycoker
ID: 9781642
Can you see how i need to modify what I have already written.  This is ,y own personal project to introduce me to c++ and have been working on iot for ages now.  I am new to programming and don't understand the code you just sent me.

Thanks a bunch
Ashley :-)
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 11

Expert Comment

by:bcladd
ID: 9784083
ashleycoker-

Doubly linked lists are easier to insert into than singly linked lists. The one thing you need, though, is a pointer at the node that comes BEFORE the node you want to insert. That way if the node "before" is NULL you know your node goes in at the head and if "before" isn't NULL you can find the next node using "before's" next pointer.

I am going to modify your code and wave my hands at it (what I give will probably compile but won't be complete). From your insert routine:

              list* before = NULL;
              list* scan_tab=tab;
               scan_tab=scan_tab->next;
               while((scan_tab)&&(scan_tab->priority<=t))
               {
                    before = scan_tab;
                    scan_tab=scan_tab->next;
               }

               insertion->next=scan_tab;
               // --- Here is where you need to do more work

What work do you need to do? You need to point insertion at the node that comes after it. Wait, you do that. You need to point insertion at the node that comes before it. You need to point the node (IF ANY; if there isn't one, you need to point tab at insertion) that comes before insertion at insertion. You need to point the node (IF ANY) that comes after insertion back at insertion.

Hope this helps.
-bcl
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 9787007
Here's an illustration of jkr's priority queue:
--------8<--------
#include <iostream>
#include <queue>
#include <string>

// General purpose class
template<class T,class P> struct Prioritised {
      T t;
      P priority;
      Prioritised(const T& t,int priority = 0) : t(t),priority(priority) {}
      bool operator< (const Prioritised<T,P>& p) const {return priority < p.priority;}
};

int main()
{
      typedef Prioritised<std::string,int> PrioritisedString;

      std::priority_queue<PrioritisedString> queue;

      queue.push(PrioritisedString("Love",100));
      queue.push(PrioritisedString("Peace",50));
      queue.push(PrioritisedString("Wealth",20));
      queue.push(PrioritisedString("Happiness",150));

      while (!queue.empty()) {
            std::cout << queue.top().t << '\n';
            queue.pop();
      }
}
--------8<--------

In this illustration, ints are used to designate priority and I've used std::string as the "data". In your code, you are using ints also as the data. You can so that using the same template as follows:

--------8<--------
#include <iostream>
#include <queue>
//#include <string> // Don't need this now

// General purpose class
template<class T,class P> struct Prioritised {
      T t;
      P priority;
      Prioritised(const T& t,int priority = 0) : t(t),priority(priority) {}
      bool operator< (const Prioritised<T,P>& p) const {return priority < p.priority;}
};

int main()
{
      typedef Prioritised<int,int> PrioritisedInt;

      std::priority_queue<PrioritisedInt> queue;

      queue.push(PrioritisedInt(1,100));
      queue.push(PrioritisedInt(2,50));
      queue.push(PrioritisedInt(3,20));
      queue.push(PrioritisedInt(4,150));

      while (!queue.empty()) {
            std::cout << queue.top().t << '\n';
            queue.pop();
      }
}
--------8<--------
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 9787093
Come to think of it, the following template is a better design, because it doesn't use the member variable:
--------8<--------
#include <iostream>
#include <queue>
#include <string>

// General purpose class
template<class T,class P> class Prioritised : public T {
      P priority;
public:      Prioritised(const T& t,int priority = 0) : typename T(t),priority(priority) {}
      bool operator< (const Prioritised<T,P>& p) const {return priority < p.priority;}
};

int main()
{
      typedef Prioritised<std::string,int> PrioritisedString;

      std::priority_queue<PrioritisedString> queue;

      queue.push(PrioritisedString("Love",100));
      queue.push(PrioritisedString("Peace",50));
      queue.push(PrioritisedString("Wealth",20));
      queue.push(PrioritisedString("Happiness",150));

      while (!queue.empty()) {
            std::cout << queue.top() << '\n';
            queue.pop();
      }
}
--------8<--------
0
 
LVL 17

Accepted Solution

by:
rstaveley earned 250 total points
ID: 9787112
Oops...sorry spurious typename ... I tested this...

--------8<--------
#include <iostream>
#include <queue>
#include <string>

// General purpose class
template<class T,class P> class Prioritised : public T {
     P priority;
public:    
     Prioritised(const T& t,int priority = 0) : T(t),priority(priority) {}
     bool operator< (const Prioritised<T,P>& p) const {return priority < p.priority;}
};

int main()
{
     typedef Prioritised<std::string,int> PrioritisedString;

     std::priority_queue<PrioritisedString> queue;

     queue.push(PrioritisedString("Love",100));
     queue.push(PrioritisedString("Peace",50));
     queue.push(PrioritisedString("Wealth",20));
     queue.push(PrioritisedString("Happiness",150));

     while (!queue.empty()) {
          std::cout << queue.top() << '\n';
          queue.pop();
     }
}
--------8<--------
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

947 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now