Deque in Java

The Deque interface, a subtype of the java.util package's Queue interface, introduces a versatile double-ended queue supporting element addition and removal from both ends. It serves as a flexible data structure, applicable as a queue (first-in-first-out/FIFO) or a stack (last-in-first-out/LIFO). As part of the Java Collections Framework, the Deque interface enriches the language with a generic tool for implementing diverse algorithms and data structures. Deque, short for "double-ended queue," is aptly named, reflecting its capacity to operate seamlessly as a stack or queue, accommodating both Last In First Out (LIFO) and First In First Out (FIFO) operations.

Deque Interface

Deque in Java is an interface, and it belongs to the java.util package. It is a subtype of the Queue interface. Deque stands for double-ended queue because it allows retrieval, addition, and removal from both ends. Hence it can be used as a Stack (Last-In-First-Out) or a Queue (First-In-First-Out). Deque in Java is an extension of the Queue interface.

Syntax:

Deque extends the Queue interface, allowing addition to the end and removal from the front. Queue extends Collection interface. The Collection interface extends the Iterable interface, making all the collections iterable.

Declaration:

Example

Now let's apply Deque in Palindrome Checker. A palindrome is a sequence of characters that reads the same forward or backward. The characters are first added to the deque, and the characters from the front and the rear are repeatedly removed and compared to see if they are equal. If they are not equal, it is not a palindrome. If they are equal for all iterations, it is a palindrome.

Output:

Explanation:

1. We first initialized the deque with the characters of the string.
2. We repeatedly remove and compare the first and last values of the deque and check if they are equal.
3. If they are not equal, we return false; we repeat step 2 until the deque has more than one value.

Creating Deque Objects

A Deque in Java can be created by creating objects of the classes that implement the Deque interface. ArrayDeque and LinkedList are the commonly used Deque implementations.

Example:

When we create Deque objects, we can specify the type of objects that can be stored in the deque. This type of restriction can be achieved by the Generics concept in Java.

Example

• Deque<Integer> - Stores only Integer values.
• Deque<Student> - Stores only Student objects.
• Deque<Object> - Stores any objects.

Methods of Deque Interface

Deque in Java offers several methods to add, remove and retrieve elements from the Deque.

Add Elements

add()

The add() method adds an element to the end of the deque. This method returns true if the element is added to the deque and throws an exception if the element cannot be added to the deque.

Output

addFirst()

The addFirst() method adds elements to the beginning of deque. This method returns true if the element is added to the deque and throws an exception if the element cannot be added to the deque.

Output

addLast()

The addLast() method adds elements to the end of the deque. This method returns true if the element is added to the deque and throws an exception if the element cannot be added to the deque. This method is equivalent to the add() method.

Output

offer()

The offer() method adds an element to the end of the deque. This method returns true if the element is added to the deque and false if the element cannot be added to the deque.

Output

offerFirst()

The offerFirst() method adds an element to the end of the deque. This method returns true if the element is added to the deque and false if the element cannot be added to the deque.

Output

offerLast()

The offerLast() method adds an element to the end of the deque. This method returns true if the element is added to the end of the deque and false if the element cannot be added to the deque.

Output

push()

The push() method adds elements to the beginning of deque. This method doesn't return any value if the element is added to the deque and throws an exception when the element cannot be added to the deque.

Output

Remove Elements

pop()

The pop() method removes and returns the first element of the deque. This method throws an exception if the deque is empty. This method internally called the removeFirst() method, which we will see shortly.

Output

remove()

The remove() method removes and returns the first element of the deque. This method throws an exception if the deque is empty. This method is internally called the removeFirst() method.

Output

removeFirst()

The removeFirst() method removes and returns the first element of the deque. This method throws an exception if the deque is empty.

Output

removeLast()

The removeLast() method removes and returns the last element of the deque. This method throws an exception if the deque is empty.

Output

poll()

The poll() method removes and returns the first element of the deque. This method returns null if the deque is empty.

Output

pollFirst()

The pollFirst() method removes and returns the first element of the deque. This method returns null if the deque is empty.

Output

pollLast()

The pollLast() method removes and returns the last element of the deque. This method returns null if the deque is empty.

Output

removeFirstOccurrence()

The removeFirstOccurrence() method removes the first occurrence of the given element at the front from the deque. This method returns true if the element is removed from the deque and false if the element is not removed from the deque.

Output

Explanation

In this example, removeFirstOccurrence(2) removed the first occurrence of 2, at index 1.

removeLastOccurrence()

The removeLastOccurrence() method removes the last occurrence of the given element from the deque. This method returns true if the element is removed from the deque and false if the element is not removed from the deque.

Output

Explanation

In this example, removeLastOccurrence(2) removed the last occurrence of 2, which is at index 4.

Peek Elements

peek()

The peak() method returns the first element of the deque without removing it. This method returns null if the deque is empty.

Output

peekFirst()

The peakFirst() method returns the first element of the deque without removing it. It is equivalent to the peak() method. This method returns null if the deque is empty.

Output

peekLast()

The peakLast() method returns the last element of the deque without removing it. This method returns null if the deque is empty.

Output

getFirst()

The getFirst() method returns the first element of the deque without removing it. This method throws an exception if the deque is empty.

Output

getLast()

