Code C++. Not sure if what I did is right, if not please write n add comments to

Question

Code C++. Not sure if what I did is right, if not please write n add comments to code.

It says: If a priority queue is implemented as a binary search tree instead of a heap, the member functions defined in PQType would not change, but the private data members defined in PQType would change. The only data member would be a pointer to a TreeNode<ItemType.>.

TreeNode<ItemType> *items;

Complete the dequeue operation, using this implementation.

template<class ItemType>

void PQType<ItemType>::Dequeue (ItemType& item

//Pre: Priority queue is not empty/

//Post: The rightmost node is returned.

{

//add your code here(please add comments if possible)

}

queue is as a binary tree instead a member functions defined in would not but the private data members defined in would change. The only data member would be a pointer to a TreeNodecltemType ItemType items Complete the dequeue operation, using this implementation. template

Explanation / Answer

include <iostream>
using namespace std;

class priorityQueue
{
private:
int front;
int rear;
int size;
int *array;

public:
priorityQueue();
~priorityQueue();
void insert(int x);
//remove and return the smallest item currently in the priority queue
int extractMin();
bool empty();
};

priorityQueue::priorityQueue()
{
front = rear = -1;
size = 10;
array = new int[size];
}

priorityQueue::~priorityQueue()
{
delete[] array;
}

void priorityQueue::insert(int x)
{

if ( (rear + 1)% size == front ){
return;
}

//else if queue is empty
else if ( empty() ){
rear = front = 0;
}

else
{
rear = (rear + 1) % size;
}

array[rear] = x;
}

int priorityQueue::extractMin()
{
int minValue = array[front];

if ( empty() ){
return -1;
}

else if (front == rear){
front = rear = -1;
}

else
{
front = (front + 1) % size;
}

  
for (int i = front; i <= rear; i++){
if (array[i] < minValue)
minValue = array[i];
}
return array[front];
}

bool priorityQueue::empty()
{
if ( (front == -1) && (rear == -1) )
return true;
else
return false;
}

int main()
{
priorityQueue myqueue;

myqueue.insert(4);
myqueue.insert(3);
myqueue.insert(2);
myqueue.insert(1);

cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;

myqueue.insert(8);
myqueue.insert(7);
myqueue.insert(6);
myqueue.insert(5);

cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;

system("pause");
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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