Deques – Collections: Part II

15.7 Deques

In this section we look at deques—that is, linear collections that allow processing of elements from both ends.

The Deque<E> Interface

The Deque<E> interface extends the Queue<E> interface to allow double-ended queues. Such a queue is called a deque. It allows operations not just at its head as a queue, but also at its tail. It is a linear unbounded structure in which elements can be inserted at or removed from either end. Various synonyms are used in the literature for the head and tail of a deque: front and back, first and last, start and end.

A deque can be used as a FIFO queue, where elements added at the tail are presented at the head for inspection or removal in the same order, thus implementing FIFO ordering. A deque can also be used as a stack, where elements are added to and removed from the same end, thus implementing LIFO ordering.

The Deque<E> interface defines symmetrical operations at its head and tail. Which end is in question is made evident by the method name. A XXXFirst() method and a XXXLast() method process an element at the head and at the tail, respectively. Below, equivalent methods from the Queue<E> interface are also identified. The push() and pop() methods are convenient for implementing stacks.

Click here to view code image

// Insert
boolean offerFirst(E element)
boolean offerLast(E element)                  
Queue equivalent:
 offer()
void addFirst(E element)
void addLast(E element)                      
Queue equivalent:
 add()
void push(E element)                         
Synonym:
 addFirst()

Insert the specified element in the deque. They all throw a NullPointerException if the specified element is null. The addFirst() and addLast() methods throw an IllegalStateException if the element cannot be added, but the offerFirst() and offerLast() methods do not.

Click here to view code image

// Remove
E removeFirst()                              
Queue equivalent:
 remove()
E removeLast()
E pollFirst()                                
Queue equivalent:
 poll()
E pollLast()
E pop()                                       
Synonym:
 removeFirst()
boolean removeFirstOccurence(Object obj)
boolean removeLastOccurence(Object obj)

Remove an element from the deque. The removeFirst() and removeLast() methods throw a NoSuchElementException if the deque is empty. The pollFirst() and pollLast() methods return null if the deque is empty.

Click here to view code image

// Examine
E getFirst()                                 
Queue equivalent:
 element()
E getLast()
E peekFirst()                                 
Queue equivalent:
 peek()
E peekLast()

Retrieve an element from the deque, but do not remove it from the deque. The getFirst() and getLast() methods throw a NoSuchElementException if the deque is empty. The peekFirst() and peekLast() methods return null if the deque is empty.

Click here to view code image

// Misc.
Iterator<E> descendingIterator()

Returns an iterator to iterate over the deque in reverse order—that is, from the tail to the head.

Table 15.5 summarizes the methods provided by the Deque<E> interface, showing which operations can be performed at the head and which ones at the tail of the deque. Each row indicates the runtime behavior of the methods in that row, whether they throw an exception or not. Any method whose name starts with either “offer”, “poll”, or “peek” does not throw an exception. Counterpart methods inherited from the Queue<E> interface are marked by an asterisk (*) in the table.

Table 15.5 Summary of Deque Methods

Insert at the head	Insert at the tail	Runtime behavior on failure
offerFirst()	offerLast(), offer()*	Returns false if full
addFirst()	addLast(), add()*	Throws IllegalStateException
Remove from the head	Remove from the tail	Runtime behavior on failure
pollFirst(), poll()*	pollLast()	Returns null if empty
removeFirst(), remove()*	removeLast()	Throws NoSuchElementException
peekFirst(), peek()*	peekLast()	Returns null if empty
getFirst(), element()*	getLast()	Throws NoSuchElementException