Deque Interface
What if your application needs a queue where elements can be added or removed from both ends? A normal Queue primarily focuses on processing from one end, but many real-world problems need more flexibility.
This is where the Deque interface comes in. Deque stands for Double-Ended Queue. It supports insertion, removal, and inspection at both the front and the rear of the collection.
Core Idea: A Deque gives you two working ends. You can use it as a traditional Queue or as a Stack.
Why Does the Deque Interface Exist?
Imagine a browser history system. You may want to add a page to the end, remove the oldest page from the front, or occasionally process the most recently added page first. A double-ended structure makes these operations natural.
Another example is a task scheduler where urgent tasks can be inserted at the front while normal tasks are added at the rear.
Deque<String> tasks = new ArrayDeque<>();
tasks.addLast("Normal Task");
tasks.addLast("Another Task");
tasks.addFirst("Urgent Task");
System.out.println(tasks);
The important idea is that the application can control both ends without needing a separate data structure.
Think of Deque as a two-door waiting line: people can enter or leave from either the front door or the back door.
Deque Interface Hierarchy
Deque extends the Queue interface, which itself extends Collection.
Collection
|
+-- Queue
|
+-- Deque
|
+-- ArrayDeque
+-- LinkedList
This relationship is important because a Deque can be used wherever Queue behavior is expected, while also providing additional operations for the opposite end.
Creating a Deque
The most common general-purpose implementation is ArrayDeque.
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> tasks = new ArrayDeque<>();
tasks.addLast("Task 1");
tasks.addLast("Task 2");
tasks.addLast("Task 3");
System.out.println(tasks);
}
}
Here, Deque<String> is the interface and ArrayDeque<String> is the implementation.
Best practice: Declare the variable using the Deque interface when your code only needs Deque behavior.
Adding Elements at Both Ends
Deque provides methods specifically for adding elements at the front and rear.
Deque<String> languages = new ArrayDeque<>();
languages.addLast("Java");
languages.addLast("Spring");
// Add an element at the front.
languages.addFirst("Programming");
System.out.println(languages);
After these operations, Programming is at the front, while Java and Spring remain toward the rear.
addFirst() and addLast()
| Method | Purpose |
|---|---|
| addFirst() | Adds an element at the front. |
| addLast() | Adds an element at the rear. |
Deque also provides offerFirst() and offerLast(), which follow the Queue-style special-value failure behavior.
Deque<String> tasks = new ArrayDeque<>();
tasks.offerFirst("Urgent Task");
tasks.offerLast("Normal Task");
System.out.println(tasks);
Removing Elements from Both Ends
A Deque can remove elements from either end.
Deque<String> tasks = new ArrayDeque<>();
tasks.addLast("Task 1");
tasks.addLast("Task 2");
tasks.addLast("Task 3");
String first = tasks.removeFirst();
String last = tasks.removeLast();
System.out.println(first);
System.out.println(last);
| Method | Purpose |
|---|---|
| removeFirst() | Removes and returns the first element. |
| removeLast() | Removes and returns the last element. |
| pollFirst() | Removes and returns the first element, or returns null if empty. |
| pollLast() | Removes and returns the last element, or returns null if empty. |
Boundary Behavior: removeFirst()/removeLast() use exception-based behavior for an empty Deque, while pollFirst()/pollLast() return null when no element is available.
Inspecting Both Ends
You can inspect either end without removing an element.
Deque<String> tasks = new ArrayDeque<>();
tasks.addLast("Task 1");
tasks.addLast("Task 2");
tasks.addLast("Task 3");
System.out.println(tasks.peekFirst());
System.out.println(tasks.peekLast());
| Method | Purpose | Empty Deque |
|---|---|---|
| getFirst() | Returns the first element without removing it. | Throws an exception. |
| getLast() | Returns the last element without removing it. | Throws an exception. |
| peekFirst() | Returns the first element without removing it. | Returns null. |
| peekLast() | Returns the last element without removing it. | Returns null. |
The Deque Method Families
Deque has many methods, but they become easy to understand when grouped by the end they operate on and their failure behavior.
| Operation | Front | Rear |
|---|---|---|
| Insert, exception-based | addFirst() | addLast() |
| Insert, special-value based | offerFirst() | offerLast() |
| Remove, exception-based | removeFirst() | removeLast() |
| Remove, special-value based | pollFirst() | pollLast() |
| Inspect, exception-based | getFirst() | getLast() |
| Inspect, special-value based | peekFirst() | peekLast() |
Memory Pattern: First and Last tell you which end. Add/Offer insert, Remove/Poll remove, and Get/Peek inspect.
Using Deque as a Queue
Because Deque extends Queue, you can use it with standard Queue methods.
Deque<String> tasks = new ArrayDeque<>();
tasks.offer("Task 1");
tasks.offer("Task 2");
tasks.offer("Task 3");
System.out.println(tasks.peek());
System.out.println(tasks.poll());
These methods treat the Deque like a traditional FIFO queue. Elements are added at the rear and processed from the front.
Using Deque as a Stack
Deque becomes even more interesting when used as a stack. A stack follows LIFO, meaning Last In, First Out.
Deque<String> stack = new ArrayDeque<>();
stack.push("Page 1");
stack.push("Page 2");
stack.push("Page 3");
System.out.println(stack.pop());
The last value pushed, Page 3, is the first value removed.
Modern Java Practice: When you need stack behavior, Deque with ArrayDeque is generally preferred over the legacy Stack class.
Queue Behavior vs Stack Behavior
| Behavior | Insertion | Removal | Ordering |
|---|---|---|---|
| Queue | Rear | Front | FIFO |
| Stack using Deque | Front | Front | LIFO |
The same Deque implementation can support both models. The difference comes from which operations you choose.
ArrayDeque
ArrayDeque is a resizable-array implementation of Deque. It is designed for efficient operations at both ends and is commonly used for stack and queue use cases.
Deque<Integer> numbers = new ArrayDeque<>(); numbers.addFirst(20); numbers.addFirst(10); numbers.addLast(30); System.out.println(numbers);
ArrayDeque does not permit null elements. This restriction helps avoid ambiguity because methods such as poll() and peek() use null to indicate that no element is available.
LinkedList as a Deque
LinkedList also implements Deque, so it can perform double-ended operations.
Deque<String> messages = new LinkedList<>();
messages.addFirst("First");
messages.addLast("Last");
System.out.println(messages);
Although LinkedList supports Deque behavior, ArrayDeque is often the better default for dedicated queue/deque use cases because it avoids the per-node overhead associated with a linked structure.
ArrayDeque vs LinkedList
| Aspect | ArrayDeque | LinkedList |
|---|---|---|
| Structure | Resizable array | Doubly linked nodes |
| Deque operations | Efficient at both ends | Efficient at both ends |
| Null elements | Not permitted | Permitted |
| Memory overhead | Generally lower | Generally higher |
| Typical dedicated Deque choice | Strong default | Useful when its List capabilities are also relevant |
Removing the First Occurrence
Deque also provides methods for removing the first or last occurrence of a matching value.
Deque<String> values = new ArrayDeque<>();
values.addLast("Java");
values.addLast("Spring");
values.addLast("Java");
values.addLast("SQL");
values.removeFirstOccurrence("Java");
System.out.println(values);
Only the first matching occurrence is removed. The second Java remains in the Deque.
values.removeLastOccurrence("Java");
This removes the last matching occurrence instead.
Iterating Through a Deque
A Deque can be traversed from the front toward the rear using the enhanced for loop.
Deque<String> tasks = new ArrayDeque<>();
tasks.addLast("Task 1");
tasks.addLast("Task 2");
tasks.addLast("Task 3");
for (String task : tasks) {
System.out.println(task);
}
Deque also provides descendingIterator() when you need to traverse from the rear toward the front.
Iterator<String> iterator = tasks.descendingIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
This is useful when the direction of traversal matters.
Real-World Example: Browser Navigation
A simplified navigation system can use a Deque to maintain a sequence of visited pages.
Deque<String> history = new ArrayDeque<>();
history.addLast("Home");
history.addLast("Products");
history.addLast("Details");
// Move backward.
String previousPage = history.removeLast();
System.out.println("Back to: " + previousPage);
A production browser needs much more sophisticated history management, but the example demonstrates why double-ended structures are useful when elements can be processed from either side.
Real-World Example: Sliding Window
Deque is also extremely useful in algorithms that maintain a moving window over data. For example, a system might continuously process the most recent events while discarding old events from the opposite end.
Deque<Integer> window = new ArrayDeque<>(); window.addLast(10); window.addLast(20); window.addLast(30); // Remove the oldest element. window.removeFirst(); // Add the newest element. window.addLast(40); System.out.println(window);
This pattern appears in streaming systems, caching algorithms, rate-limiting logic, and many coding-interview problems.
Deque and Null Values
Not all Deque implementations have the same null policy. In particular, ArrayDeque does not permit null elements.
Deque<String> values = new ArrayDeque<>(); // Null is not permitted. // values.addFirst(null); // NullPointerException
This is worth remembering because methods such as pollFirst() and peekFirst() return null when no element is available.
Deque Does Not Provide Random Access
Deque is optimized around its two ends. It is not intended to replace List for arbitrary index-based access.
Deque<String> tasks = new ArrayDeque<>();
tasks.addLast("Task 1");
tasks.addLast("Task 2");
// Deque does not provide List-style get(index).
// tasks.get(0); // Not available through Deque.
If your application frequently asks for the element at an arbitrary index, a List is usually a better abstraction.
Deque vs Queue vs List
| Feature | List | Queue | Deque |
|---|---|---|---|
| Primary purpose | Ordered sequence | Processing queue | Double-ended processing |
| Index access | Yes | No | No |
| Front operations | Not its primary abstraction | Yes | Yes |
| Rear operations | Possible depending on implementation, but not its core contract | Yes for insertion | Yes |
| Stack behavior | Not its intended abstraction | No | Yes |
| Typical use | Records, items, ordered data | Waiting jobs | Queues, stacks, sliding windows, double-ended processing |
Common Beginner Mistakes
- Thinking Deque means only Queue: Deque extends Queue but adds operations at both ends.
- Using List when only end operations are needed: Deque communicates the required data structure more clearly.
- Using Stack for modern stack implementations: Prefer Deque with ArrayDeque for typical stack behavior.
- Confusing addFirst() with addLast(): Always identify which end your operation should affect.
- Ignoring empty-Deque behavior: remove/get methods throw exceptions, while poll/peek methods return null.
- Adding null to ArrayDeque: ArrayDeque does not permit null elements.
- Expecting index-based access: Deque is designed around its ends, not arbitrary positions.
Best Practices
- Use Deque when elements need to be inserted, removed, or inspected from either end.
- Prefer ArrayDeque for many general-purpose single-threaded Queue and Deque use cases.
- Use Deque with push() and pop() when you need stack behavior.
- Use offerFirst(), offerLast(), pollFirst(), and pollLast() when special-value failure behavior is appropriate.
- Avoid relying on random access; choose List when positional access is a core requirement.
- Remember that ArrayDeque does not permit null elements.
Interview Insights
Question: What does Deque stand for?
Answer: Deque stands for Double-Ended Queue. It allows insertion, removal, and inspection at both the front and rear.
Question: Can Deque be used as a Stack?
Answer: Yes. A Deque supports stack behavior through operations such as push(), pop(), and peek(). ArrayDeque is commonly used for this purpose.
Question: What is the difference between Queue and Deque?
Answer: Queue provides operations centered around a queue's processing order, while Deque extends Queue with operations that allow insertion, removal, and inspection at both ends.
Question: Why is ArrayDeque often preferred over Stack?
Answer: ArrayDeque is a modern general-purpose Deque implementation designed for efficient stack and queue operations, while Stack is a legacy class.
Question: Does ArrayDeque allow null elements?
Answer: No. ArrayDeque does not permit null elements.
Quick Revision
| Concept | Key Point |
|---|---|
| Deque | Double-ended queue that supports operations at both ends. |
| addFirst() | Adds an element at the front. |
| addLast() | Adds an element at the rear. |
| removeFirst() | Removes the first element and throws an exception if empty. |
| removeLast() | Removes the last element and throws an exception if empty. |
| pollFirst() | Removes the first element and returns null if empty. |
| pollLast() | Removes the last element and returns null if empty. |
| peekFirst() | Inspects the first element without removing it. |
| peekLast() | Inspects the last element without removing it. |
| ArrayDeque | Efficient general-purpose Deque implementation that does not permit null elements. |
| Stack behavior | Can be implemented using Deque with push() and pop(). |
The Deque interface is one of those Java concepts that becomes much easier once you stop memorizing individual methods and start thinking in terms of two ends. From FIFO queues to LIFO stacks and sliding-window algorithms, Deque provides a flexible abstraction for problems where data enters and leaves from either side. In the next chapter, we will move from the interfaces into one of the most widely used implementations in Java: ArrayList.