Priority Queue Help

Here is my priority queue.. I can't seem to get my enqueue and dequeue to work quite right. The enqueue will work to a certain extent but still isn't that great. Any suggestions?

Code:

---


#include<iostream>
using namespace std;

const int MAX = 10;
const int DUMMY_PRIORITY = 1000;
class qNode {
public:
  int num;      // queue element
  int priority; // queue priority
  qNode();
  ~qNode();
};

qNode::qNode() {
  num = 0;
  priority = DUMMY_PRIORITY;
}

qNode::~qNode() {
}

class queue {
private:
  qNode q[MAX]; // queue node
  int size;    // queue size
public:
  queue();
  ~queue();
  bool isEmpty();
  bool isFull();
  void enqueue(int,int);
  int dequeue();
  void show();
};

queue::queue() {
  size  = 0;
}

queue::~queue() {
}

bool queue::isEmpty() {
  bool empty = false;
  if(size == 0) {
    empty = true;
  }

  return empty;
}

bool queue::isFull() {
  bool full = false;
  if(size == MAX) {
    full = true;
  }

  return full;
}

void queue::enqueue(int number, int priority) {
  bool placedElement = false; // determine whether or not the element was placed
  qNode tempNode1;
  qNode tempNode2;
  int temp = 0;
 
  /* if the queue is empty, just add the number to the front of the queue */
  if (isEmpty()) {
    q[temp].num = number;
    q[temp].priority = priority;
    size++;
    placedElement = true;
  }
  else {
    while (!placedElement) {
      if(q[temp].priority > priority) {
        if(q[temp].priority != DUMMY_PRIORITY) {
          tempNode1 = q[temp];
          q[temp].num = number;
          q[temp].priority = priority;
          size++;
          for(int i = temp + 1 ; i <= size ; i++) { // move the elements up
            tempNode2 = q[i];
            q[i] = tempNode1;
            tempNode1 = tempNode2;
          }
        }
        else {
          q[temp].num = number;
          q[temp].priority = priority;
          size++;
        }
        placedElement = true;
      }
      else {
        temp++;
      }
    }
  }
}

int queue::dequeue() {
  int element = q[0].num;
  qNode tempNode1;
  qNode tempNode2;
 
  if(!isEmpty()) {
    size--;
    tempNode1 = q[size-1];
    for(int i=size-1; i > 0; i--) {
      tempNode2 = q[i-1];
      q[i-1] = tempNode1;
      tempNode1 = tempNode2;
    }
  }

  return element;
}
   

void queue::show() {
  for(int i=0; i<MAX; i++) {
    cout << "Element -> " << q[i].num << "\t" << "Priority -> " << q[i].priority << endl;
  }
}

int main() {
  int num;
  int priority;
 
  queue myQueue;
  for(int i=0; i<MAX; i++) {
    cout << "enter a number -> ";
    cin  >> num;
    cout << "enter a priority -> ";
    cin >> priority;
    myQueue.enqueue(num,priority);
    cout << endl << endl;
    myQueue.show();
    cout << endl << endl;
  }

  // dequeue 3 elements
  cout << "dequeuing " << myQueue.dequeue() << endl << endl;
  cout << "dequeuing " << myQueue.dequeue() << endl << endl;
  cout << "dequeuing " << myQueue.dequeue() << endl << endl;

  // myQueue.show();
  return 0;
}

---

What would you like to improve about it?

Other suggestions:
isEmpty could be implemented much more nicely:

Code:

---

bool queue::isEmpty() {
  return size == 0; //or !size
}

---

Same thing about isFull.

A larger change might be to store the nodes in reverse, those with highest priority coming last. This should make dequeuing trivial (decrement size).

To insert, start to loop backwards from size-1 while the current element has higher priority, moving it up one position in the array, until you find the right place to insert the current node.

When you print out the queue, may-be you shouldn't print the unused nodes (you shouldn't care what their value is).

That's a very poor priority queue I'm afraid. It's O(n) insertion and removal.
You should be using a heap which is O(log n) insertion and removal.
As such I'm not going to offer any suggestions on little fixes to that code. You need to start again using a heap.

I assume this is just a school assignment and the OP is just learning about classes. Therefore the efficiency of the container type should not be a concern.

Writing a container seems to be a good way to learn about classes because there are so many ways it can be implemented. If the implementation is well hidden from the user of the class, you can change it any way you like without having to change the code that uses this class.

Speaking of which I would make MAX a private static constant inside queue, not a global, and change this loop

Code:

---

for(int i=0; i<MAX; i++)

---

into

Code:

---

while (!myQueue.isFull())

---

The reason is that the size of the underlying container is an implementation detail that the rest of the code shouldn't know about. If you indeed decided to use a heap or something different that would give you the possibility to store unlimited number of nodes, MAX would become meaningless but code outside the queue is still expecting it to mean something. (Of course, isFull would become rather meaningless too :(.)

I'm unphased as to whether it is an assignment or not.
But if it is, and I suspect that is, considering it is all in one file, then they have been asked to implement a priority queue, and in that case you can be damn sure it was intended to be implemented using a heap, so this submission would be wrong.
"Priority queue" is pretty much synonymous with "Heap".

Wikipedia doesn't seem to agree. A heap is a good way to implement it, but what makes something into a priority queue is what it allows you to do: to insert things and retrieve things in the order of priority. It also mentions that if it is implemented using an ordered array as OP is doing, then the relevant sort routine (for inserting thing) is insertion sort.

Considering that with an ordered array you should be able to get O(n) insertion, O(1) top and O(1) pop, a queue of only 10 elements might even be more efficient this way. (If the size limitation is dropped, the class design should allow to change to more efficient representation without any significant changes to user code.)

If OP is still wondering how to improve things, then you should drop the arbitrary DUMMY_PRIORITY. Because you should be able to know how many nodes the queue actually contains, you just shouldn't ever look at the unused ones - which therefore might just as well contain garbage.

----------

It took me long to reply because this heap thing is new to me too and I spent quite some time implementing a priority queue and reinventing std:: push_heap and std:: pop_heap. So at least I learnt something new :)

Wikipedia doesn't disagree with me. A heap is the most general and most efficient, and hence most common method of implementing a Priority queue. In fact it's hard to find anyone that doesn't automatically assume you mean a heap when you say priority queue.

Where it says "for integer data faster implementations exist", I am familiar with a van Emde Boas tree. It's very very complicated, uses a ton of memory, and is only faster if you have a massive number of items. I've been hunting for an implementation of a van Emde Boas tree before after barely managing to understand them, and found none. Don't be mislead, in the real world people use a heap.

I'm surprised there are even programmers out there that don't know all about heaps already. It's one of the fundamental data structures that I thought everyone gets taught, and it's hard to remember ever not knowing it. As a matter of fact, my Avatar is a picture of heapsort in action! (I made an animated gif of it, but they wont let us pleb users use gifs)
Now if you didn't know what a "Beap" was you could be forgiven...

Oh and yes I too would simply use an ordered array for a priority queue that was a always maximum of about 8 items.