Section 14.4. Deque

14.4. Deque

A deque (pronounced "deck") is a double-ended queue. Unlike a queue, in which elements can be inserted only at the tail and inspected or removed only at the head, a deque can accept elements for insertion and present them for inspection or removal at either end. Also unlike Queue, Deque's contract specifies the ordering it will use in presenting its elements: it is a linear structure in which elements added at the tail are yielded up in the same order at the head. Used as a queue, then, a Deque is always a FIFO structure; the contract does not allow for, say, priority deques. If elements are removed from the same end (either head or tail) at which they were added, a Deque acts as a stack or LIFO (Last In First Out) structure.

Deque and its subinterface BlockingDeque were introduced in Java 6. The fast Deque implementation ArrayDeque uses a circular array (see Section 14.3.2), and is now the implementation of choice for stacks and queues. Concurrent deques have a special role to play in parallelization, discussed in Section 14.4.2.

The Deque interface (see Figure 14.7) extends Queue with methods symmetric with respect to head and tail. For clarity of naming, the Queue methods that implicitly refer to one end of the queue acquire a synonym that makes their behavior explicit for Deque. For example, the methods peek and offer, inherited from Queue, are equivalent to peekFirst and offerLast. (First and last refer to the head and tail of the deque; the JavaDoc for Deque also uses "front" and "end".)

Figure 14-7. Deque

Collection-like Methods

 void addFirst(E e)      // insert e at the head if there is enough space void addLast(E e)       // insert e at the tail if there is enough space void push(E e)          // insert e at the head if there is enough space boolean removeFirstOccurrence(Object o);                         // remove the first occurrence of o boolean removeLastOccurrence(Object o);                         // remove the last occurrence of o Iterator<E> descendingIterator()                         // get an iterator, returning deque elements in                         // reverse order 

The contracts for the methods addFirst and addLast are similar to the contract for the add method of Collection, but specify in addition where the element to be added should be placed, and that the exception to be thrown if it cannot be added is IllegalState-Exception. As with bounded queues, users of bounded deques should avoid these methods in favor of offerFirst and offerLast, which can report "normal" failure by means of a returned boolean value.

The method name push is a synonym of addFirst, provided for the use of Deque as a stack. The methods removeFirstOccurrence and removeLastOccurrence are analogues of Collection.remove, but specify in addition exactly which occurrence of the element should be removed. The return value signifies whether an element was removed as a result of the call.

Queue-like Methods

 boolean offerFirst(E e) // insert e at the head if the deque has space boolean offerLast(E e)  // insert e at the tail if the deque has space 

The method offerLast is a renaming of the equivalent method offer on the Queue interface.

The methods that return null for an empty deque are:

 E peekFirst()           // retrieve but do not remove the first element E peekLast()            // retrieve but do not remove the last element E pollFirst()           // retrieve and remove the first element E pollLast()            // retrieve and remove the last element 

The methods peekFirst and pollFirst are renamings of the equivalent methods peek and poll on the Queue interface.

The methods that throw an exception for an empty deque are:

 E getFirst()            // retrieve but do not remove the first element E getLast()             // retrieve but do not remove the last element E removeFirst()         // retrieve and remove the first element E removeLast()          // retrieve and remove the last element E pop()                 // retrieve and remove the first element 

The methods getFirst and removeFirst are renamings of the equivalent methods element and remove on the Queue interface. The method name pop is a synonym forremoveFirst, again provided for stack use.

14.4.1. Implementing Deque

14.4.1.1. ArrayDeque

Along with the interface Deque, Java 6 also introduced a very efficient implementation, ArrayDeque, based on a circular array like that of ArrayBlockingQueue (see Section 14.3.2). It fills a gap among Queue classes; previously, if you wanted a FIFO queue to use in a single-threaded environment, you would have had to use the class LinkedList (which we cover next, but which should be avoided as a general-purpose Queue implementation), or else pay an unnecessary overhead for thread safety with one of the concurrent classes ArrayBlockingQueue or LinkedBlockingQueue. ArrayDeque is now the general-purpose implementation of choice, for both deques and FIFO queues. It has the performance characteristics of a circular array: adding or removing elements at the head or tail takes constant time. The iterators are fail-fast.

14.4.1.2. LinkedList

Among Deque implementations LinkedList is an oddity; for example, it is alone in permitting null elements, which are discouraged by the Queue interface because of the common use of null as a special value. It has been in the Collections Framework from the start, originally as one of the standard implementations of List (see Section 15.2), and was retrofitted with the methods of Queue for Java 5, and those of Deque for Java 6. It is based on a linked list structure similar to those we saw in Section 13.2.2 as the basis for skip lists, but with an extra field in each cell, pointing to the previous entry (see Figure 14.8). These pointers allow the list to be traversed backwardsfor example, for reverse iteration, or to remove an element from the end of the list.

Figure 14-8. A doubly linked list

As an implementation of Deque, LinkedList is unlikely to be very popular. Its main advantage, that of constant-time insertion and removal, is rivalled in Java 6for queues and dequesby the otherwise superior ArrayDeque. Previously you would have used it in situations where thread safety isn't an issue and you don't require blocking behavior. Now, the only likely reason for using LinkedList as a queue or deque implementation would be that you also needed random access to the elements. With LinkedList, even that comes at a high price; because random access has to be implemented by linear search, it has time complexity of O(n).

The constructors for LinkedList are just the standard ones of Section 12.3. Its iterators are fail-fast.

14.4.2. BlockingDeque

Figure 14.9 shows the methods that BlockingDeque adds to BlockingQueue (see Figure 14.5). Each of the two blocking insertion methods and two removal methods of BlockingQueue is given a synonym to make explicit which end of the deque it modifies, together with a matching method to provide the same action at the other end. So offer, for example, acquires a synonym offerLast and a matching method offerFirst. As a result, the same four basic behaviors that were defined for BlockingQueuereturning a special value on failure, returning a special value on failure after a timeout, throwing an exception on failure, and blocking until successcan be applied for element insertion or removal at either end of the deque.

Figure 14-9. BlockingDeque

Good load balancing algorithms will be increasingly important as multicore and multiprocessor architectures become standard. Concurrent deques are the basis of one of the best load balancing methods, work stealing. To understand work stealing, imagine a load-balancing algorithm that distributes tasks in some wayround-robin, sayto a series of queues, each of which has a dedicated consumer thread that repeatedly takes a task from the head of its queue, processes it, and returns for another. Although this scheme does provide speedup through parallelism, it has a major drawback: we can imagine two adjacent queues, one with a backlog of long tasks and a consumer thread struggling to keep up with them, and next to it an empty queue with an idle consumer waiting for work. It would clearly improve throughput if we allowed the idle thread to take a task from the head of another queue. Work stealing improves still further on this idea; observing that for the idle thread to steal work from the head of another queue risks contention for the head element, it changes the queues for deques and instructs idle threads to take a task from the tail of another thread's deque. This turns out to be a highly efficient mechanism, and is becoming widely used.

14.4.2.1. Implementing BlockingDeque

The interface BlockingDeque has a single implementation, LinkedBlockingDeque. LinkedBlockingDeque is based on a doubly linked list structure like that of LinkedList. It can optionally be bounded so, besides the two standard constructors, it provides a third which can be used to specify its capacity:

 LinkedBlockingDeque(int capacity) 

It has similar performance characteristics to LinkedBlockingQueuequeue insertion and removal take constant time and operations such as contains, which require traversal of the queue, require linear time. The iterators are weakly consistent.