[collections][SUBMIT] Queue (A double-ended thread-safe queue)

[Jeff Varszegi <jv...@yahoo.com>]

It has been suggested that I make this class implement the Buffer interface, so I will look into
that at the first opportunity (tomorrow).  This is a queue that can satisfy requests from multiple
threads, delivering output to them in the proper order.  It is double-ended, and supports blocking
(indefinitely and for a specified number of milliseconds).  It supports removal and peeking at
entries.  Javadoc is included, so take a look at that for a full explanation if you're interested.

The internal mechanism is a doubly-linked list.  All threads that block go into a separate
internal doubly-linked list.  Nodes of both types (to hold elements and waiting threads) are
created anew only if there are none in the internal cache.  I didn't use LinkedList inside the
class because it is wasteful.  In the end, it looks like this class is less than twice as slow as
LinkedList, even though it is heavily synchronized.

To avoid method-call overhead, method calls are flat-- only one deep.  The only exceptions to this
are convenience methods for using the queue as a single-ended queue; for instance, the remove()
method calls removeFirst().  There are lots of comments inside the methods to explain what's going
on.

Please check the code for correctness and performance if you have a chance, and let me know any
thoughts you may have.

Jeff

__________________________________________________
Do you Yahoo!?
Yahoo! Web Hosting - Let the expert host your site
http://webhosting.yahoo.com