Queues
Queues are used to contain lists of elements which are scheduled for further processing. Usually, elements are processed in the order they were added; this is known as first-in-first-out (FIFO) processing.
Figure 1. The Taxonomy of Queues
You can implement queues either using an array or a linked-list (single or double). In most Queue implementations, the head element has been in the Queue the longest time and the tail element has been in the queue the shortest. Some implementations, like PriorityQueues, allow you to override this default behavior by using a caller-supplied Comparator.
A Queue collection is not intended to allow random access to elements, so using get(index) is not supported. Also, null elements are not usually allowed, as these are treated as return values for some methods, like poll(). Queue implementations in JDK 1.6 and 1.5 do not allow nulls except for LinkedList, which has been retrofitted to implement Queue interface in JDK 1.5.
Memory Requirements
Queue implementations can be capacity bounded or unbounded. You must supply a capacity limit to the constructor, which cannot be changed later.
Thread Safety and Blocking Calls
Some implementations of Queue exhibit thread safety and can support blocking calls, as defined in BlockingQueue. If Blocking is a part of the Queue name, then the methods will be thread safe, however, some operations will wait indefinitely or for a stipulated time for the Queue to change.
Blocking Queues
Apart from the general methods in queue that support storing and retrieval, there are two additional methods with two different flavors that support blocking:
| Blocks indefinitely |
Fixed Time Blocking |
| put(e) |
offer(e, time, unit) |
| take() |
poll(time, unit) |
TimeUnits are enumeration types for specifying the time durations at a given unit of granularity, for example:
offer(7, 50L, TimeUnit.MILLISECONDS)
The above statement attempts to store an element in 50 milliseconds and returns false after the stipulated time has expired.
The remainingCapacity() method returns Integer.MAX_VALUE. If the queue is unbounded otherwise, it returns the count of empty slots remaining in the queue. A put() on a queue with a remainingCapacity() greater than zero will succeed without blocking.
Implementation Classes
Figure 2. The Queue Class Diagram
Figure 3. Blocking the Queue Class Diagram
AbstractQueue
AbstractQueue provides a skeleton implementation for the following methods:
/** AbstractQueue */
public boolean add(E o); /*calls offer(e)*/
public E remove(); /*calls poll()*/
public E element(); /*calls peek()*/
public void clear(); /*calls poll() until it returns null*/
public boolean addAll(Collection c); /*calls Iterator and add(e)*/
PriorityQueue
Ordering elements in PriorityQueue is based on the priority of the element as opposed to the arrival time. Here, the priority of an element is determined by whether a Comparator is supplied to the constructor.
If no Comparator is provided, the natural ordering of the elements (using Comparable) will be used to determine priority. Capacity is unbounded and methods are not thread-safe. Also note that Iterator is not guaranteed to traverse the elements in any particular order. The table below summarizes the functional characteristics of PriorityQueue:
| Memory Requirements |
Capacity Unbounded |
| Thread Safe |
No (Use PriorityBlockingQueue) |
| Implemented Using |
balanced binary heap |
| Iterator Type |
fail-fast |
Performance
|
| Methods |
Complexity |
|
| peek, element, size |
O(1) |
| offer, poll, remove, add |
O(log(n)) |
| remove(e), contains(e) |
O(n) |
|
ConcurrentLinkedQueue
This is a nonblocking queue that employs a wait-free algorithm to access a queue concurrently without thread suspension and context switching. Elements are declared as volatile references and updates are done through AtomicReferenceFieldUpdater, which comes in three flavors: Integer, Long, and Reference:
| Memory Requirements |
Capacity Unbounded |
| Thread Safe |
Yes |
| Implemented Using |
Singly-linked nodes |
| Iterator Type |
weakly consistent |
Performance
[ignoring time spent retries] |
| Methods |
Complexity |
|
| peek, element, size |
O(1) |
| offer, poll, remove, add |
O(1) |
remove(e), contains(e),
iterator.remove,size() |
O(n) |
|
New on the Java Boutique:
New Review:
Time Management Made Easy with the Quartz Enterprise Job Scheduler
Why not just use the Java timer API? This open source scheduling
API boasts simplicity, ease-of-integration, a well-rounded feature
set, and it's free!
New Applet:
Reverse Complement
Reverse Complement is a simple applet that converts DNA or RNA
sequences into three useful formats.
Elsewhere on internet.com:
WebDeveloper Java
Lots of Java information on webdeveloper.com
WDVL Java
Thorough Java resource at the Web Developer's Virtual Library.
ScriptSearch Java
Hundreds of free Java code files to download.
jGuru: Your View of the Java Universe
Customizable portal with online training, FAQs, regular news updates, and tutorials.
