The last of the core interfaces in the collection framework is the Deque
interface (pronounced “Deck”). A Deque
is a collection that allows us to manipulate elements from both the front and end of the collection.
The Deque
interface has two types of methods for manipulating the front and back of the collection.
The following methods throw an exception when:
addFirst()
,addLast()
- there is no space to add an element.removeFirst()
,removeLast()
- there is no element to remove.getFirst()
,getLast()
- there is no element to get.
The following methods return a special value:
offerFirst()
,offerLast()
-false
when there is no space to add an element.pollFirst()
,pollLast()
-null
when there is no element to remove.peekFirst()
,peekLast()
-null
when there is no element to get.
A Deque
has many implementations and we’ll focus on the LinkedList
and ArrayDeque
implementations. The LinkedList
, although not the most optimized, is flexible enough to not only be used as a List
and Queue
but also a Deque
. The ArrayDeque
is the preferred implementation when needing to manipulate elements at the front and end of a collection.
Let’s look at a LinkedList
implementation of a Deque
:
Deque<String> stringDeque = new LinkedList<>(); stringDeque.addFirst("A"); // Front -> "A" <- end stringDeque.offerFirst("B"); // Return `true` - front -> "B", "A" <- end stringDeque.offerLast("Z"); // Returns `true` - front -> "B", "A", "Z" <- end String a = stringDeque.removeFirst() // Returns "B" - front -> "A", "Z" String b = stringDeque.pollLast() // Returns "Z" - front -> "A" <- back String c = stringDeque.removeLast() // Returns "A" - empty deque String d = stringDeque.peekFirst() // Returns null String e = stringDeque.getLast() // Throws NoSuchElementException
In the example above we:
- Called
addFirst()
,offerFirst()
, andofferLast()
to add elements. Note that theoffer()
methods return a boolean. - Called
removeFirst()
,pollLast()
, andremoveLast()
to remove elements. - Called
peekFirst()
andgetLast()
to get but not remove the element at the front and back of deque respectively.
We can iterate Deque
from front to back using an enhanced for-loop
and we can use the descendingIterator()
method and use the Iterator
returned to go from back to front.
// Assuming `stringDeque` has elements front -> "Mike", "Jack", "John" <- back Iterator<String> descItr = stringDeque.descendingIterator(); while(descItr.hasNext()) { System.out.println(descItr.next()); } // OUTPUT TERMINAL: "John", "Jack", "Mike"
Let’s practice creating a Deque
and iterating through it.
Instructions
Let’s practice using a Deque
to separate odd and even integers stored in a List
.
In Main.java, let’s complete the body of separateInts()
by first defining an Integer
type Deque
named separatedDeque
with an ArrayDeque
implementation.
Let’s create a separation between even and odd elements in integers
.
In separateInts()
, define an enhanced for-loop
that iterates over integers
using an Integer
named myInt
. In the body of the for-loop
add myInt
to the front of separatedDeque
if it’s even and add it to the back otherwise.
Let’s complete separateInts()
by return
ing separatedDeque
and running the program.