Question

JAVA PROGRAMMING

You are given an interface PriorityQueue (the source code is at the end of this document) that specifies the protocols for a priority queue with generic values and priorities, where the priorities are discretely ordered rather than comparable. Implement the class ArrayListPQ implements PriorityQueue to fulfill the requirements of the interface (see the Javadoc in the interface’s source code). Use an ArrayList in order to fulfill the needs of the interface. For each constructor and method in your implementation, implement it in constant time if possible or else in no worse than linear time, and include a detailed comment analyzing the runtime in ?(… ) notation (order of magnitude or “big-Oh” notation). You are not expected to implement a main method. The class you implement is just an abstract data type, which you test as necessary using techniques discussed in lecture and lab. Do not change the PriorityQueue interface, because the instructors use the interface as given. Your implemented class is expected to comply with the given interface without any protocol conflicts.

Interface:

public interface PriorityQueue<V, P> {

/**

* Clears or initializes all encapsulated data structures

* which store any discrete priorities or enqueued values.

*

* Each constructor must call this method exactly once.

*/

void clear();

/**

* Appends a new lowest priority to the end of the sequence

* of discrete priorities (ordered from highest to lowest).

*

* This method must be called at least once after clearing

* the priority queue but before enqueueing any values.

*

* @param priority The priority to append

*/

void prioritize(P priority);

/**

* Adds a new value with the given priority

* after all other values with the same or higher priority

* and before all values with a lower priority.

*

* @param value The value to add

* @param priority The priority for that value

*/

void enqueue(V value, P priority);

/**

* Removes the oldest value of the

* highest priority available.

*

* @return The value to remove

*/

V dequeue();

/**

* Accesses the oldest value of the

* highest priority available.

*

* @return The value to access

*/

V peek();

/**

* Determines whether the priority queue has no values.

*

* @return Whether the priority queue is empty

*/

boolean isEmpty();

/**

* Represents the values in the priority queue

* in descending order of priority with a notation

* that includes both values and their priorities.

*

* @return The string representation

*/

String toString();

}

Answer 1

Program

filename:ArrayListPQ.java

import java.util.ArrayList;
import java.util.PriorityQueue;

public class ArrayListPQ {

private ArrayList<Object> lst; // arraylist to hold the elements

/**
* default constructor to create a new PriorityQueue
*/
public ArrayListPQ() {
lst = new ArrayList<Object>();
}

/**
* method to enqueue a new element to the PriorityQueue
*
* @param e
*/
public void enqueue(Object e) {
lst.add(lst.size(), e);
}

/**
* method to dequeue an existing element from the PriorityQueue
*
* @return the removed element
*/
public Object dequeue() {
int maxIndex = maxIndex();
Object maxObj = lst.get(maxIndex);
lst.remove(maxIndex);
return maxObj;
}

/**
* method to view the element at the top of the PriorityQueue
*
* @return the element at the top
*/
public Object peek() {
return lst.get(maxIndex());
}

/**
* method to return the maximum index
*
* @return the maximum index
*/
private int maxIndex() {
int max = 0;
for (int i = 0; i < lst.size(); i++) {
Comparable<Object> d = (Comparable<Object>) lst.get(i);
Object maxObj = lst.get(max);
if (d.compareTo(maxObj) > 0) {
max = i;
}
}

return max;

}

/**
* main driver method
*
* @param args
*/
public static void main(String[] args) {

PriorityQueue<String> Way = new PriorityQueue<String>();
Way.add("Alpha");
Way.add("Bravo");
Way.add("Charlie");

int count = 1;

while (!Way.isEmpty()) {
System.out.println("PQ " + count + "-->" + Way.remove());
count++;
System.out.println();
}

}
}

import java.util.ArrayList; import java.util.PriorityQueue; public class ArrayListPQ { private ArrayList<object> Ist; // arraylist to hold the elements 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 * default constructor to create a new PriorityQueue public ArrayListPQ() { 1st = new ArrayList<object>(); } 16 * method to enqueue a new element to the PriorityQueue @param e public void enqueue(Object e) { 1st.add(1st.size(), e); بها /** method to dequeue an existing element from the PriorityQueue @return the removed element 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 public Object dequeue() { int maxIndex = maxIndex(); Object maxobj = lst.get(maxIndex); 1st.remove(maxIndex); return maxobj; } method to view the element at the top of the PriorityQueue @return the element at the top public Object peek() { return 1st.get(maxIndex()); } method to return the maximum index 48 @return the maximum index 49 50 51 52 53 54 55 private int maxIndex() { int max = 0; for (int i = 0; i < lst.size(); i++) { Comparable<object> d = (Comparable<object>) lst.get(i); Object maxobj = lst.get(max); if (d.compareTo(maxobj) > 0) {

max i; 56 57 58 } } return max; } main driver method @param args public static void main(String[] args) { = new PriorityQueue<String>(); 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 PriorityQueue<String> Way Way.add("Alpha"); Way.add("Bravo"); Way.add("Charlie"); int count 1; + count + while (!Way.isEmpty()) { System.out.println("PQ count++; System.out.println(); + Way.remove()); بها }

Output

PQ 1-->Alpha PQ 2-->Bravo PQ 3-->Charlie

==========================================================================================

Hope this helps!

Thank you!

I hope you're safe during the pandemic.