It is possible to provide a fast priority queue implementation if the inserted items have a bounded number of integer priorities.

Make an array list of linked lists. The linked list at index i holds all items with priority i. To add an element, simply add it to the end of the ith priority list. To remove an element, remove it from the front of the non-empty list with the lowest priority.


Complete the following class that implements this idea. (Note that the elements stored in this priority queue do not implement the Comparable interface. Instead, an integer priority must be specified together with each item as it is inserted.)

Complete the following file:

import java.util.ArrayList; import java.util.LinkedList; public class FastPQueue { public FastPQueue(int maxPriority) { itemLists = new ArrayList<LinkedList<Object>>(); for (int i = 0; i <= maxPriority; i++) itemLists.add(new LinkedList<Object>()); } public void add(int priority, Object item) { // TODO: Complete this method } public Object remove() { // TODO: Complete this method } private ArrayList<LinkedList<Object>> itemLists; // linked lists of items with the same priority // This method is used to check your work public static String[] check(String[] items) { FastPQueue pq = new FastPQueue(9); for (String item : items) pq.add(Integer.parseInt(item.substring(0, 1)), item.substring(1)); String[] r = new String[items.length]; for (int i = 0; i < r.length; i++) r[i] = pq.remove().toString(); return r; } }