Login | Register   
RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Minding the Queue: Java 1.5 Adds a New Data Structure Interface  : Page 2

The release of Java 1.5 finally provides built-in support for one of the most fundamental data structures in programming—the queue. This article explores the new Queue interface that's been added to the java.util package, demonstrating how to use this new support to streamline your data handling.

The AbstractQueue Class
As you've seen, the java.util.LinkedList class implements the java.util.Queue interface and, in a way, so does the AbstractQueue class. The AbstractQueue class implements some of the methods of the java.util interface (therefore the abstract in its name). However, the AbstractQueue places the onus on you to implement the offer, poll, and peek methods. Another way is to use some of the provided concrete implementations.

The PriorityQueue Class
In the PriorityQueue, queue implementation items are automatically ordered as you add them to the Queue. Depending on which PriorityQueue constructor you use, the order of your queue elements is either based on their natural order or is established via a Comparator that gets passed to the PrirorityQueue's constructor. The code below (excerpted from PriorityQueueUsageExample.java) demonstrates the usage of the PriorityQueue class. At the head of the queue is the String "Alabama"—since elements in the PriorityQueue are ordered naturally (in this case, in alphabetical order).

PriorityQueue<String> priorityQueue = new PriorityQueue<String>(); priorityQueue.offer("Texas"); priorityQueue.offer("Alabama"); priorityQueue.offer("California"); priorityQueue.offer("Rhode Island"); int queueSize = priorityQueue.size(); for (int i =0; i< queueSize; i++) { System.out.println(priorityQueue.poll()); }

Execution of the above code yields the following:

Alabama California Rhode Island Texas

The queue items are ordered according to their natural ordering—alphabetically.

As mentioned, you can create your own Comparator class and provide it to the Priority queue. Doing so allows you to define your own ordering. Check this out in the PriorityQueueComparatorUsageExample class, which uses a helper class named State. As you can see in the class definition below, a "State" simply contains a name and a population:

private String name; private int population; public State(String name, int population) { super(); this.name = name; this.population = population; } public String getName() { return this.name; } public int getPopulation() { return this.population; } public String toString() { return getName() + " - " + getPopulation(); }

In PriorityQueueComparatorUsageExample, the queue is defined using a custom implementation of java.util.Comparator (see below).

PriorityQueue<State> priorityQueue = new PriorityQueue(6, new Comparator<State>() { public int compare(State a, State b) { System.out.println("Comparing Populations"); int populationA = a.getPopulation(); int populationB = b.getPopulation(); if (populationB>populationA) return 1; else if (populationB<populationA) return -1; else return 0; } } );

After executing the PriorityQueueComparatorUsageExample class, the State objects you add to the queue should be placed in the PriorityQueue based on their population (from lowest to highest).

Comment and Contribute






(Maximum characters: 1200). You have 1200 characters left.



Thanks for your registration, follow us on our social networks to keep up-to-date