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.
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:
LinkedList is a pretty standard Deque / Queue implementation.
Internal 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.
Possible Usage
Because the double-ended queue supports addition or removal of elements from either end of the data structure, it can be used as a queue (first-in-first-out/FIFO) or as a stack (last-in-first-out/LIFO). J2SE 5 introduced a Queue interface and the Deque interface extends this interface. Note that a Vector-based Stack class has been present since JDK 1.0, but the Javadoc documentation for this class states that Deque should be used instead because it provides better LIFO operation support. Implementations of Deque are typically expected to perform better than Stack as well.
The Deque interface is extended by the concurrency-supporting interface BlockingDeque and is implemented by classes LinkedBlockingDeque (introduced in Java SE 6), LinkedList (available since JDK 1.2, but now implements Deque), and ArrayDeque (introduced in Java SE 6). For this blog entry, I will demonstrate using one Deque instance as a queue and one Deque instance as a stack using ArrayDeque for both. ArrayDeque is not thread-safe and does not allow for elements of the data structure to be null (a recommended but not required condition of Deque implementations and uses).
Operations on Deque
Adding to deque
To add elements to the tail of a
Getting or Peeking the element
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:
Removing the element
To remove elements from a deque, you call the remove(), removeFirst() and removeLast methods. Here are a few examples:
Iterating over the elements
One method is normal foreach style:
Another method is via iterator
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 (Click on the link to read about it.)
- java.util.LinkedList
LinkedList is a pretty standard Deque / Queue implementation.
Internal 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.
Possible Usage
Because the double-ended queue supports addition or removal of elements from either end of the data structure, it can be used as a queue (first-in-first-out/FIFO) or as a stack (last-in-first-out/LIFO). J2SE 5 introduced a Queue interface and the Deque interface extends this interface. Note that a Vector-based Stack class has been present since JDK 1.0, but the Javadoc documentation for this class states that Deque should be used instead because it provides better LIFO operation support. Implementations of Deque are typically expected to perform better than Stack as well.
The Deque interface is extended by the concurrency-supporting interface BlockingDeque and is implemented by classes LinkedBlockingDeque (introduced in Java SE 6), LinkedList (available since JDK 1.2, but now implements Deque), and ArrayDeque (introduced in Java SE 6). For this blog entry, I will demonstrate using one Deque instance as a queue and one Deque instance as a stack using ArrayDeque for both. ArrayDeque is not thread-safe and does not allow for elements of the data structure to be null (a recommended but not required condition of Deque implementations and uses).
Operations on Deque
Adding to deque
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
Getting or Peeking the element
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();
Removing the element
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();
Iterating over the elements
One method is normal foreach style:
//access via new for-loop
for(Object object : dequeA) {
String element = (String) object;
}
Another method is via iterator
//access via Iterator
Iterator iterator = dequeA.iterator();
while(iterator.hasNext(){
String element = (String) iterator.next();
}
