What Is Deque Data Structure in Java?

Deque, short for double-ended queue, is a data structure in Java that allows insertion and removal of elements from both ends. It is an implementation of the Queue interface that supports operations at both the head and the tail of the queue.

The Deque Interface

In Java, the Deque interface is available in the java.util package. It extends the Queue interface and provides additional methods for inserting and removing elements at both ends.

The Deque interface is implemented by several classes in Java, such as ArrayDeque and LinkedList. These classes provide different implementations of a double-ended queue based on different underlying data structures.

Creating a Deque Object

To create a Deque object in Java, you can simply instantiate one of the implementing classes:

Deque<String> deque = new ArrayDeque<>();

This creates a new empty deque that can hold elements of type String. You can replace String with any other data type or use custom objects as well.

Operations on a Deque

Once you have created a Deque object, you can perform various operations on it:

• Adding Elements:

You can add elements to both ends of the deque using methods such as addFirst(), addLast(), or offerFirst(), offerLast(). For example:

  deque.addFirst("First");
  deque.addLast("Last");
  

• Removing Elements:

You can remove elements from both ends using methods like removeFirst(), removeLast(), or pollFirst(), pollLast().

For example:

  String firstElement = deque.removeFirst();
  String lastElement = deque.removeLast();
  

• Accessing Elements:

You can access the first and last elements of the deque without removing them using methods like getFirst(), getLast(), or peekFirst(), peekLast(). For example:

  String firstElement = deque.getFirst();
  String lastElement = deque.getLast();
  

• Checking Size and Emptyness:

You can check the size of the deque using the size() method and determine if it is empty using the isEmpty() method.

Usage Example

The following example demonstrates how to use a Deque to implement a simple task scheduler:

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

public class TaskScheduler {
    private Deque<String> tasks;

    public TaskScheduler() {
        tasks = new ArrayDeque<>();
    }

    public void addTask(String task) {
        tasks.addLast(task);
        System.out.println("Task added: " + task);
    }

    public void executeTasks() {
        while (!tasks.isEmpty()) {
            String task = tasks.removeFirst();
            System.println("Executing task: " + task);
        }
    }

    public static void main(String[] args) {
        TaskScheduler scheduler = new TaskScheduler();
        scheduler.addTask("Task 1");
        scheduler.addTask("Task 2");
        scheduler.addTask("Task 3");
        scheduler.executeTasks();
    }
}

In this example, the TaskScheduler class uses a Deque to store and execute tasks in the order they were added. The addTask() method adds tasks to the end of the deque using addLast(), and the executeTasks() method removes tasks from the front of the deque using removeFirst().

Conclusion

The Deque data structure in Java provides a convenient way to implement double-ended queues. It allows insertion and removal of elements at both ends efficiently. By using Deque, you can easily handle scenarios where elements need to be added or removed from the front or back of a queue-like structure.

Remember to choose the appropriate implementing class based on your specific requirements and consider factors such as performance and memory usage.