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 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 myQueue = new LinkedList();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 myQueue = new LinkedList();boolean offerSuccess;// offer method tries to enqueue.  // A boolean is returned telling you if the // attempt to add to the queue was successful or notofferSuccess=myQueue.offer("Add Me");offerSuccess=myQueue.offer("Add Me Too");// peek at the head of the queue, but don't grab itObject pull = myQueue.peek();String enqueued = null;// grab the head of the queueif (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.

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 priorityQueue = new PriorityQueue();priorityQueue.offer("Texas");priorityQueue.offer("Alabama");priorityQueue.offer("California");priorityQueue.offer("Rhode Island");int queueSize = priorityQueue.size();for (int i =0; i

Execution of the above code yields the following:

AlabamaCaliforniaRhode IslandTexas

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 priorityQueue =      new PriorityQueue(6, new Comparator(){     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

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).Blocking Queues
Queues are typically restricted to a given size. With the queue implementations you have seen so far, using the offer or add methods to enqueue (and the remove or poll methods to dequeue) assumes that if the queue cannot accommodate an enquing or dequeuing operation, then you don't need to wait to execute the program. The java.util.concurrent.BlockingQueue interface codifies this concept. It adds the methods put and take to the arsenal. An example might be useful.

Using the classis classic producer/consumer relationship, suppose your producer writes to a queue (more specifically a BlockingQueue). You have a number of consumers reading from that queue, which you want to happen in an orderly fashion. Basically, each consumer needs to wait for the previous consumer before it is allowed to grab an item from the queue. To architect this setup programmatically, spawn one producer thread that writes to a queue and then spawn a number of consumer threads which read from the same queue. Note here that the threads will block one another until the current thread is done grabbing an item from the queue.

The code below shows the class Producer writing to a BlockingQueue. Notice that objects in the run method (which you're obligated to implement, since you extended Thread) are put onto the BlockingQueue after waiting a random amount of time (ranging from 100 – 500 millseconds). The object put onto the queue is simply a String object consisting of the timestamp when the message was produced.

The actual work of enqueuing the object is done by the statement:

blockingQueue.put("Enqueued at: " + time)

The put method throws an InterruptedException. Accordingly, the put operation is surrounded by a try and a catch block, which catches the exception thrown (see Listing 1).

Leeching messages from the producer is the Consumer object, which again extends from the Thread object and is therefore obligated to implement the run method (see Listing 2).

The Consumer class is very similar in the design to the Producer class. Instead of putting messages on the BlockingQueue, the Consumer class uses the take method to pull (i.e., dequeue) messages off of the queue. As stated before, this happens by waiting until something is actually on the queue. If the Producer thread stopped putting (i.e.,queuing) objects onto the queue, then the Consumer threads would wait until a queue item became available. The class TestBlockingQueue, shown below, spawns four consumer threads which try and grab objects from the BlockingQueue:

import java.util.concurrent.BlockingQueue;import java.util.concurrent.LinkedBlockingQueue;public class TestBlockingQueue{  public static void main(String args[])  {    BlockingQueue blockingQueue = new LinkedBlockingQueue();    Producer producer = new Producer(blockingQueue, System.out);    Consumer consumerA = new Consumer("ConsumerA", blockingQueue, System.out);    Consumer consumerB = new Consumer("ConsumerB", blockingQueue, System.out);    Consumer consumerC = new Consumer("ConsumerC", blockingQueue, System.out);    Consumer consumerD = new Consumer("ConsumerD", blockingQueue, System.out);	    producer.start();    consumerA.start();    consumerB.start();    consumerC.start();    consumerD.start();    }}	

Figure 1. Consumer Threads: These threads dequeue messages from the BlockingQueue in the order that you spawned them.

The following line creates the Blocking Queue:

BlockingQueue blockingQueue = new LinkedBlockingQueue();

Notice it uses the LinkedBlockingQueue implementation of the BlockingQueue. You can't instantiate the BlockingQueue directly, since it is an abstract class. You could also have used the queue type ArrayBlockingQueue. ArrayBlockingQueue uses an array as its storage device, while the LinkedBlockingQueue uses a linked list. The capacity of an ArrayBlockingQueue is fixed. For a LinkedBlockingQueue, the maximum size can be specified; by default it is unbounded. The sample code[link] takes the unbounded approach.

During the execution of the class, the dequeuing of objects from the queue happens in sequential order (see example execution below). In essence, one consumer thread blocks the others from accessing the BlockingQueue, until it is able to dequeue an object off of the queue.

DelayQueue?I Am/Am Not Half-baked
In some cases, objects that you place on a queue should be on that queue for a certain amount of time before they are ready to be dequeued. This is where you use the java.util.concurrent.DelayQueue class, which implements the BlockingQueue interface. The DelayQueue requires that queue objects be resident on the queue for a specified amount of time.

The real world example that I thought of to illustrate this (which might make you hungry) involves muffins. Well, Muffin objects (as we are talking Java?no coffee pun intended). Suppose you have a DelayQueue upon which you place Muffin objects. The Muffin object (shown below) must implement the java.util.concurrent.Delayed interface to be placed on a DelayQueue. The interface requires the Muffin object to implement the getDelay method (shown below). The getDelay method, in essence, states how much time is left for the object to be kept in the DelayQueue. When the number returned by this method becomes zero or less than zero, the object is ready (or in this example, baked) and allowed to be dequeued (shown in Listing 3).

The Muffin class also implements the compareTo(java.util.concurrent.Delayed) method. Since the Delayed interface extends from the java.lang.Comparable class, this binds you by contract to implement the bakeCompletion time of the Muffin object.

Since you don't really want to eat a Muffin that's not fully cooked, place the Muffin on the DelayQueue for the recommended cooking time. Listing 4, taken from the class DelayQueueUsageExample, shows the queuing and dequeuing of the Muffin objects from the DelayQueue.

As you can see, the cooking time for a Muffin object is set using its constructor (the constructor expects the cooking time to be in seconds).

As stated before, the Muffin objects placed on the DelayQueue are not allowed to be dequeued until their delay time (a.k.a. cooking time) has expired. Elements are dequeued from the queue based on the oldest delay time. In this example, if you have a number of Muffin objects that have been cooked, they will be dequeued on a basis of how long they've been waiting to be dequeued (in other words, the oldest cooked Muffins get the dequeued before the newest cooked Muffins).

Catch 22?The SynchronousQueue
Another blocking queue implementation Java 1.5 makes available is the SynchronousQueue. Interestingly enough, this queue doesn’t have an internal capacity. This is intentional, as the queue is meant for handoff purposes. This means that in a synchronous queue setup, a put request must wait for a take request to the SynchronousQueue from another thread. At the same time, a take request must wait for a put request to the SynchronousQueue from another thread. To demonstrate the concept programmatically, take a look at the sample code. Similar to the LinkedBlockingQueue example earlier, it contains a consumer (SynchConsumer), which is shown in Listing 5.

The code in Listing 5 uses the poll (long timeout, TimeUnit unit) method of the SynchronousQueue class. This method allows for the polling process to wait for a specified amount of time (in this case 20 seconds) before getting tired of waiting for another thread to write to the SynchronousQueue for consumption.

The producer (SynchProducer) shown in Listing 6 uses a similar offer(E o, long timeout, TimeUnit unit) method to enqueue objects on the SynchronousQueue. Use of this method allows a wait time (in this case, 10 seconds) before getting tired of waiting for another thread to read from the SynchronousQueue.

TestSynchQueue shows the producer and consumer in action:

import java.util.concurrent.SynchronousQueue;import java.util.concurrent.LinkedBlockingQueue;public class TestSynchQueue{  public static void main(String args[])  {    SynchronousQueue synchQueue = new SynchronousQueue();    SynchProducer producer = new SynchProducer("ProducerA",synchQueue, System.out);    SynchConsumer consumerA = new SynchConsumer("ConsumerA", synchQueue, System.out);    consumerA.start();    producer.start();  }}

When trying to understand the concept behind a SynchronousQueue, keep in mind where these types of queues are commonly used. The JavaDoc for the Synchronous queue points out:

"They [synchronous queues] are well suited for handoff designs, in which an object running in one thread must sync up with an object running in another thread in order to hand it some information, event, or task."