About
Collection - Queue (FIFO) and Collection - Stack (LIFO) in Java concurrency context
Articles Related
Interface and Implementation
Java Concurrency - java.util.concurrent Interface and Implementation
Blocking queue
The BlockingQueue interface defines a first-in-first-out data structure that blocks or times out when you attempt to:
- add to a full queue, (put method)
- or retrieve from an empty queue. (take and remove methods)
BlockingQueue implementations are designed to be used primarily for producer-consumer queues.
The BlockingDeque interface extends BlockingQueue to support both FIFO and LIFO (stack-based) operation.
Interface | Operations | Implementation |
---|---|---|
BlockingQueue | FIFO | ArrayBlockingQueue |
BlockingQueue | FIFO | LinkedBlockingQueue |
BlockingQueue | FIFO | SynchronousQueue |
BlockingQueue | FIFO | PriorityBlockingQueue |
BlockingQueue | FIFO | DelayQueue |
BlockingDeque | FIFO and LIFO (stack-based) operation | LinkedBlockingDeque |
After some tests, ArrayBlockingQueue seems to be quicker than the LinkedBlockingQueue.
Non-blocking queue
- FIFO: The ConcurrentLinkedQueue class supplies an efficient scalable thread-safe non-blocking FIFO queue. ConcurrentLinkedQueue is not using locks, but Compare and swap (CAS) for synchronization.See Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms by Maged M. Michael and Michael L. Scott.
- FIFO and LIFO The ConcurrentLinkedDeque class is similar, but additionally supports the Deque interface.
Synchronous transfer (between producer and consumer)
Extended interface TransferQueue, and implementation LinkedTransferQueue introduce a synchronous transfer method (along with related features) in which a producer may optionally block awaiting its consumer.
End of Queue
End-of-stream or poison objects
From the Blocking Queue doc
A BlockingQueue does not intrinsically support any kind of "close" or "shutdown" operation to indicate that no more items will be added. The needs and usage of such features tend to be implementation-dependent.
A common tactic is for producers to insert special end-of-stream or poison objects, that are interpreted accordingly when taken by consumers.
A end-of-stream or poison objects is a marker object that is added to the queue in order to mark the end of the queue.
Code example in the consumer:
while (true) {
String element = queue.take();
if ("EndOfStream".equals(element)) {
System.out.println("End of Queue quiting");
break;
}
}