Java ArrayDeque

Java ArrayDeque implements Deque interface and ArrayDeque is available from java 1.6. ArrayDeque is an Optimized stack and queue. Java ArrayDeque is available in java.util package which implements a double-ended queue, allows efficient insertion and deletion from both ends.

ArrayDeque internally used array to store its elements. if number of elements exceeds the space in array( when head and tail have wrapped around to become equal), a new array is allocated and all elements copied. In other words, ArrayDeque grows as needed.

ArrayDeque is a generic class that has this declaration:

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable

Here, E specifies the type of objects that the ArrayDeque will hold.

• Java ArrayDeque inherits AbstractCollection class.
• Java ArrayDeque does not permit null elements.
• Deque is that queue which allows insert and remove of elements from both sides.
• ArrayDeque can be used as stack and queue both. when it is used as stack, it is fatsre than Stack and when it is used as queue, it is faster than LinkedList.
• Java ArrayDeque can not be used for primitive types, like int, char, etc. We need to use wrapper classes.
• Java ArrayDeque is not synchronized.
• Java ArrayDeque is not thread-safe, in the absence of external synchronization, they do not support concurrent access by multiple threads.
• Most of the Java ArrayDeque operations run in amortized constant time. Exceptions include remove(Object), removeFirstOccurrence, removeLastOccurrence, contains,iterator.remove(), and the bulk operations, all of which run in linear time.
• The iterators returned by this ArrayDeque's iterator method are fail-fast.

Java ArrayDeque constructors

There are three constructors in Java ArrayDeque.

Constructor	Description
public ArrayDeque()	Constructs an empty array deque with an initial capacity sufficient to hold 16 elements.
public ArrayDeque(int numElements)	Constructs an empty array deque with an initial capacity sufficient to hold the specified number of elements.
public ArrayDeque(Collection<? extends E> c)	Constructs a deque containing the elements of the specified collection, in the order they are returned by the collection's iterator.

Below is a simple code snippet showing Java ArrayDeque constructors.

// default constructor
ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();
arrayDeque.add(10);
arrayDeque.add(20);
arrayDeque.add(30);

// ArrayDeque with initial capacity
ArrayDeque<String> words = new ArrayDeque<>(2000);

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

//ArrayDeque based on collection
ArrayDeque<String> deque = new ArrayDeque<>(list);

Java ArrayDeque methods

Method	Description
public boolean add(E e)	Inserts the specified element at the end of this deque.
public void addFirst(E e)	Inserts the specified element at the front of this deque.
public void addLast(E e)	Inserts the specified element at the end of this deque.
public boolean offer(E e)	Inserts the specified element at the end of this deque.
public boolean offerFirst(E e)	Inserts the specified element at the front of this deque.
public boolean offerLast(E e)	Inserts the specified element at the end of this deque.
public E removeFirst()	Retrieves and removes the first element of this deque. This method differs from pollFirst only in that it throws an exception if this deque is empty.
public E removeLast()	Retrieves and removes the last element of this deque. This method differs from pollLast only in that it throws an exception if this deque is empty.
public E pollFirst()	Retrieves and removes the first element of this deque, or returns null if this deque is empty.
public E pollLast()	Retrieves and removes the last element of this deque, or returns null if this deque is empty.
public E getFirst()	Retrieves, but does not remove, the first element of this deque. This method differs from peekFirst only in that it throws an exception if this deque is empty.
public E getLast()	Retrieves, but does not remove, the last element of this deque. This method differs from peekLast only in that it throws an exception if this deque is empty.
public E peekFirst()	Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty.
public E peekLast()	Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty.
public boolean removeFirstOccurrence(Object o)	Removes the first occurrence of the specified element in this deque (when traversing the deque from head to tail).
public boolean removeLastOccurrence(Object o)	Removes the last occurrence of the specified element in this deque (when traversing the deque from head to tail).
public E remove()	Retrieves and removes the head of the queue represented by this deque.
public E poll()	Retrieves and removes the head of the queue represented by this deque.
public E element()	Retrieves, but does not remove, the head of the queue represented by this deque. This method differs from peek only in that it throws an exception if this deque is empty.
public E peek()	Retrieves, but does not remove, the head of the queue represented by this deque, or returns null if this deque is empty.
public void push(E e)	Pushes an element onto the stack represented by this deque. In other words, inserts the element at the front of this deque.
public E pop()	Pops an element from the stack represented by this deque. In other words, removes and returns the first element of this deque.
public int size()	Returns the number of elements in this deque.
public boolean isEmpty()	Returns true if this deque contains no elements.
public Iterator<E> iterator()	Returns an iterator over the elements in this deque. The elements will be ordered from first (head) to last (tail).
public Iterator<E> descendingIterator()	Returns an iterator over the elements in this deque in reverse sequential order. The elements will be returned in order from last (tail) to first (head).
public boolean contains(Object obj)	Returns true if this deque contains the specified element. More formally, returns true if and only if this deque contains at least one element e such that obj.equals(e).
public boolean remove(Object obj)	Removes a single instance of the specified element from this deque.
public void clear()	Removes all of the elements from this deque. The deque will be empty after this call returns.
public Object[] toArray()	Returns an array containing all of the elements in this deque in proper sequence (from first to last element).
public <T> T[] toArray(T[] a)	Returns an array containing all of the elements in this deque in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array. If the deque fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this deque.
public ArrayDeque<E> clone()	Returns a copy of this deque.
public Spliterator<E> spliterator()	Creates a late-binding and fail-fast Spliterator over the elements in this deque.

Java ArrayDeque Example

Java ArrayDeque common operations

Here we will see an example of commonly used method of ArrayDeque.

package com.walking.techie;

import java.util.ArrayDeque;

public class ArrayDequeDemo {
    public static void main(String[] args) {

        ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();
        // add an element at the end of the deque.
        arrayDeque.add(10);

        // add an element at the front of the deque.
        arrayDeque.addFirst(20);

        // add an element at the end of the deque.
        arrayDeque.addLast(30);

        // add an element at the end of the deque.
        arrayDeque.offer(40);

        // add an element at the front of the deque.
        arrayDeque.offerFirst(50);

        // add an element at the end of the deque.
        arrayDeque.offerLast(60);

        System.out.println("Elements of ArrayDeque: "
                + arrayDeque);

        // retrieve and remove first element from deque.
        System.out.println("Head element of the deque: "
                + arrayDeque.removeFirst());

        //retrieve and remove last element from deque.
        System.out.println("Last element of the deque: "
                + arrayDeque.removeLast());
    }
}

Output of above program is shown below:

Elements of ArrayDeque: [50, 20, 10, 30, 40, 60]
Head element of the deque: 50
Last element of the deque: 60

Java ArrayDeque Iterator

Java ArrayDeque iterator is fail-fast, so iterator will throw java.util.ConcurrentModificationException if the deque is modified at any time after the iterator is created, in any way except through the iterator's own remove method. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

The iterator of ArrayDeque returns the elements in proper sequence (from first to last element).

package com.walking.techie;

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

public class ArrayDequeIteratorDemo {
    public static void main(String[] args) {

        ArrayDeque<Integer> numbers = new ArrayDeque<>();
        numbers.add(23);
        numbers.add(34);
        numbers.add(13);
        numbers.add(2);
        numbers.add(28);
        System.out.print("Elements of numbers deque [");

        // traversal over ArrayDeque using iterator
        Iterator<Integer> iterator = numbers.iterator();
        while (iterator.hasNext()) {
            int number = iterator.next();
            System.out.print(number + " ");
        }
        System.out.println("]");

        // ConcurrentModificationException
        iterator = numbers.iterator();

        while (iterator.hasNext()) {

            int number = iterator.next();
            System.out.print(number + " ");
            if (number == 2) {
                System.out.println();
                numbers.add(20);// ConcurrentModificationException
            }
        }
    }
}

Output of above program is shown below:

Elements of numbers deque [23 34 13 2 28 ]
23 34 13 2
Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.ArrayDeque$DeqIterator.next(ArrayDeque.java:643)
 at com.walking.techie.ArrayDequeIteratorDemo.main(ArrayDequeIteratorDemo.java:30)

Java ArrayDeque as Stack and Queue

Stack is a linear data structure which follows LIFO(Last In First Out) or FILO(First In Last Out) order.

Mainly the following three basic operations are performed in the stack:

Push: Adds an item in the stack.
Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed.
Peek: Get the topmost item.

Queue is a linear data structure which follows FIFO(First In First Out) or LILO(Last In Last Out) order.

Mainly the following four basic operations are performed on queue:

Enqueue: Adds an item to the queue. ArrayDeque.add method is equivalent to it.
Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. ArrayDeque.poll method is equivalent to it.

ArrayDeque is faster than Stack when it is used as stack and It is faster than LinkedList when it is used as queue.

package com.walking.techie;

import java.util.ArrayDeque;

public class ArrayDequeDemo {
    public static void main(String[] args) {

        ArrayDeque<String> stack = new ArrayDeque<>();


        // Use an ArrayDeque like a stack
        stack.push("A");
        stack.push("B");
        stack.push("C");
        stack.push("D");
        stack.push("E");
        stack.push("F");

        System.out.println("Popping the stack: ");

        while (stack.peek() != null) {
            System.out.println(stack.pop());
        }


        System.out.println();

        //Use an ArrayDeque like a queue
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        // enqueue the queue elements
        queue.add(10);
        queue.add(20);
        queue.add(30);
        queue.add(40);
        queue.add(50);
        queue.add(60);
        queue.add(70);

        System.out.println("Dequeue the queue: ");

        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

Output of above program is shown below:

Popping the stack:
F
E
D
C
B
A

Dequeue the queue:
10
20
30
40
50
60
70