Question

Write a C++ program that will implement a Priority Queue class using the List Class provided below. Test your class with the input file QueueInput.txt. You will have to edit the file and eliminate the text at the top of the file. You will not alter the commands

Answer 1

Complete Program:

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

class Entry
{
public:
   int value;
   int priority;

   Entry()
   {
       value = 0;
       priority = 0;
   }

   Entry(int aValue, int aPriority)
   {
       value = aValue;
       priority = aPriority;
   }
};

class List
{
private:
   int CAPACITY;
   Entry *arr;
   int currentPos, size1;

public:
   List()
   {
       CAPACITY = 20;
       arr = (Entry *)malloc(CAPACITY * sizeof(Entry *));
       size1 = 0;
       currentPos = -1;
   }

   List(const List &obj)
   {
       CAPACITY = obj.CAPACITY;
       size1 = obj.size1;
       currentPos = obj.currentPos;
       if(arr != NULL)
       {
           for(int i = 0; i < size1; i++)
               arr[i] = obj.arr[i];
       }
   }

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

   void front()
   {
       if(size1 == 0)
           cout << "List is empty!" << endl;
       else
           currentPos = 0;
   }

   void end()
   {
       if(size1 == 0)
           cout << "List is empty!" << endl;
       else
           currentPos = size1 - 1;
   }

   void prev()
   {
       if(size1 <= 0)
           cout << "Previous element is empty.\n";
       else
       {
           currentPos--;
       }
   }

   void next()
   {
       if(currentPos >= CAPACITY - 1)
           cout << "Next element is empty.\n";
       else
       {
           currentPos++;
       }
   }

   int getPos()
   {
       return currentPos;
   }

   void setPos(int n)
   {
       if(n < 0 || n >= size1)
           cout << "Position should not be out of range." << endl;
       else
           currentPos = n;
   }

   void insertBefore(Entry ele)
   {
       if(size1 == CAPACITY)
       {
           cout << "The list has reached max capacity. Cannot add more elements.\n";
           return;
       }
       else if(currentPos - 1 < 0)
       {
           cout << "No previous position.\n";
           return;
       }
       else
       {
           currentPos--;
           arr[currentPos] = ele;
           size1++;
       }
   }

   void insertAfter(Entry ele)
   {
       if(size1 == CAPACITY)
       {
           cout << "The list is full. Elements have NOT been added.\n";
           return;
       }
       else if(currentPos + 1 >= CAPACITY)
       {
           cout << "No next position.\n";
           return;
       }
       else
       {
           currentPos++;
           arr[currentPos] = ele;
           size1++;
       }
   }

   Entry getElement()
   {
       return arr[currentPos];
   }

   int size()
   {
       return size1;
   }

   void replace(Entry n)
   {
       if(currentPos < 0)
           cout << "List is empty!" << endl;
       else
           arr[currentPos] = n;
   }

   void erase()
   {
       if(currentPos < 0)
           cout << "List is empty!" << endl;
       else
       {
           for(int i = currentPos; i < size1 - 1; i++)
           {
               arr[i] = arr[i + 1];
           }
           size1--;
       }
   }

   void clear()
   {
       currentPos = -1;
       size1 = 0;
       arr = new Entry[CAPACITY];
   }

   void reverse()
   {
       for(int i = 0; i < size1 / 2; i++)
       {
           Entry tmp = arr[i];
           arr[i] = arr[size1 - i];
           arr[size1 - i] = tmp;
       }
   }

   void swap(List a)
   {
       Entry *tmp = arr;
       arr = a.arr;
       a.arr = tmp;
   }

   friend ostream &operator<<(ostream &out, List &l)
   {              
       for(int i = 0; i < l.size(); i++)
       {          
           if(l.arr[i].value != 0)
               out << l.arr[i].value << " - " << l.arr[i].priority << endl;
       }
       out << "\n";
       return out;
   }

   bool operator ==(List &l)
   {
       if(size1 != l.size1)
           return false;
  

       for(int i = 0; i < size1; i++)
       {
           if(arr[i].priority != l.arr[i].priority || arr[i].value != l.arr[i].value)
               return false;
       }

       return true;
   }

   void operator=(List &l)
   {
       if(this != &l)
       {
           delete [] arr;
           CAPACITY = l.CAPACITY;
           size1 = l.size1;
           arr = new Entry[CAPACITY];
           currentPos = l.currentPos;

           if(arr != NULL)
           {
               for(int i = 0; i < size1; i++)
                   arr[i] = l.arr[i];
           }      
       }
   }
};

class PriorityQueue
{
private:
   List list;

public:
   PriorityQueue()
   {}

   void enqueue(Entry ent)
   {
       list.insertAfter(ent);
   }

   Entry dequeue()
   {
       list.front();

       Entry ent = list.getElement();
       int index = 0;

       for(int i = 1; i < list.size(); i++)
       {
           list.next();

           if(list.getElement().priority > ent.priority)
           {
               ent = list.getElement();
               index = i;
           }
       }

       list.setPos(index);
       list.erase();

       return ent;
   }

   bool empty()
   {
       return list.empty();
   }
};

int main()
{
   ifstream infile;
   infile.open("QueueInput.txt");
   if(!infile)
   {
       cout << "Input file is not found!" << endl;
       exit(1);
   }

   PriorityQueue pq;
   string str;
   int value;
   int priority;

   infile >> str;
   while(infile)
   {
       if(str == "Enqueue")
       {
           infile >> value;
           infile >> priority;

           Entry ent(value, priority);

           pq.enqueue(ent);
       }
       else
       {
           Entry ent = pq.dequeue();
           cout << "Dequeue: " << ent.value << " - " << ent.priority << endl;
       }

       infile >> str;
   }
   infile.close();
  

   cout << endl;
   system("pause");
   return 0;
}

-----------------------------------------------------------------

Sample Output: