ArrayDeque in Java

A Queue is a simple, linear data structure that allows us to insert elements from one end and remove them from another end. Deque stands for Double-Ended Queue. Unlike a Queue, a Deque can insert and remove elements from either end.

In this tutorial, we will learn how a Deque is implemented in Java with the help of an ArrayDeque class.

Deque Data Structure

As discussed above, a Deque is a linear data structure that allows insertion and deletion from both ends. This is the reason it is called a Double-Ended Queue. We can use this data structure to implement other linear data structures like stacks and queues. We will allow insertion and deletion from just one common end of the Deque to implement a Stack. To implement a Queue using Deque, we will allow insertion from one end and deletion from the other end.

ArrayDeque in Java

• The ArrayDeque class in Java provides a dynamic array that can be used as a Deque. This class implements the Deque and the Queue interface.
• It uses two pointers called head and tail. The head takes care of insertion and deletion from the front, and the tail takes care of insertion and deletion from the end.
• If an element is added at the front, then the head moves forward(from left to right). If an element is removed from the front then the head moves backward.
• If an element is added at the end, then the tail moves from right to left. If an element is removed from the end, then the tail moves forward(left to right).

Let's look at some of the common operations performed on an ArrayDeque.

Insertion (Adding Elements to ArrayDeque)

We can insert elements at the front or the rear of the Deque. ArrayDeque provides the offerFirst() and addFirst() methods to add elements at the front of the ArrayDeque.

import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> deck = new ArrayDeque<Integer>();
	    deck.addFirst(5);
	    deck.addFirst(10);
	    System.out.println("Deque After Inserting using addFirst(): " + deck);
	    
	    deck.offerFirst(15);
	    deck.offerFirst(20);
	    System.out.println("Deque After Inserting using offerFirst(): " + deck);
	}
}

Deque After Inserting using addFirst(): [10, 5]
Deque After Inserting using offerFirst(): [20, 15, 10, 5]

We can use the offerLast() or the addLast() methods to insert elements at the rear of the ArrayDeque.

import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> deck = new ArrayDeque<Integer>();
	    deck.addLast(5);
	    deck.addLast(10);
	    System.out.println("Deque After Inserting using addLast(): " + deck);
	    
	    deck.offerLast(15);
	    deck.offerLast(20);
	    System.out.println("Deque After Inserting using offerLast(): " + deck);
	}
}

Deque After Inserting using addLast(): [5, 10]
Deque After Inserting using offerLast(): [5, 10, 15, 20]

Deletion (Deleting Elements from ArrayDeque)

We have the pollFirst() and the removeFirst() methods that can remove elements from the front of the ArrayDeque that return the element present at the head or the front of the Deque.

import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> deck = new ArrayDeque<Integer>();
	    deck.addLast(5);
	    deck.addLast(10);  
	    deck.addLast(15);
	    deck.addLast(20);
	    System.out.println("Deque After Insertion: " + deck);
	    
	    Integer i1 = deck.removeFirst();
	    System.out.println("Deleted Element: " + i1);
	    System.out.println("Deque after Deletion: " + deck);
	    
	    Integer i2 = deck.pollFirst();
	    System.out.println("Deleted Element: " + i2);
	    System.out.println("Deque after Deletion: " + deck);
	}
}

Deque After Insertion: [5, 10, 15, 20]
Deleted Element: 5
Deque after Deletion: [10, 15, 20]
Deleted Element: 10
Deque after Deletion: [15, 20]

Similarly, the pollLast() and the removeLast() methods are used to remove the last element of the Deque.

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

public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> deck = new ArrayDeque<Integer>();
	    deck.addLast(5);
	    deck.addLast(10);  
	    deck.addLast(15);
	    deck.addLast(20);
	    System.out.println("Deque After Insertion: " + deck);
	    
	    Integer i1 = deck.removeLast();
	    System.out.println("Deleted Element: " + i1);
	    System.out.println("Deque after Deletion: " + deck);
	    
	    Integer i2 = deck.pollLast();
	    System.out.println("Deleted Element: " + i2);
	    System.out.println("Deque after Deletion: " + deck);
	}
}

Deque After Insertion: [5, 10, 15, 20]
Deleted Element: 20
Deque after Deletion: [5, 10, 15]
Deleted Element: 15
Deque after Deletion: [5, 10]

Fetching Elements from ArrayDeque

We can easily fetch the first element from an ArrayDeque by using the peekFirst() or the getFirst() methods. As you may have guessed, we have a peekLast() and a getLast() method to fetch the last element from a Deque.

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

public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> deck = new ArrayDeque<Integer>();
	    deck.addLast(5);
	    deck.addLast(10);  
	    deck.addLast(15);
	    deck.addLast(20);
	    System.out.println("Deque After Insertion: " + deck);
	    
	    Integer i1 = deck.peekFirst();
	    Integer i2 = deck.getFirst();
	    System.out.println("First Element is(using peekFirst()): " + i1);
	    System.out.println("First Element is(using getFirst()): " + i2);
	    
	    Integer i3 = deck.peekLast();
	    Integer i4 = deck.getLast();
	    System.out.println("Last Element is(using peekLast()): " + i3);
	    System.out.println("Last Element is(using getLast()): " + i4);
	}
}

Deque After Insertion: [5, 10, 15, 20]
First Element is(using peekFirst()): 5
First Element is(using getFirst()): 5
Last Element is(using peekLast()): 20
Last Element is(using getLast()): 20

Iterating through an ArrayDeque

We can traverse an ArrayDeque with the help of an Iterator as we do to access other collection elements.

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

public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> deck = new ArrayDeque<Integer>();
	    deck.addLast(5);
	    deck.addLast(10);  
	    deck.addLast(15);
	    deck.addLast(20);
	    
	    Iterator i = deck.iterator();
	    while(i.hasNext())
	    	System.out.print(i.next() + " "); 
	}
}

5 10 15 20

Iterating ArrayDeque in Reverse

We can iterate the ArrayDeque in the reverse order by using a descending iterator.

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

public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> deck = new ArrayDeque<Integer>();
	    deck.addLast(5);
	    deck.addLast(10);  
	    deck.addLast(15);
	    deck.addLast(20);
	    
	    Iterator i = deck.descendingIterator();
	    while(i.hasNext())
	    	System.out.print(i.next() + " "); 
	}
}

20 15 10 5

Why do we have two methods for each operation?

As you may have noticed, we have two methods that can perform the same operation. For example, we can remove the last element from an ArrayDeque by using the removeLast() method or the pollLast() method. The difference between these methods is that one of them returns an exception if the operation fails. And the other one returns a value that denotes the failed operation.

Methods that return an exception if operation fails are:

• addFirst()
• addLast()
• removeFirst()
• removeLast()
• getFirst()
• getLast()

Methods that return a value without exception if operation fails are:

• offerFirst()
• offerLast()
• pollFirst()
• pollLast()
• peekFirst()
• peekLast()

Let's understand this with the help of an example. We have an empty Deque, and we use the removeLast() method on it. We will get a NoSuchElementException.

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

public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> deck = new ArrayDeque<Integer>();
	    System.out.print(deck.removeLast());
	}
}

Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.ArrayDeque.removeLast(ArrayDeque.java:372)
at snippet.ArrayDequeDemo.main(ArrayDequeDemo.java:11)

But if we use the pollLast() method, we do not get any exception. In the output below, we can see that the method returns a null. This denotes that the deletion was not successful.

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

public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> deck = new ArrayDeque<Integer>();
	    System.out.print(deck.pollLast());
	}
}

null

ArrayDeque as a Stack

As discussed in the previous sections, we can implement a Stack using an ArrayDeque. We will choose one end of the Deque(front or rear) to insert and delete elements from this end only. We can either use the methods that we discussed for insertion and deletion. Or we can use the convenient push() and pop() methods with the ArrayDeque.

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

public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> stk = new ArrayDeque<Integer>();
		stk.push(15);
	    stk.push(10);
	    stk.push(5);
	    System.out.println("Stack after insertion: " + stk);
	    
	    stk.pop();
	    System.out.println("Stack after deletion: " + stk);
	    stk.pop();
	    System.out.println("Stack after deletion: " + stk);
	}
}

Stack after insertion: [5, 10, 15]
Stack after deletion: [10, 15]
Stack after deletion: [15]

ArrayDeque as a Queue

We can implement a Queue using ArrayDeque by inserting elements at one end and removing them from the other. We can use the methods discussed above. Or we can use the add() and remove() methods. These methods automatically decide the front and the rear end and insert and delete elements accordingly.

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

public class ArrayDequeDemo
{
	public static void main(String[] args)
	{
		Deque<Integer> que = new ArrayDeque<Integer>();
		que.add(5);
		que.add(15);
		que.add(20);
	    System.out.println("Queue after insertion: " + que);
	    
	    que.remove();
	    System.out.println("Queue after deletion: " + que);
	    que.remove();
	    System.out.println("Queue after deletion: " + que);
	}
}

Queue after insertion: [5, 15, 20]
Queue after deletion: [15, 20]
Queue after deletion: [20]

Summary

The following points summarize the key features of the ArrayDeque class.

• Deque can be thought of as a Queue where insertion and deletion can take place on either end.
• ArrayDeque uses a dynamic array to implement the Deque data structure. The ArrayDeque automatically doubles in size when we run out of space.
• We can implement the Stack and Queue data structures using an ArrayDeque.
• Stacks, when implemented using ArrayDeques, work much faster than the normal Stack class.
• Similarly, Queues implemented using ArrayDeques are faster than LinkedList used as Queues.
• Note that the ArrayDeque class is not thread-safe, and we need to synchronize them for concurrent access.
• ArrayDeques do not allow null elements to be inserted in them.