Java Collections – Deque

Deque implementation:

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.

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

Deque implementations in the Java Collections API:

  1. java.util.ArrayDeque
  2. 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.

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.

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

You can also iterate all elements of a deque, instead of just processing one at a time.

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.

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.

MyObject myObject = deque.remove();

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


   

Share :Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

Comments are closed