JAVA Your task is to create a priority queue class called PriQueue that is deriv

Question

JAVA

Your task is to create a priority queue class called PriQueue that is derived from the ArrayList class. Your class should be constructed as a Generic class so that the type of data the queue operates on can easily be changed:

PriQueue iQueue = new PriQue(); // holds Integers

PriQueue dQueue new PriQue(); // holds Doubles.

Your priority queue should be sorted by priority based on a value from 1 to 10. If a number is assigned that is outside the range of 1 to 10 you should give the element a value of 5. What this means is that each time an element is added to the queue it should be put in order by priority. If multiple elements are given the same priority their position relative to each other is unimportant as long as they are prioritized relative to other elements in the queue.

Your PriQueue should have the following functionality:

enqueue - Add an element to the queue

dequeue - Remove element from the front of the queue

peek - Return value at front of queue do not remove it

size - Returns the number of items in the queue.

Specifics

You should create a class called QElem that will hold both the priority of the element and the data to be put in the queue. The class should also be of a Generic type so that the value it holds can be of any type. The priority variable type should be an int.

The PriQueue class should be derived from ArrayList and should also be a Generic class so that it can operate on any type. The enque method should be adding a QElem so that the data and the priority are coupled. This needs to be done so that the data and priority are related for sorting. Here is an example:

PriQueue que = new PriQueue();

que.enqueue("Hello", 3);
que.enqueue("Goodbye", 9); // You are passing a string and an int but you should store a QElem class.

String s = que.dequeue();

The String s at this point should hold "Goodbye" even though it was put in last because it has a higher priority.

Sorting your queue. You are to create your own sort functionality. Pick any sort that you would like but the bubble sort might be the easiest to implement. If you cannot find an example of a bubble sort, I will provide a link for you.

NOTE:

Your PriQueue class should be derived from the ArrayList class that is part of java.util.ArrayList

Explanation / Answer

/*A simple priority Queue class. Using a vector to store keys ensures that data structure can grow dynamically. Also see we have vector of int. In a real world example we will have vector of some real items like process information for doing scheduling based on priority.*/ class PriorityQueue { vector pq_keys; void shiftRight(int low, int high); void shiftLeft(int low, int high); void buildHeap(); public: PriorityQueue(){} PriorityQueue(vector& items) { pq_keys = items; buildHeap(); } /*Insert a new item into the priority queue*/ void enqueue(int item); /*Get the maximum element from the priority queue*/ int dequeue(); /*Just for testing*/ void print(); }; void PriorityQueue::enqueue(int item) { pq_keys.push_back(item); shiftLeft(0, pq_keys.size() - 1); return; } int PriorityQueue::dequeue() { assert(pq_keys.size() != 0); int last = pq_keys.size() - 1; int tmp = pq_keys[0]; pq_keys[0] = pq_keys[last]; pq_keys[last] = tmp; pq_keys.pop_back(); shiftRight(0, last-1); return tmp; } void PriorityQueue::print() { int size = pq_keys.size(); for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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