Creating a Generic Priority Queue Using the MyLinkedList class that we developed

Question

Creating a Generic Priority Queue

Using the MyLinkedList class that we developed in assignment #6 as a starting point, you may modify the class code OR extend the class to create a generic priority queue.  

For this exercise, a priority queue is defined as a queue of nodes that contain both generic data AND and an integer value representing priority. Within the LinkedList used to form the queue, nodes are inserted in sorted order BY PRIORITY. The enqueue method should insert every new node BEHIND every other node of lower priority, but IN FRONT of evey other node in the list that has the same or higher priority. This retains the first-in-first-out property for any given priority level.

Your solution should create a new PriorityQueue for String data with:
   PriorityQueue<String> pq = new PriorityQueue<String();

If I wanted to enqueue the String

Explanation / Answer

#include <iostream>
#include <algorithm>
using namespace std;

const int Max = 100;

//
template<typename T>
class priorityQueue
{
private:
   T data[Max];
   int length; //?1length

   void swap( int i, int j)
   {
       T temp;
       temp = data[i];
       data[i] = data[j];
       data[j] = temp;;
   }

   void siftUp(int last) //
   {
       for(int i=last; i>1 && data[i] < data[i/2]; i /= 2)
       {
           swap(i, i/2);
       }
   }

   void siftDown(int first) //?
   {
       for(int i=first * 2; i <=length; i *= 2)
       {
           //i
           if(i+1 <= length && data[i+1] < data[i])   i++;
  
           //
           if(data[i/2] <= data[i])
               break;
           else
               swap(i/2, i);
       }
   }

public:

   priorityQueue()
   {
       length = 0;
   }

   T front()
   {
       return data[1];
   }

   void push(T key)
   {
       data[++length] = key;
       siftUp(length);
   }

   void pop()
   {
       swap(1, length);
       length --;
       siftDown(1);
   }

   int size()
   {
       return length;
   }

   bool empty()
   {
       return length == 0;
   }
};

int main()
{
   priorityQueue<float> q;
   float num;

   //
   while(cin >> num && num != 0)
   {
       q.push(num);
   }
   while(!q.empty())
   {
       cout << q.front() << ' ' ;
       q.pop();
   }
   system("pause");
   return 1;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.