What is a Java deque?
Java deques (pronounced “decks”) are data structures that extend the concept of Java queues, giving you more functionality and flexibility. But what is a Java deque exactly, and how do Java deques work?
What are Java deques?
Queues are an abstract data type in which elements are stored in FIFO (first in, first out) order. Think of queues as simulating the process of waiting in line: new arrivals go to the end of the line, and people at the front don’t have to wait as long as people in the back.
The deque, which is short for “double-ended queue,” combines the concept of the queue with the stack, another fundamental data structure in which elements are stored in LIFO (last in, first out) order. Like queues, deques have both a head and a tail, and elements are maintained in a sequential order. However, deques allow you to insert and remove elements from both the head and the tail—unlike queues, which have a defined order based on when each element arrived. Note that whether you remove elements from the head or tail of the deque, there is still no easy way to access elements in the middle of the data structure.
Java deques are implementations of the deque data structure for the Java programming language. Deques are implemented in the java.util.Deque interface. Because you can use deques as either a queue or a stack (or both at the same time), they offer more flexibility and a wider range of use cases.
How do Java deques work?
Like queues, Java deques can store any type of element—integers, strings, objects, and much more. The java.util.Deque interface defines the methods that must be part of any class that implements the interface. Below are some of the most important methods of Java deques:
- addFirst(): Inserts an element at the head of the deque.
- addLast(): Inserts an element at the tail of the deque.
- contains(): Returns a Boolean value based on whether the deque contains the given element.
- peekFirst(): Looks at the element at the head of the deque without removing it.
- peekLast(): Looks at the element at the tail of the deque without removing it.
- pollFirst(): Retrieves and removes the element at the head of the deque.
- pollLast(): Retrieves and removes the element at the tail of the deque.
- size(): Returns the number of elements in the deque.
Java deques also include methods inherited from queues, such as add(), peek(), and poll(). These methods operate on the elements at the head of the deque, which makes them equivalent to methods such as addFirst(), peekFirst(), and pollFirst().
Because java.util.Deque is only an interface, it cannot be instantiated directly in Java. Instead, users need to instantiate one of the classes that implement the Deque interface, such as ArrayDeque, ConcurrentLinkedDeque, and LinkedBlockingDeque. The differences between these classes is as follows:
- ArrayDeque: The ArrayDeque is a basic Java deque implementation using Java resizable arrays; it is not thread-safe.
- ConcurrentLinkedDeque: The ConcurrentLinkedDeque is a Java deque implementation using a linked list that supports access, insertion, and removal across multiple threads.
- LinkedBlockingDeque: When a thread performs an unexpected operation, such as removing from an empty deque or adding to a full deque, the blocking deque blocks the thread until the operation can continue (i.e. an element arrives in the deque, or the deque is no longer full).
Java deques in Redis
Redis is an open-source, in-memory data structure store that is widely used for applications such as NoSQL key-value databases, caches, and message brokers. According to Stack Overflow’s 2020 survey, Redis is the “most loved” database technology among developers.
Redis isn’t automatically compatible with programming languages such as Java out of the box. This means that Java developers in Redis don’t have access to the language’s rich standard library, including useful data structures such as deques.
The good news is that you can get access to deques and many other Java objects and collections by installing a third-party Redis Java client such as Redisson. Redisson implements the deque data structure using the RDeque interface. Below is an example of how to use Java deques in Redis with Redisson:
RDeque<SomeObject> queue = redisson.getDeque("anyDeque");
queue.addFirst(new SomeObject());
queue.addLast(new SomeObject());
SomeObject obj = queue.removeFirst();
SomeObject someObj = queue.removeLast();