What is Deque in Java: Complete Guide with Implementation Examples

Introduction

In Java programming, managing data from both ends of a queue can be extremely useful—especially in scenarios like undo operations, palindrome checking, or implementing caching systems. That’s where the Deque (Double-Ended Queue) comes in.

A Deque allows you to insert and remove elements from both the front and the back, making it more flexible than standard queues. It is part of Java’s collection framework and is widely used in real-world applications that require efficient and dynamic data handling.

In this blog, we’ll explore what a Deque is, its key features, different implementations like ArrayDeque and LinkedList, and how to use it effectively with real Java code examples.

To better grasp these concepts and write clean, efficient code, enroll in top software engineering courses online.

Understanding Deque in Java

Deque stands for "Double Ended Queue," which allows you to add and remove elements from both the front and the end of the queue. This flexibility makes it a powerful data structure for various algorithms and programming scenarios.

Key Characteristics of Deque in Java:

1. Double-ended: Elements can be added or removed from both ends
2. Interface: Deque is an interface in the Java Collections Framework
3. Extends Queue: Deque extends the Queue interface
4. Multiple Implementations: Available as ArrayDeque, LinkedList, and more
5. Null Elements: Some implementations allow null elements, others don't
6. Thread Safety: Not thread-safe by default, but has thread-safe implementations
7. Versatile: Can function as a stack, queue, or both simultaneously

Advance your career with these proven skill-building programs.

• upGrad’s AI-Powered Full Stack Development Course by IIITB 
• upGrad’s Professional Certificate Program in Cloud Computing and DevOps 
• upGrad’s Master of Design in User Experience

Deque Operations in Java

The Deque interface provides methods for inserting, removing, and examining elements at both the head and tail of the queue:

Core Operations for First (Head) Element:

Core Operations for Last (Tail) Element:

Deque as a Queue (FIFO):

Deque as a Stack (LIFO):

Implementations of Deque in Java

Java programming provides several implementations of the Deque interface, each with its own characteristics:

1. ArrayDeque

ArrayDeque is a resizable array implementation of the Deque interface. It's the most commonly used implementation when you need a double-ended queue.

Key Features:

• Faster than LinkedList for most operations
• No capacity restrictions
• Not thread-safe
• Doesn't allow null elements
• Ideal for stack or queue implementations

2. LinkedList

LinkedList implements both List and Deque interfaces, providing the capabilities of both a linked list and a double-ended queue.

Key Features:

• Allows null elements
• Not thread-safe
• Better performance for frequent insertions/removals in the middle
• Uses more memory than ArrayDeque

3. ConcurrentLinkedDeque

A thread-safe variant that implements the Deque interface.

Key Features:

• Thread-safe operations without synchronization
• Non-blocking algorithm
• Suitable for concurrent applications
• Higher overhead compared to non-concurrent implementations

Example 1: Basic Deque Operations with ArrayDeque

import java.util.ArrayDeque;
import java.util.Deque;

public class BasicDequeOperations {
    public static void main(String[] args) {
        // Create an ArrayDeque implementation
        Deque<String> deque = new ArrayDeque<>();
        
        // Adding elements to both ends
        deque.addFirst("First");
        deque.addLast("Last");
        
        // Adding more elements
        deque.offerFirst("New First");
        deque.offerLast("New Last");
        
        System.out.println("Deque contents: " + deque);
        
        // Examining elements without removal
        System.out.println("First element: " + deque.peekFirst());
        System.out.println("Last element: " + deque.peekLast());
        
        // Removing elements
        System.out.println("Removed first: " + deque.removeFirst());
        System.out.println("Removed last: " + deque.removeLast());
        
        System.out.println("Updated deque: " + deque);
        
        // Using poll methods
        System.out.println("Polled first: " + deque.pollFirst());
        System.out.println("Polled last: " + deque.pollLast());
        
        System.out.println("Final deque: " + deque);
    }
}

Output:

Deque contents: [New First, First, Last, New Last]

First element: New First

Last element: New Last

Removed first: New First

Removed last: New Last

Updated deque: [First, Last]

Polled first: First

Polled last: Last

Final deque: []

This example demonstrates the basic operations of adding, examining, and removing elements from both ends of a Deque using ArrayDeque implementation.

