Suppose that you want to implement the PriorityQueue so that insertions occur in

Question

Suppose that you want to implement the PriorityQueue so that insertions occur in constant time, but getFront requires linear time. You will use these class definitions, where the data entering the PriorityQueue is a String and the priorities are ints.

public class PriorityQueue
{
// A PriorityNode is a node from a linked list of strings, with
// methods for getString, setString, getPriority, setPriority,
// getLink, and setLink.
private PriorityNode head;

public void insert(String entry, int priority)...
public String getFront( )...
...
}

(A) Write ONE sentence to describe how the insert method will work (with constant time).
(B) Then implement the getFront method (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 prioirty queue however you like, without necessarily having FIFO behavior). To remove the head node of a linked list, use the assignment:

head = head.getLink( );

Explanation / Answer

package priorityq; 02 import java.util.*; 03 /** 04 * 05 * @author Ron 06 */ 07 public class Main { 08 09 /** 10 * @param args the command line arguments 11 */ 12 public static void main(String[] args) { 13 // TODO code application logic here 14 int f; 15 int size = 20; 16 PriorityQ thePQ = new PriorityQ(size+1); 17 int [] numbers = new int [size+1]; 18 //Random generator = new Random(); 19 int high = 1000; 20 int low = -1000; 21 int dequeue; 22 Scanner scan = new Scanner (System.in); 23 boolean choice = true; 24 25 for(f=0; f

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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