Question
Implement a priority queue capable of holding objects of an arbitrary type, T, by defining a PriorityQueue class that implements the queue with an ArrayList . A priority queue is a type of list where every item added to the queue also has an associated priority. Define priority in your application so that those items with the largest numerical value have the highest priority. Your class should support the following methods:
• Add(item, priority) —Adds a new item to the queue with the associated priority.
• Remove() —Returns the item with the highest priority and removes it from the queue. If the user attempts to remove from an empty queue, return null .
For example, if q is a priority queue defined to take Strings
q.add("X", 10);
q.add("Y", 1);
q.add("Z", 3);
System.out.println(q.remove()); // Returns X
System.out.println(q.remove()); // Returns Z
System.out.println(q.remove()); // Returns Y
Test your queue on data with priorities in various orders (e.g., ascending, descending, mixed). You can implement the priority queue by performing a linear search through the ArrayList . In future courses, you may study a data structure called a heap that is a more efficient way to implement a priority queue.
Answer
Program code:
public class PriorityDemo
{
public static void main(String args[])
{
//Define PriorityQueue's class object is q
PriorityQueue q=new PriorityQueue();
//Input values
q.add("X", 10);
q.add("Y", 1);
q.add("Z", 3);
//Output
System.out.println(" " +q.remove()); // Returns X
System.out.println(" " +q.remove()); // Returns Z
System.out.println(" " +q.remove()); // Returns Y
}
}
import java.util.*;
public class PriorityQueue
{
private ArrayList queueArray;
private ArrayList priorityArray;
//Constructor
public PriorityQueue()
{
queueArray=new ArrayList();
priorityArray=new ArrayList();
}
//Adds the items in the queue list by using priority
public <T> void add(T itemAdd,int priorityAdd)
{
queueArray.add(itemAdd);
priorityArray.add(priorityAdd);
}
public boolean isEmpty()
{
return queueArray.size()==0;
}
public <T> T remove()
{
int max=0,maxPriority=0;
for(int i=0;i<queueArray.size();i++)
{
if(priorityArray.get(i) > maxPriority)
{
max=i;
maxPriority=priorityArray.get(i);
}
}
priorityArray.remove(max);
return (T) queueArray.remove(max);
}
}
Output:
Y
Z
X
Discussions
chase buttons
Tried it and it doesn't compile. "The operator > is undefined for argument type(s) obj , int.
line 31, line 33. Gonna try to fix it. Thanks for the submission!!! If you get it edited, would like to check back in. Cheers!
Post the discussion to improve the above solution.