The getLast() method returns the last element of the deque without removing it. This method throws an exception if the deque is empty.

Output

Operations Using Deque Interface and ArrayDeque Class

Adding Elements

Values are added to the deque using add(), addFirst(), addLast(), offer(), offerFirst(), or offerLast() method. The working of these methods is explained later in detail.

Output

Explanation

All the methods in this example adds a value to the deque. add(), addLast(), offer(), and offerLast() adds value to the end of the deque. addFirst(), offerFirst(), and push() adds value to the beginning of the deque.

Removing Elements

Values are removed from the deque using poll(), pollFirst(), pollLast(), pop(), remove(), removeFirst(), or removeLast() method. The working of these methods is explained later in detail.

Output

Explanation

All the methods in this example removes a value from the deque. poll(), pollFirst(), pop(), remove() and removeFirst() removes value from the beginning of the deque. pollLast() and removeLast() removes value from the end of the deque.

Iterating through the Deque

Deque provides iterator() and descendingIterator() methods which can be used to iterate deque in forward and reverse order, respectively. Deque can also be iterator by the Java for-each loop

Syntax

deque.iterator() - Iterates a deque from front to end.

deque.descendingIterator() - Iterates a deque from end to front.

Example

Output

Explanation

1. We used the for-each iterator to traverse and print the values of the deque. This is similar to iterating other linear data structures like list, array, etc.
2. Deque provides an Iterator object via deque.iterator() that can be used to iterate the deque in the forward direction. The values are accessed via iterator.next().
3. Deque provides a descending Iterator object via deque.descendingIterator() that can be used to iterate the deque in the reverse direction. The values are accessed via iterator.next().

Classes that Implement Deque

Deque in Java is an interface and cannot be instantiated because it only provides method declarations, not implementations. Concrete implementation has to be provided for the Deque interface to instantiate it. The classes that implement the Deque interface are

• ArrayDeque
• LinkedList
• ConcurrentLinkedDeque
• LinkedBlockingDeque

Let us discuss each of these in detail.

ArrayDeque

ArrayDeque is a deque implementation in Java that belongs to the java.util package. It is the resizeable array implementation of the Deque interface. It internally uses an array to store the elements.

ArrayDeque doesn't have any capacity constraints and grows based on the requirement. null values cannot be stored in an ArrayDeque. The initial capacity of an ArrayDeque object is 16.

Syntax

ArrayDeque<T>(): Creates an empty deque with the initial capacity of 16.

ArrayDeque<T>(int initialCapacity) - Creates an empty deque with the capacity provided via initialCapacity.

ArrayDeque<T>(Collection collection) - Creates a deque with the elements present in the collection.

LinkedList

LinkedList is a deque implementation in Java that belongs to the java.util package. It uses a doubly linked list to store the elements. The elements are stored in nodes and linked together via pointers i.e the address of the next node will be stored in the previous node. LinkedList doesn't require the size to be specified while creating. The size of the list is automatically increased or decreased when an element is added or removed respectively.

Syntax

LinkedList<T>(): Creates a empty list without any values in it.

LinkedList<T>(Collection collection): Creates a list with the values of the collection passed as the parameter.

ConcurrentLinkedDeque

ConcurrentLinkedDeque is a deque implementation in Java that belongs to java.util.concurrent package. It doesn't allow null values to be stored. It is a thread-safe deque and allows multiple threads to add or remove elements from the deque concurrently. It is the best choice when multiple threads perform concurrent insertion and removal operations on the deque.

Syntax

ConcurrentLinkedDeque<T>(): Creates an empty deque.

ConcurrentLinkedDeque<T>(Collection collection): Creates a deque with the elements of the collection passed as the parameter.

Why is ConcurrentLinkedDeque thread-safe and ArrayDeque is not?

In ArrayDeque while one thread is iterating the deque, if the other thread tries to add or remove an element, we get ConcurrentModificationException. It is because ArrayDeque does not support synchronized access to the deque from multiple threads.

In ConcurrentLinkedDeque we don't get ConcurrentModificationException when one thread iterates the deque and the other thread tries to add or remove an element. It is because ConcurrentLinkedDeque provides internal synchronization support in multiple threads environment.

LinkedBlockingDeque

LinkedBlockingDeque is a deque implementation in Java that belongs to java.util.concurrent package. It has an initial capacity of Integer.MAX_VALUE. It doesn't allow null values to be stored. It blocks the threads when operations cannot be performed on the deque.

Example

• Block a thread that tries to remove an element from an empty deque. The thread will be blocked until there is at least one element in the deque.
• Block a thread that tries to add an element to a full deque. The thread will be blocked until there is at least one space left in the deque.

Syntax

LinkedBlockingDeque<T>(): Creates an empty deque with an initial capacity of Integer.MAX_VALUE

LinkedBlockingDeque<T>(int initialCapacity): Creates an empty deque with the capacity provided via initialCapacity.

LinkedBlockingDeque<T>(Collection collection) - Creates a deque with the elements of collection passed as the parameter.

ArrayDeque vs LinkedList

LinkedList class stores every element as a Node object connected via pointers. So, the LinkedList class has an additional overhead of creating new Node objects when an element is added and has a performance impact. This overhead is not present in ArrayDeque as it stores elements in a circular array. Hence, ArrayDeque is better than LinkedList.