Tech and Media Labs
This site uses cookies to improve the user experience.




Java Collections - Deque

Jakob Jenkov
Last update: 2014-06-23

The java.util.Deque interface is a subtype of the java.util.Queue interface. It represents a queue where you can insert and remove elements from both ends of the queue. Thus, "Deque" is short for "Double Ended Queue" and is pronounced "deck", like a deck of cards.

Here is a list of the topics covered in this text:

  1. Deque Implementations
  2. Adding and Accessing Elements
  3. Removing Elements
  4. Generic Deques
  5. More Details in the JavaDoc

Deque Implementations

Being a Queue subtype all methods in the Queue and Collection interfaces are also available in the Deque interface.

Since Deque is an interface you need to instantiate a concrete implementation of the interface in order to use it. You can choose between the following Deque implementations in the Java Collections API:

  • java.util.ArrayDeque
  • java.util.LinkedList

LinkedList is a pretty standard deque / queue implementation.

ArrayDeque stores its elements internally in an array. If the number of elements exceeds the space in the array, a new array is allocated, and all elements moved over. In other words, the ArrayDeque grows as needed, even if it stores its elements in an array.

There are also Queue implementations in the java.util.concurrent package, but I will leave the concurrency utilities out of this tutorial.

Here are a few examples of how to create a Deque instance:

Deque dequeA = new LinkedList();
Deque dequeB = new ArrayDeque();

Adding and Accessing Elements

To add elements to the tail of a Deque you call its add() method. You can also use the addFirst() and addLast() methods, which add elements to the head and tail of the deque.

Deque dequeA = new LinkedList();

dequeA.add     ("element 1"); //add element at tail
dequeA.addFirst("element 2"); //add element at head
dequeA.addLast ("element 3"); //add element at tail

The order in which the elements added to the Deque are stored internally, depends on the implementation. The two implementations mentioned earlier both store the elements in the order (first or last) in which they are inserted.

You can peek at the element at the head of the queue without taking the element out of the queue. This is done via the element() method. You can also use the getFirst and getLast() methods, which return the first and last element in the Deque. Here is how that looks:

Object firstElement = dequeA.element();
Object firstElement = dequeA.getFirst();
Object lastElement  = dequeA.getLast();

Taking elements from the deque is covered later.

You can also iterate all elements of a deque, instead of just processing one at a time. Here is how that looks:

Deque dequeA = new LinkedList();

dequeA.add("element 0");
dequeA.add("element 1");
dequeA.add("element 2");

//access via Iterator
Iterator iterator = dequeA.iterator();
while(iterator.hasNext(){
  String element = (String) iterator.next();
}

//access via new for-loop
for(Object object : dequeA) {
    String element = (String) object;
}

When iterating the deque via its Iterator or via the for-loop (which also uses the Iterator behind the scene, the sequence in which the elements are iterated depends on the deque implementation.


Removing Elements

To remove elements from a deque, you call the remove(), removeFirst() and removeLast methods. Here are a few examples:

Object firstElement = dequeA.remove();
Object firstElement = dequeA.removeFirst();
Object lastElement  = dequeA.removeLast();

Generic Deque

By default you can put any Object into a Deque, but from Java 5, Java Generics makes it possible to limit the types of object you can insert into a Deque. Here is an example:

Deque<MyObject> deque = new LinkedList<MyObject>();

This Deque can now only have MyObject instances inserted into it. You can then access and iterate its elements without casting them. Here is how it looks:

MyObject myObject = deque.remove();

for(MyObject anObject : deque){
   //do someting to anObject...   
}

For more information about Java Generics, see the Java Generics Tutorial.


More Details in the JavaDoc

There is a lot more you can do with a Deque, but you will have to check out the JavaDoc for more details. This text focused on the two most common operations: Adding / removing elements, and iterating the elements.

Jakob Jenkov




Copyright  Jenkov Aps
Close TOC