Suppose that you want to implement the priority_queue (the priority is stored in

Question

Suppose that you want to implement the priority_queue (the priority is stored in the node data field) so that insertions occur in constant time, but getting the front item requires linear time. You will use these class definitions:

class priority_queue

{ void push(const Item& entry);

value_type top( );

...

private: node *head_ptr;

}

(A)Write ONE sentence to describe how the push member function will work (with constant time). (10 points)

(B) Then implement the top function (which will have linear worst-case time). In your implementation, you DO NOT have to worry about items with equal priority (they may come out of the priority_queue however you like, without necessarily having FIFO behavior). You may also assume that the following two toolkit functions have been modified to work with the priority_queue's node: (10 points))

void list_head_remove(Node*& head_ptr); // Removes head node of a list

void list_remove(Node* precursor); // Removes node after *precursor

Explanation / Answer

In single line node newnode =new node(); newnode.item = some value

IMPLEMENT PRIORITY - QUEUE

CODE ;

void list_head_remove(Node*& head_ptr){

head_ptr.prev = null; //It will make next node as header node

remove(head_ptr); //it will remove node

}

void list_remove(Node* precursor){

precursor.prev.next = precursor.next; // here setting previous node next link as immediate next link node

remove(precursor); // removing Node

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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