Priority Queue Start with the definition of the Queue class and modify it to sto

Question

Priority Queue Start with the definition of the Queue class and modify it to store integers instead of characters. A special type of queue is a priority queue. A priority queue behaves like a regular queue except the remove function always extracts the item with the smallest value (this is the item with the highest priority). Create a Priority Queue class that is derived from the Queue class with appropriate constructors. Redefine the remove function in the PriorityQueue class to extract the item with the smallest value. Test the PriorityQueue class by adding several numbers to a PriorityQueue object then remove each one, printing the removed numbers as they are removed from the queue Sample output: Asn #3 by John Smith-Priority Queue Add five integers to queue: #1: 25 #2: 12 #3: 5 #4: 10 #5: -3 Remove the numbers -3 5 10 12 25 Again? (y/n):

Explanation / Answer

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

const int MAX_SIZE = 200;
//Queue using array
class Queue
{
public:
   int data[MAX_SIZE];
   int front;
   int rear;
public:
   Queue()
   {
       front = 0;
       rear = 0;
   }

   void Enqueue(int element)
   {
       // Don't allow the queue to grow more
       // than MAX_SIZE - 1
       if (Size() == MAX_SIZE - 1)
           cout << "Queue FULL";
       else
       {
           data[rear] = element;
           // MOD is used so that rear indicator
           // can wrap around
           rear = ++rear % MAX_SIZE;
          
       }

      
   }

   int Dequeue()
   {
       if (isEmpty())
       {
           cout << "Queue empty";
           return 0;
       }
       else
       {
           int ret = data[front];

           // MOD is used so that front indicator
           // can wrap around
           front = ++front % MAX_SIZE;

           return ret;
       }

      
   }

   int Front()
   {
       if (isEmpty())
           return 0;

       return data[front];
   }

   int Size()
   {
       return abs(rear - front);
   }

   bool isEmpty()
   {
       return (front == rear) ? true : false;
   }
   void print_queue()
   {
       if (isEmpty())
           cout << "queue empty";
       else
       {
           for (int i = front; i < rear; i++)
               cout << data[i] << endl;
       }
   }
};
class PriorityQueue :public Queue
{
public:
   PriorityQueue() :Queue()
   {

   }
   //function to remove elements from the queue
   int Dequeue()
   {
       int min = 0;
       if (isEmpty())
       {
           cout << "Queue empty";
           return 0;
       }
       else //find the minimum element in the queue and delete it
       {
           min = Front(); //assume first element to be minimum
           int index = front;
           for (int i = front+1; i < rear; i++)
           {
               if (min>data[i]) //if any other element is less then the minimum element change the values
               {
                   min = data[i];
                   index = i; //save the index value so that we can shift the array after finding minimum element
               }
           }
           //shifting the entire array after minimum element is found
           for (int i = index; i < rear-1; i++)
           {
               data[i] = data[i + 1];
           }
           rear = rear - 1; //now rear will decrease as one element is deleted
       }
       return min;

   }
};

int main()
{
   PriorityQueue q;
       if (q.isEmpty())
       {
           cout << "Queue is empty" << endl;
       }

       // Enqueue elements
       q.Enqueue(100);
       q.Enqueue(200);
       q.Enqueue(300);
       q.Enqueue(-3);
       q.Enqueue(-4);
       q.Enqueue(30);
       cout << "The queue contains:" << endl;
       q.print_queue();
      

       // Dequeue elements
       cout << "deleting element:" << q.Dequeue() << endl;
       cout << "deleting element:" << q.Dequeue() << endl;
       cout << "deleting element:" << q.Dequeue() << endl;
       cout << "after deleting 3 elements from queue:" << endl;
       q.print_queue();
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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