Notes on Java Common Data Structures: Queue

Blocking queues provide blocking put and take methods as well as the timed equivalents offer and poll.

BlockingQueue
LinkedBlockingQueue and ArrayBlockingQueue are FIFO queues
PriorityBlockingQueue is a priority-ordered queue, which is useful
when you want to process elements in an order other than FIFO.

PriorityQueue
An unbounded priority queue based on a priority heap. The head of this queue is the least element with respect to the specified ordering. 

Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)].
private transient Object[] queue;

SynchronousQueue
http://blog.nirav.name/2013/12/interesting-use-case-for.html
http://www.ibm.com/developerworks/library/j-5things4/
http://www.drdobbs.com/parallel/java-concurrency-queue-processing-part-2/232900063
http://www.javavm.net/synchronousqueue-example-tutorial/
It is not really a queue at all, in that it maintains no storage space for queued elements. Instead,
it maintains a list of queued threads waiting to enqueue or dequeue an element.
The difference being that the put() call to a SynchronousQueue will not return until there is a corresponding take() call.
it is the default BlockingQueue used for the Executors.newCachedThreadPool() methods. It's essentially the BlockingQueue implementation for when you don't really want a queue (you don't want to maintain any pending data).

Deque, BlockingDeque and work stealing
A Deque is a doubleended
queue that allows efficient insertion and removal from both the head and
the tail. Implementations include ArrayDeque and LinkedBlockingDeque
A producerconsumer
design has one shared work queue for all consumers; in a work stealing
design, every consumer has its own deque. If a consumer exhausts the work in its
own deque, it can steal work from the tail of someone else’s deque. Work stealing
can be more scalable than a traditional producer-consumer design because workers
don’t contend for a shared work queue; most of the time they access only their
own deque, reducing contention. When a worker has to access another’s queue,
it does so from the tail rather than the head, further reducing contention.

LinkedBlockingQueue
private final ReentrantLock takeLock = new ReentrantLock();
private final Condition notEmpty = takeLock.newCondition();

private final ReentrantLock putLock = new ReentrantLock();
private final Condition notFull = putLock.newCondition();

DelayQueue: Elements placed in the queue are not available for removal until their delay time has expired. Items that are furthest past their expiration time are available for removal first. Calls to put() do not block since this queue is unbounded, although calls to take() will block until an expired message is available.

LinkedTransferQueue: Similar to SynchronousQueue, except the queue is unbounded in size and calls to put() never block. Calls to take(), however, will block until a queued item is available for removal.
PriorityBlockingQueue: Similar to SynchronousQueue, except the queue is unbounded in size and calls to put() never block. Calls to take(), however, will block until a queued item is available for removal, and those items are subject to priority-based ordering. Enqueued objects must be comparable, meaning they must implement the Comparable interface and required methods.