Example 2: Using Deque as a Stack

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeAsStack {
    public static void main(String[] args) {
        // Create a Deque to be used as a stack
        Deque<Integer> stack = new ArrayDeque<>();
        
        // Push elements onto the stack
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        
        System.out.println("Stack: " + stack);
        
        // Peek at the top element
        System.out.println("Top element: " + stack.peek());
        
        // Pop elements from the stack
        System.out.println("Popping elements:");
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

Output:

Stack: [40, 30, 20, 10]

Top element: 40

Popping elements:

40

30

20

10

This example shows how to use a Deque as a stack with Last-In-First-Out (LIFO) behavior using push(), pop(), and peek() operations.

Example 3: Using Deque as a Queue

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeAsQueue {
    public static void main(String[] args) {
        // Create a Deque to be used as a queue
        Deque<String> queue = new ArrayDeque<>();
        
        // Add elements to the queue
        queue.add("Customer 1");
        queue.add("Customer 2");
        queue.add("Customer 3");
        queue.add("Customer 4");
        
        System.out.println("Queue: " + queue);
        
        // Peek at the first element
        System.out.println("First in queue: " + queue.peek());
        
        // Process the queue (FIFO)
        System.out.println("Processing queue:");
        while (!queue.isEmpty()) {
            System.out.println("Serving: " + queue.remove());
        }
    }
}

Output:

Queue: [Customer 1, Customer 2, Customer 3, Customer 4]

First in queue: Customer 1

Processing queue:

Serving: Customer 1

Serving: Customer 2

Serving: Customer 3

Serving: Customer 4

This example demonstrates using a Deque as a regular queue with First-In-First-Out (FIFO) behavior using add(), remove(), and peek() operations.

Example 4: Implementing a Palindrome Checker with Deque

import java.util.ArrayDeque;
import java.util.Deque;

public class PalindromeChecker {
    public static boolean isPalindrome(String str) {
        // Remove non-alphanumeric characters and convert to lowercase
        String cleanStr = str.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        
        // Create a deque and fill it with characters
        Deque<Character> deque = new ArrayDeque<>();
        for (char c : cleanStr.toCharArray()) {
            deque.add(c);
        }
        
        // Compare characters from both ends
        while (deque.size() > 1) {
            if (!deque.removeFirst().equals(deque.removeLast())) {
                return false;
            }
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        String[] testStrings = {
            "racecar",
            "A man, a plan, a canal: Panama",
            "hello",
            "Madam, I'm Adam",
            "Java"
        };
        
        for (String str : testStrings) {
            System.out.println("\"" + str + "\" is a palindrome: " + isPalindrome(str));
        }
    }
}

Output:

"racecar" is a palindrome: true

"A man, a plan, a canal: Panama" is a palindrome: true

"hello" is a palindrome: false

"Madam, I'm Adam" is a palindrome: true

"Java" is a palindrome: false

This example demonstrates a practical application of Deque to check whether a string is a palindrome (reads the same backward as forward) by comparing characters from both ends simultaneously.

Performance Comparison of Deque Implementations

When choosing a Deque implementation, consider the performance characteristics:

In most cases, ArrayDeque offers better performance and lower memory overhead compared to LinkedList, unless you need frequent insertions or removals in the middle of the list.

Common Use Cases for Deque in Java

Deques are versatile data structures suitable for numerous applications:

1. Work Stealing Algorithms: Tasks can be taken from either end of the queue
2. Browser History: Implementing forward and backward navigation
3. Undo/Redo Functionality: Managing operations that can be undone or redone
4. Palindrome Checking: Comparing characters from both ends
5. Sliding Window Problems: Maintaining a window of elements
6. Task Scheduling: Priority-based task management
7. BFS Algorithm Implementation: Level-order traversal of trees
8. Expression Evaluation: Parsing and evaluating expressions

Iterating Through a Deque

There are multiple ways to iterate through a Deque:

Using Iterator

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

public class DequeIteration {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.add("One");
        deque.add("Two");
        deque.add("Three");
        
        System.out.println("Iterating using Iterator:");
        Iterator<String> iterator = deque.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        
        System.out.println("\nIterating using enhanced for loop:");
        for (String element : deque) {
            System.out.println(element);
        }
        
        System.out.println("\nIterating using forEach method:");
        deque.forEach(System.out::println);
    }
}

Output:

Iterating using Iterator:

One

Two

Three

Iterating using enhanced for loop:

One

Two

Three

Iterating using forEach method:

One

Two

Three

Thread Safety with Deque

Standard Deque implementations like ArrayDeque and LinkedList are not thread-safe. For concurrent applications, consider:

1. ConcurrentLinkedDeque: A thread-safe implementation for concurrent access
2. Collections.synchronizedDeque(): Creates a synchronized (thread-safe) Deque
3. BlockingDeque: Interface that extends Deque with blocking operations

Deque vs. Other Collection Types

Understanding how Deque compares to other collections helps choose the right data structure:

Conclusion

Deque in Java provides a versatile and powerful data structure that can be used as both a stack and a queue, offering efficient operations for adding and removing elements at both ends. With multiple implementations available, you can choose the one that best fits your specific requirements for performance, memory usage, and thread safety.

By understanding what Deque in Java is, how it works, and when to use it, you can leverage this collection to solve a wide range of programming problems more efficiently. Whether you're implementing complex algorithms, managing browser history, or processing tasks in a specific order, the Deque interface provides the flexibility and performance you need.

FAQ

1. What is the difference between Queue and Deque in Java?

A Queue in Java is a First-In-First-Out (FIFO) data structure where elements are added at the rear and removed from the front. A Deque (Double-Ended Queue) extends this functionality by allowing elements to be added or removed from both ends. Deque supports all Queue operations plus additional methods for working with both ends of the queue.

2. When should I use ArrayDeque vs. LinkedList?

Use ArrayDeque for most cases as it provides better overall performance and lower memory overhead. Choose LinkedList when you need frequent insertions or removals from the middle of the list, or if you need to utilize both List and Deque functionalities. ArrayDeque doesn't allow null elements, while LinkedList does.

3. Is Deque thread-safe in Java?

The standard Deque implementations (ArrayDeque, LinkedList) are not thread-safe. For thread-safe operations, use ConcurrentLinkedDeque, or wrap a Deque implementation with Collections.synchronizedDeque(). Always consider the performance implications of synchronized collections in high-concurrency environments.

4. Can Deque contain duplicate elements?

Yes, all standard Deque implementations in Java allow duplicate elements. Elements are ordered based on insertion order, not by their values.

5. What's faster: using Deque as a stack or java.util.Stack?

Using ArrayDeque as a stack is generally faster than using java.util.Stack. The Stack class extends Vector, which is synchronized and has performance overhead. ArrayDeque provides better performance for stack operations and is the recommended approach since Java 6.

6. What happens when I call removeFirst() on an empty Deque?

Calling removeFirst() on an empty Deque throws a NoSuchElementException. If you want to avoid exceptions, use pollFirst() instead, which returns null when the Deque is empty.

7. Can I use Deque for implementing a priority queue?

Deque is not designed for priority-based ordering. For priority queue functionality, use the PriorityQueue class or PriorityBlockingQueue for thread-safe operations.

8. How can I convert a Deque to an array?

You can convert a Deque to an array using the toArray() method:

Deque<String> deque = new ArrayDeque<>();
// Add elements...
String[] array = deque.toArray(new String[0]);

9. Can I sort elements in a Deque?

Deque doesn't provide direct sorting methods. To sort elements, you can convert the Deque to a List, sort the List, and then create a new Deque from the sorted List:

Deque<Integer> deque = new ArrayDeque<>();
// Add elements...
List<Integer> list = new ArrayList<>(deque);
Collections.sort(list);
deque = new ArrayDeque<>(list);

10. How does Deque handle capacity and resizing?

ArrayDeque starts with an initial capacity (16 by default) and automatically resizes when needed. The capacity is always a power of 2, which optimizes array-based operations. LinkedList doesn't have capacity constraints as it uses linked nodes.

11. Can I make a fixed-size Deque?

Standard Deque implementations don't support fixed size directly. You can create wrapper classes to enforce size limits, or use specialized implementations like CircularFifoQueue from Apache Commons Collections.

Take the Free Quiz on Java

Answer quick questions and assess your Java knowledge

Start Quiz