Learn

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(), and offerLast() to add elements. Note that the offer() methods return a boolean.
Called removeFirst(), pollLast(), and removeLast() to remove elements.
Called peekFirst() and getLast() to get but not remove the element at the front and back of deque respectively.

We can iterate Deque front 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(itr.hasNext()) {
  System.out.println(itr.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 seperateInts() by first defining an Integer type Deque named seperatedDeque 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 returning separatedDeque and running the program.

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?

Log in from a computer to take this course

Instructions

Take this course for free

Or sign up using: