Java 1.5 Tiger A Developers Notebook [Electronic resources] نسخه متنی

1.3 Ordering Queues Using Comparators

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.

1.3.1 How do I do that?

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.

Example 1-3. Using a PriorityQueue

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