henterji's blog
henterji · 2006-07-22
<< Top 30 Ruby on Rails Tutorials : Ultimate Web Developer Lists : eConsultant
|
首 页
|
Swing and Roundabouts 4: Grid Bag Grease >>
Minding the Queue: Java 1.5 Adds a New Data Structure Interface
- [
]
2006-07-22
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.
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).
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<String> blockingQueue = new LinkedBlockingQueue<String>();
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<String> blockingQueue = new LinkedBlockingQueue<String>();
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<String> synchQueue = new SynchronousQueue<String>();
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."
Download The Code for this Article
Tags:
Java
henterji
发表于 10:33:48 |
引用 0
|
编辑
评论
发表评论
姓名
E-mail
地址
原始快照:web.archive.org