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

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.

ne of the fundamental data structures in computer science is the queue. You will recall that a queue is a data structure in which elements are removed in the same order in which they were added. This FIFO (first in, first out) data structure was unfortunately neglected in previous versions of Java. With the advent of Java 1.5 (a.k.a. Tiger), queue support is innate for the first time.

How We Managed In the Past Without Queues
Pre- Java 1.5, it was common practice to use a java.util.List collection to imitate a queue. The concept of a queue was emulated by objects being added (an operation commonly known as enqueuing) to the rear of the List (i.e., the rear of the queue) and removed (an operation commonly known as dequeuing) from the List by grabbing objects from the top of the List (i.e., the top of the queue). The code below shows what you might have done before.

import java.util.Enumeration; import java.util.LinkedList; import java.util.Vector; public class QueueEmulate { private LinkedList queueMembers; public Object enqueue(Object element) { queueMembers.add (element); return element; } public Object dequeue() { return queueMembers.removeFirst(); } }

Now We Have Queues
Java 1.5 adds a new Queue interface to the java.util package, which is used in the code just below (grabbed from SimpleQueueUsageExample.java of the project sample code). Notice that in Java 1.5 java.util.LinkedList has been retrofitted to implement the java.util.Queue interface as well as the java.util.List interface. Also notice how I can explicitly state that my queue will consist of only strings, using the <String> generic (for a deeper understanding of generics, please see"J2SE 1.5: Java's Evolution Continues"). This saves me from the headache of having to cast objects when I grab them from my queue.

Queue<String> myQueue = new LinkedList<String>(); myQueue.add("Add Me"); myQueue.add("Add Me Too"); String enqueued = myQueue.remove();

You can see the add and remove methods of the LinkedList class being used to perform the enqueuing and dequeuing operations respectively. These are actually not the preferred methods to use; the Queue interface gives you the new offer and poll methods, shown below (grabbed from SimpleQueueUsageExamplePreferred):

Queue<String> myQueue = new LinkedList<String>(); boolean offerSuccess; // offer method tries to enqueue. // A boolean is returned telling you if the // attempt to add to the queue was successful or not offerSuccess=myQueue.offer("Add Me"); offerSuccess=myQueue.offer("Add Me Too"); // peek at the head of the queue, but don't grab it Object pull = myQueue.peek(); String enqueued = null; // grab the head of the queue if (pull!=null) enqueued = myQueue.poll(); System.out.println(enqueued);

If your queue is restricted to a certain size (which is often the case), adding to it using the add method will result in an unchecked exception being thrown. When you compile the source of SimpleQueueUsageExample, the compiler will warn you about this. On the other hand, when the new offer method tries to enqueue, if things go well, it will return true. If not, it will return false. Similarly, if you try to use the remove method on an empty queue, this also results in an unchecked exception.

You can also use the poll method to pull elements from the queue. The poll method will return a null (i.e., not throw an exception) if there are no elements in the queue. In some cases, you might not want to extract the element at the head of the queue, but rather just take a peek at it. The Queue interface provides us with a peek method to do just that. If you're dealing with an empty queue, peek returns a null. As in the add-offer and remove-poll relationship, there is a peek-element relationship. In the case of an empty queue, the element method throws an unchecked exception. But if there are elements in the queue, the peek method allows you to take a gander at the first element without actually pulling it from the queue. Usage of the peek method is demonstrated in the SimpleQueueUsageExamplePreferred class.

Comment and Contribute








