ArrayQueue.h defnition, derive two versions of a priority queue. Note that there

Question

ArrayQueue.h defnition, derive two versions of a priority queue. Note that there are essentially two ways (using an array-based structure) to achieve the “remove smallest” operation. Te frst is to make sure the queue is always sorted, so that the smallest element is always at the front. Te second is to leave the queue in its “natural” arrival order and search for the smallest element every time removeMin() is called. Implement both of these—call the frst subclass PriorityQueueSort and the second PriorityQueueSearch. Assume that the element type, T, has the < operator defned. (Be sure your implementations do the sensible thing in the case where two elements have the “smallest” priority—which one should get removed frst?)

ArrayQueue.h

Explanation / Answer

namespace ods { template class ArrayQueue { protected: array a; int j; int n; void resize(); public: ArrayQueue(); virtual ~ArrayQueue(); virtual bool add(T x); virtual T remove(); int size(); }; template ArrayQueue::ArrayQueue() : a(1) { n = 0; j = 0; } template ArrayQueue::~ArrayQueue() { // delete a; } template void ArrayQueue::resize() { array b(max(1, 2*n)); for (int k = 0; k a.length) resize(); a[(j+n) % a.length] = x; n++; return true; } template T ArrayQueue::remove() { T x = a[j]; j = (j + 1) % a.length; n--; if (a.length >= 3*n) resize(); return x; } template int ArrayQueue::size() { return n; }

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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