While FIFO is a useful paradigm, there are times when you'll want a queue-like structure, ordered by another metric. This is exactly the purpose of PriorityQueue, another Queue implementation. You provide it a Comparator, and it does the rest.
PriorityQueue works just as any other Queue implementation, and you don't even need to learn any new methods. Instead of performing FIFO ordering, though, a PriorityQueue orders its items by using the Comparator interface. If you create a new queue and don't specify a Comparator, you get what's called natural ordering, which applies to any classes that implement Comparable. For numerical values, for instance, this places highest values, well, highest! Here's an example:
PriorityQueue<Integer> pq =
new PriorityQueue<Integer>(20);
// Fill up with data, in an odd order
for (int i=0; i<20; i++) {
pq.offer(20-i);
}
// Print out and check ordering
for (int i=0; i<20; i++) {
System.out.println(pq.poll( ));
}
Since no Comparator implementation is given to PriorityQueue, it orders the numbers lowest to highest, even though they're not added to the queue in that order. So when peeling off elements, the lowest item comes out first:
[echo] Running PriorityQueueTester... [java] 1 [java] 2 [java] 3 [java] 4 [java] 5 [java] 6 [java] 7 [java] 8 [java] 9 [java] 10 [java] 11 [java] 12 [java] 13 [java] 14 [java] 15 [java] 16 [java] 17 [java] 18 [java] 19 [java] 20
However, this queue starts to really come into its own when you provide your own comparator, as shown in Example 1-3. This is done via the constructor, and a custom implementation of java.util.Comparator.
package com.oreilly.tiger.ch01;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueTester {
public static void main(String[] args) {
PriorityQueue<Integer> pq =
new PriorityQueue<Integer>(20,
new Comparator<Integer>( ) {
public int compare(Integer i, Integer j) {
int result = i%2 - j%2;
if (result == 0)
result = i-j;
return result;
}
}
);
// Fill up with data, in an odd order
for (int i=0; i<20; i++) {
pq.offer(20-i);
}
// Print out and check ordering
for (int i=0; i<20; i++) {
System.out.println(pq.poll( ));
}
}
}
The output from this is lowest to highest even numbers, and then lowest to highest odd numbers:
[echo] Running PriorityQueueTester... [java] 2 [java] 4 [java] 6 [java] 8 [java] 10 [java] 12 [java] 14 [java] 16 [java] 18 [java] 20 [java] 1 [java] 3 [java] 5 [java] 7 [java] 9 [java] 11 [java] 13 [java] 15 [java] 17 [java] 19