Deque Interface and ArrayDeque in Java
The Deque interface in Java, pronounced "deck", stands for double-ended queue. It is used for a collection where elements can be added and removed at both ends: the front (head) and the back (tail). Because of this, a deque can act as a normal queue (FIFO) or as a stack (LIFO). ArrayDeque is the most common implementation; it stores elements in a resizable circular array and is faster than both Stack and LinkedList. In this lesson, you will learn the methods of Deque, how to use ArrayDeque, and then build a small playlist manager that combines several collections.
Declaration
public interface Deque<E> extends Queue<E>, SequencedCollection<E>
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, SerializableMethods of Deque
| Method | Description |
|---|---|
offerFirst(e) / addFirst(e) | It is used to add an element at the front. |
offerLast(e) / addLast(e) | It is used to add an element at the back. |
pollFirst() / removeFirst() | It removes and returns the front element. |
pollLast() / removeLast() | It removes and returns the back element. |
peekFirst() / getFirst() | It returns the front element without removing it. |
peekLast() / getLast() | It returns the back element without removing it. |
push(e) | It adds at the front (stack style), same as addFirst. |
pop() | It removes from the front (stack style), same as removeFirst. |
The offer/poll/peek forms return false or null when they fail; the add/remove/get forms throw.
Features of ArrayDeque
- Both ends: fast O(1) adds and removes at the front and back.
- No capacity limit: it grows as needed.
- No
nullelements:nullis used internally to mean "empty slot". - Faster than
Stack(no locking) and faster thanLinkedList(no node objects). - Not synchronized.
Example: Both Ends of a Deque
Let's see an example of adding and removing at each end.
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeDemo {
public static void main(String[] args) {
Deque<String> d = new ArrayDeque<>();
d.offerLast("Srihitha");
d.offerFirst("Navika");
d.offerLast("Advitha");
System.out.println("Deque: " + d);
System.out.println("Front: " + d.peekFirst()
+ ", back: " + d.peekLast());
System.out.println("Removed front: " + d.pollFirst());
System.out.println("Removed back: " + d.pollLast());
System.out.println("Left: " + d);
}
}Deque: [Navika, Srihitha, Advitha]
Front: Navika, back: Advitha
Removed front: Navika
Removed back: Advitha
Left: [Srihitha]Explanation: offerFirst put Navika in front of Srihitha, and offerLast put Advitha at the back. pollFirst and pollLast then removed one element from each end.
Example: Undo History as a Stack
import java.util.ArrayDeque;
import java.util.Deque;
public class Undo {
public static void main(String[] args) {
Deque<String> history = new ArrayDeque<>();
history.push("type Hello");
history.push("make bold");
history.push("insert image");
System.out.println("Undo: " + history.pop());
System.out.println("Undo: " + history.pop());
System.out.println("Remaining: " + history);
}
}Undo: insert image
Undo: make bold
Remaining: [type Hello]Explanation: Each action is pushed on the front. Undo pops the most recent action first, exactly like a stack.
The Checkpoint: A Playlist Manager
This program brings together what this chapter has covered so far. It keeps a playlist in an ArrayList, uses a HashSet to reject duplicate songs, sorts with comparator chaining, and keeps the three most recently played songs in an ArrayDeque.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Playlist {
record Song(String title, String artist, int plays) { }
private final List<Song> songs = new ArrayList<>();
private final Set<String> titles = new HashSet<>();
private final Deque<String> recent = new ArrayDeque<>();
boolean add(Song s) {
if (!titles.add(s.title())) {
return false;
}
songs.add(s);
return true;
}
void play(String title) {
recent.remove(title);
recent.offerFirst(title);
if (recent.size() > 3) {
recent.pollLast();
}
}
public static void main(String[] args) {
Playlist p = new Playlist();
p.add(new Song("Sunrise", "Navika", 120));
p.add(new Song("Rainfall", "Srihitha", 300));
p.add(new Song("Echoes", "Advitha", 120));
p.add(new Song("Horizon", "Navika", 300));
System.out.println("Add duplicate Sunrise? "
+ p.add(new Song("Sunrise", "Advitha", 5)));
p.songs.sort(Comparator.comparingInt(Song::plays).reversed()
.thenComparing(Song::title));
for (Song s : p.songs) {
System.out.println(s.plays() + " " + s.title()
+ " by " + s.artist());
}
for (String t : List.of("Echoes", "Sunrise", "Horizon",
"Echoes", "Rainfall")) {
p.play(t);
}
System.out.println("Recently played: " + p.recent);
}
}Add duplicate Sunrise? false
300 Horizon by Navika
300 Rainfall by Srihitha
120 Echoes by Advitha
120 Sunrise by Navika
Recently played: [Rainfall, Echoes, Horizon]Explanation:
titles.addreturnsfalsefor a title already seen, so the second "Sunrise" is rejected.- The comparator sorts by plays from highest to lowest, then by title for ties.
playremoves a title if it is already in the deque, adds it at the front, and drops the oldest from the back when there are more than three. That's why Echoes, played twice, appears once, in second place.
Common Mistakes
Adding null to an ArrayDeque. It throws NullPointerException.
Mixing up ends: using offerFirst with pollFirst gives a stack, not a queue.
Expecting ArrayDeque to be thread-safe. Use ConcurrentLinkedDeque or LinkedBlockingDeque for threads.
Practice
- Easy: Check whether a word is a palindrome by putting its letters in a deque and comparing
pollFirstwithpollLast. - Harder: Extend the playlist with a
skip()method that moves the current front song of a play queue (anArrayDeque<Song>) to the back.
Key Takeaways
Was this tutorial helpful?