\"Specifically, the lab is to problem 2 on page 582 of the text. Note that you w

Question

"Specifically, the lab is to problem 2 on page 582 of the text. Note that you will need to implement a heap class (use a vector instead of a dynamic array) and then use the heap class to implement a priority queue. You need to construct a test program to help test the correctness of your code. You need to use heap.h and priority_queue.h."

THIS IS THE BOOK PROBLEM THE LAB ASSIGNMENT IS REFERRING TO

Problem 2 pg 582:

Using a heap , implement the priority queue class. The class should have a static constant member variable, CAPACITY, which is the maximum size of the heap and an array, data, that contains the heap with the entries. We also want to have FIFO behavior for entries with equal priority. To obtain this behavior, the class should have an extra private member variable that is an array, order, where order[i] contains the order in which dara[i] was added to the queue. For example, if entry[7] was the 33rd item added to the priority queue, then order [7] would be 33. When you are comparing two entries with equal priority, use the order number to "break the tie" (so that if two entries have the same priority number, then the one with the earlier order number willl come out of the priority queue first).

(This probem ^ with no predefined limit on the size of the heap, use a dynamic array).

THE LAB STATES:

IMPLEMENT THE A HEAP CLASS (USING A VECTOR INSTEAD OF A DYNAMIC ARRAY) THEN USE THE HEAP CLASS TO IMPLEMENT THE PRIORITY_QUEUE. THEN WRITE A TEST PROGRAM TO TEST THOSE IMPLEMENTATIONS.

included code:

Explanation / Answer

// Program that implements queue as a linked list
# include <iostream.h>
# include <conio.h>
class queue
{
   private :

       struct node
       {
           int data ;
           node *link ;
       } *front, *rear ;

   public :

       queue( ) ;
       void addq ( int item ) ;
       int delq( ) ;
       ~queue( ) ;
} ;

// initialises data member
queue :: queue( )
{
   front = rear = NULL ;
}

// adds an element to the queue
void queue :: addq ( int item )
{
   node *temp ;

   temp = new node ;
   if ( temp == NULL )
       cout << " Queue is full" ;

   temp -> data = item ;
   temp -> link = NULL ;

   if ( front == NULL )
   {
       rear = front = temp ;
       return ;
   }

   rear -> link = temp ;
   rear = rear -> link ;
}

// removes an element from the queue
int queue :: delq( )
{
   if ( front == NULL )
   {
       cout << " Queue is empty" ;
       return NULL ;
   }

   node *temp ;
   int item ;

   item = front -> data ;
   temp = front ;
   front = front -> link ;
   delete temp ;
   return item ;
}

// deallocates memory
queue :: ~queue( )
{
   if ( front == NULL )
       return ;
   node *temp ;
   while ( front != NULL )
   {
       temp = front ;
       front = front -> link ;
       delete temp ;
   }
}

void main( )
{
   queue a ;
   clrscr();
   a.addq ( 34 ) ;
   a.addq ( 46 ) ;
   a.addq ( 23 ) ;
   a.addq ( 29 ) ;
   a.addq ( 15 ) ;
   a.addq ( 33 ) ;
   a.addq ( 28 ) ;

   int i = a.delq( ) ;
   cout << " Item extracted: " << i ;

   i = a.delq( ) ;
   cout << " Item extracted: " << i ;

   i = a.delq( ) ;
   cout << " Item extracted: " << i ;
   getch();
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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