e-Zest members share technology ideas to foster digital transformation.

Queues And Blocking Queues

Written by Madhura Oak | Jul 10, 2012 1:17:11 PM

The Java Collections Framework provides Queue interface and its implementation classes as shown in Figure 1 which enable usage of queue data structure in a variety of ways. The interfaces and classes highlighted in this figure are part of Concurrency API.

Figure 1. Queue Interfaces and Classes in Java Collections Framework

Queue
This interface extends Collection interface and exists since Java 5. It provides methods to insert, remove or inspect elements in First In First Out (FIFO) or Last In First Out (LIFO) way.

The offer(e) method is used to add elements. It returns true if the element is added to the queue. The add(e) method of Collection interface can also be used for adding element in the queue. However, it throws exception when the capacity of bounded queue is full. The offer(e) method returns false when the capacity of bounded queue is full and is preferred to using add(e).

The poll() method removes the element from the head of the queue and returns it. It returns null if the queue is empty. The remove() method is also available to remove an element from the head of queue but it throws exception when the queue is empty.

The element() method retrieves element at the head of the queue and returns it. It throws an exception if the queue is empty. The equivalent peek() method returns null if the queue is empty.

ConcurrentLinkedQueue

This class provides thread-safe and unbounded FIFO queue based on linked nodes. It implements Queue interface and exists since Java 5. Elements are added at the tail of the queue. Like other concurrent collection classes, this class also does not allow null elements.

PriorityQueue

This class provides unbounded and ordered queue. It implements Queue interface and exists since Java 5. The least element as per the natural or defined ordering is present at the head of the queue. If there are multiple elements with the same least value then any one can be at the head of the queue. Null elements are not allowed. The iterator on priority queue does not guarantee traversal of elements in an order. This class is not thread-safe.

Deque

This interface provides a double ended queue – insertion and removal of elements is possible at both head and tail of the queue. It extends Queue and exists since Java 6.

The offerFirst(e) and offerLast(e) methods allow insertion of elements in the deque. If the deque capacity is full these methods return false. They return true if the element is inserted in the deque. The equivalent addFirst(e) and addLast(e) methods throw exception when the deque capacity is full.

The pollFirst() and pollLast() methods allow removal of elements from the deque. The removed elements are returned by these methods. If the deque is empty these methods return null. The equivalent removeFirst() and removeLast() methods throw exception if the deque is empty.

The peekFirst() and peekLast() allow retrieval of elements from the deque without removing them. These methods return the elements if the deque is not empty. They return null if the deque is empty. The equivalent getFirst() and getLast() methods throw exception if the deque is empty.

ArrayDeque

This class provides unbounded deques and is faster than Stack and LinkedList. This class should be preferred instead of Stack and LinkedList when you want to use LIFO queue or FIFO deque. This class implements Deque and exists since Java 6. This class is not thread-safe.

LinkedList

This class provides doubly linked list. It is not thread-safe. It implements List and Deque interfaces. Use of ArrayDeque should be preferred over LinkedList since the former is faster.

ConcurrentLinkedDeque

This class provides unbounded and thread-safe deque based on linked nodes. It was introduced in Java 7 and implements Deque interface. It does not allow null elements.

BlockingQueue

A blocking queue is a queue which provides insert and remove operations that block or keep waiting until they are performed. The blocking queues are usually used in Producer-Consumer frameworks. This interface extends Queue and exists since Java 5. Null elements are not allowed. All implementation classes of this interface are thread-safe.

The put(e) method of this interface inserts element in the queue. If the queue is full, this method waits until the space is available in the queue. The take() method removes the element from the head of the queue. If the queue is empty it waits until the element becomes available.

This interface also provides timed offer and poll methods. The offer(e, time, unit) method inserts element in the queue and waits for the specified time if required for the space to become available when the queue is full. This method returns true when the element is inserted in the queue. When the specified time elapses and the element is not inserted in the queue, this method returns false. The poll(e, time, unit) method retrieves elements from the head of the queue and waits for the specified time if required for the element to become available when the queue is empty. This method returns the element if it is retrieved from the queue. If the element is not available till the time elapses, this method returns null.

ArrayBlockingQueue

This class provides bounded blocking FIFO queue backed by an array. The capacity is defined during instantiating this class. The fairness policy can also be set during creation. By default, this class is unfair. Elements are inserted at the tail of the queue. This class implements BlockingQueue interface and exists since Java 5.

DelayQueue

This class provides unbounded blocking queue of elements that implement Delayed interface. Only the elements whose delay has expired can be removed from this blocking queue. The element whose delay has expired furthest in the past is at the head of the queue. If there are no elements with delay expired the poll method returns null. This class implements BlockingQueue interface and exists since Java 5.

LinkedBlockingQueue

This class provided optionally bounded blocking FIFO queue based on linked nodes. It implements BlockingQueue interface and exists since Java 5.

PriorityBlockingQueue

This class provides unbounded and thread-safe priority queue implementation. Ordering of elements with equal priority is not taken care by this class and a custom comparator needs to be defined to take care of this. This class implements BlockingQueue interface and exists since Java 5.

SynchronousQueue

This class provides a blocking queue with zero capacity – an empty collection. It acts as a channel to handoff the element from producer to consumer. The insert operation in this queue waits for the the corresponding remove operation and vice-versa. The peek operation cannot be performed on this queue. This class implements BlockingQueue interface and exists since Java 5.

BlockingDeque

This interface provides a deque that supports blocking operations. It extends BlockingQueue and Deque interfaces and exists since Java 6. All implementation classes of BlockingDeque are thread-safe and do not allow null elements.

The putFirst(e) and putLast(e) provide blocking insert operations at the head and tail of the deque respectively. The takeFirst() and takeLast() provide blocking removal operations.

The timed offer and poll operations at the head and tail of deque can be performed using these methods – offerFirst(e, time, unit), offerLast(e, time, unit), pollFirst(time, unit) and pollLast(time, unit).

LinkedBlockingDeque

This class provides optionally-bounded blocking deque based on linked nodes. It implements BlockingDeque interface and exists since Java 6.

TransferQueue

This interface provides a blocking queue in which producers may wait for consumers to receive elements. This interface extends BlockingQueue and was introduced in Java 7.

The transfer(e) method is used to transfer the element immediately if the consumer is already waiting to receive it using using take() or timed poll. If the consumer is not available, the producer waits until the element is received by the consumer. The non-blocking tryTransfer(e) method transfers the element if the consumer is already available waiting to receive it or returns false. The tryTransfer(e, timeout, unit) tries to transfer the element within the specific timeout period. This method returns true if the element is transferred before the timeout elapses and false if the element cannot be transferred.

The hasWaitingConsumer() method can be used to find out whether there is any consumer waiting to receive an element via take() or timed poll. This method returns true if atleast one waiting consumer exists.

LinkedTransferQueue

This class provides unbounded transfer FIFO queue based on linked nodes. This class implements TransferQueue interface and was introduced in Java 7.