Deque in Java | ArrayDeque in Java

Deque in Java | ArrayDeque in Java

Before starting with this post if you are not aware of Queue concept then please visit and check our post on Queue. Now if you are continuing this post then you are already aware of Queue concept. Now let’s get rolling.

Deque means Doubly ended queue. As we know for Queue, insertion will be done from one end(Rear) and deletion or retrieval from one end(Front) in contrast to this Deque comes with added advantage i.e As the name Deque or Doubly Ended Queue clearly suggest that Deque is both ended queue that means insertion and deletion can be done from both end(Front and Rear). If you are not getting this then don’t worry we will explain to you from example.

Before getting to example we will learn about basic Deque operations.

addFirst(e)Inserts Element at Front of the Dequeue
addLast(e)Inserts Element at Rear of the Dequeue
getFirst()Gets element from Front of the Dequeue
getLast()Gets the element at Rear of the Dqueue
removeFirst()Removes an element from Front of the Dequeue
removeLast()Removes the element from Front of the Dequeue

Below diagram will explain how Dque Works

Deque Operations

Deque in Java Or ArrayDeque In Java

Deque and ArrayDeque hierarchy in Collection
Deque and ArrayDeque hierarchy in Collection

As shown in the above image it’s clear that Deque is an interface that extends Collection, Iterable and Queue. And ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque are the Implementations for Deque.

Deque is a linear collection that allows Insertion, Deletion and Retrieval operation from both end of the Deque. Each of these operations are provided in two flavours by Deque one Which throws exception and other Which Does not throw Exception instead returns special value like null or false/true depending on the nature of the operation.

Here we have categorised the Operation which throw Exception and which does not throw exception.

Operations that Operate on First Element i.e Head

OperationThrows ExceptionDoes Not Throws Exception But return Special Value
insertaddFirst(e)offerFirst(e)
RemoveremoveFirst()pollFirst()
RetrievegetFirst()peekFirst()

Operations that Operate on Last Element i.e Rear/Tail

OperationThrows ExceptionDoes Not Throws Exception But return Special Value
insertaddLast(e)offerLast(e)
RemoveremoveLast()pollLast()
RetrievegetLast()peekLast()

ArrayDeque is a class which provides implementation for Deque. It is resizable implementation of Deque which means that there is no restriction on size of ArrayDeque. ArrayDeque can increase its size as ArrayDeque grows.

This class provides fail-fast iterator that means that whenever the queue is modified when Deque is created then it throws ConcurrentModificationException Unless it is modified through iterator.remove().

As ArrayDeque provides an implementation for all Deque interface so we will discuss methods provided in ArrayDeque

Methods in ArrayDeque

We will group methods as per opertations like insert, remove, get, iterate and etc.

Creating ArrayDeque

ArrayDeque can be created using following constructors.

ArrayDeque()Creates a queue with initial size of 16
ArrayDeque(Collection<? extends E> c)Constructs a dequeue with give collection
ArrayDeque(int numElements)Constructs a deque with capacity that will be sufficient to hold numElements
private static void createDeQue() {
		System.out.println("Creating DeQueue with default inital capacity of 16");
		Deque<String> deque = new ArrayDeque<String>();
		List<String> list = new ArrayList<>();
		list.add("India");
		list.add("US");
		System.out.println("Creating DeQueue with provided collection");
		Deque<String> dequeFromCollection = new ArrayDeque<String>(list);
		
		System.out.println("Creating DeQueue with initail Capacity");
		Deque<String> dequeWithElementsSize = new ArrayDeque<String>(10);
	}

Adding Elements to ArrayDeque

Elements can be added to ArrayDeque using below methods

boolean add(E e)Add an element to rear/tail of the Deque and return true if insertion is a success.
void addFirst(E e)Add an element to the head of the Deque. And throws an exception when operation fails
void addLast(E e)Add an element to the rear/tail of the Deque. And throws an exception when operation fails
boolean offerFirst(E e)Add an element to the head of the Deqeue and returns true in case of a success
boolean offerLast(E e)Add an element to the rear/tail of the Deque and returns true in case of a success
boolean offer(E e)Adds an element at the end i.e at tail of the Deque

Code illustrating above operations

	private static void insertElementsToDeque() {
		List<String> list = new ArrayList<>();
		list.add("Canada");
		list.add("Nepal");
		System.out.println("Creating DeQueue with provided collection");
		Deque<String> deque = new ArrayDeque<String>(list);
		System.out.println("Deque initialy: "+ deque);

		System.out.println("Adding India to Queue's tails/rear using add()");
		deque.add("India");
		System.out.println("Deque after adding India"+ deque);
		
		System.out.println("Adding US to Queue's head using addFirst()");
		deque.addFirst("US");
		System.out.println("Deque after adding US"+ deque);
		
		System.out.println("Adding Africa to Queue's head using offerFirst()");
		deque.offerFirst("Africa");
		System.out.println("Deque after adding Africa"+ deque);

		System.out.println("Adding Japan to Queue's rear/tail using addLast()");
		deque.addLast("Japan");
		System.out.println("Deque after adding Japan"+ deque);
		
		System.out.println("Adding Bhutan to Queue's rear/tail using offerLast()");
		deque.offerLast("Bhutan");
		System.out.println("Deque after adding Bhutan"+ deque);
		
		System.out.println("Adding Canada to Queue's rear/tail using offer()");
		deque.offer("Canada");
		System.out.println("Deque after adding Canada"+ deque);

	}

Output for above code

Creating DeQueue with provided collection
Deque initialy: [Canada, Nepal]
Adding India to Queue's tails/rear using add()
Deque after adding India[Canada, Nepal, India]
Adding US to Queue's head using addFirst()
Deque after adding US[US, Canada, Nepal, India]
Adding Africa to Queue's head using offerFirst()
Deque after adding Africa[Africa, US, Canada, Nepal, India]
Adding Japan to Queue's rear/tail using addLast()
Deque after adding Japan[Africa, US, Canada, Nepal, India, Japan]
Adding Bhutan to Queue's rear/tail using offerLast()
Deque after adding Bhutan[Africa, US, Canada, Nepal, India, Japan, Bhutan]

Removing the Element From the Deque or ArrayDeque

Deque provides several methods to remove elements form the deque.

E poll()Removes the first element from the head of the Deque and returns null if deque is empty
E pollFirst()Removes the first element from the head of the Deque and returns null if deque is empty
E pollLast()Removes the last element from Deque and returns null if deque is empty
E remove()Removes the first element from the head of the Deque. and throws Exception if deque is empty
boolean Remove(Object o)Remove the first finding of object in deque and returns true else returns false
boolean removeFirst() Removes the first element from the Deque and throws Exception if deque is empty
boolean removeLast()Removes an element from the Deque and throws Exception if deque is empty
void clear()Removes all Element from deque.

Code illustrating above operations

private static void removeElementsFromDeque() {
		Deque<String> deque = new ArrayDeque<String>();
		deque.addFirst("India");
		deque.addFirst("America");
		deque.addFirst("Canada");
		deque.addFirst("Japan");
		deque.addFirst("China");
		deque.addFirst("Russia");
		deque.addFirst("Bhutan");
		deque.addFirst("Nepal");
		deque.addFirst("Pakistan");
		System.out.println("Deque initialy: "+ deque);

		System.out.println("Removing element from deque using poll() and it returns:"+ deque.poll());
		System.out.println("Deque after removing "+ deque);
		
		System.out.println("Removing element from deque using pollFirst() and it returns:"+ deque.pollFirst());
		System.out.println("Deque after removing "+ deque);

		System.out.println("Removing element from deque using pollLast() and it returns:"+ deque.pollLast());
		System.out.println("Deque after removing "+ deque);
		
		System.out.println("Removing element from deque using remove() and it returns:"+ deque.remove());
		System.out.println("Deque after removing "+ deque);
		
		System.out.println("Removing element from deque using removeFirst() and it returns:"+ deque.removeFirst());
		System.out.println("Deque after removing "+ deque);
		
		System.out.println("Removing element from deque using removeLast() and it returns:"+ deque.removeLast());
		System.out.println("Deque after removing "+ deque);
		
		System.out.println("Removing element from deque using remove(Object) and it returns:"+ deque.remove("China"));
		System.out.println("Deque after removing "+ deque);
		
		System.out.println("Removing all elements from deque using clear() and it returns: void");
		deque.clear();
		System.out.println("Deque after removing "+ deque);
		
	}

Output of above code is

Deque initialy: [Pakistan, Nepal, Bhutan, Russia, China, Japan, Canada, America, India]
Removing element from deque using poll() and it returns:Pakistan
Deque after removing [Nepal, Bhutan, Russia, China, Japan, Canada, America, India]
Removing element from deque using pollFirst() and it returns:Nepal
Deque after removing [Bhutan, Russia, China, Japan, Canada, America, India]
Removing element from deque using pollLast() and it returns:India
Deque after removing [Bhutan, Russia, China, Japan, Canada, America]
Removing element from deque using remove() and it returns:Bhutan
Deque after removing [Russia, China, Japan, Canada, America]
Removing element from deque using removeFirst() and it returns:Russia
Deque after removing [China, Japan, Canada, America]
Removing element from deque using removeLast() and it returns:America
Deque after removing [China, Japan, Canada]
Removing element from deque using remove(Object) and it returns:true
Deque after removing [Japan, Canada]
Removing all elements from deque using clear() and it returns: void
Deque after removing []

Retrieving Elements from Deque or ArrayDeque

Deque provides us with below method to retrieve element from deque

E getFirst()Retrieves first element from the queue and throws exception when queue is empty. It does not remove element from deque
E getLast()Retrieves last element from the queue and throws exception when queue is empty. It does not remove element from deque
E peek()Retrieves first element from head of the queue and return null when the queue is empty. It does not remove element from deque
E peekFirst()Retrieves first element from the queue and return null when queue is empty. It does not remove element from deque
E peekLast()Retrieves last element from the queue and return null when queue is empty. It does not remove element from deque

Code illustration for above operations

	private static void retrieveElemntfromDeQue() {
		Deque<String> deque = new ArrayDeque<String>();
		deque.addFirst("India");
		deque.addFirst("America");
		deque.addFirst("Canada");
		
		System.out.println("Deque initialy: "+ deque);		
		
		System.out.println("Retrieve element from deque using getFirst() and it returns: "+ deque.getFirst());
		System.out.println("Retrieve element from deque using getLast() and it returns: "+ deque.getLast());
		System.out.println("Retrieve element from deque using peek() and it returns: "+ deque.peek());
		System.out.println("Retrieve element from deque using peekFirst() and it returns: "+ deque.peekFirst());
		System.out.println("Retrieve element from deque using peekLast() and it returns: "+ deque.peekLast());

	}

Output for above code is

Deque initialy: [Canada, America, India]
Retrieve element from deque using getFirst() and it returns: Canada
Retrieve element from deque using getLast() and it returns: India
Retrieve element from deque using peek() and it returns: Canada
Retrieve element from deque using peekFirst() and it returns: Canada
Retrieve element from deque using peekLast() and it returns: India

Iterating Through Deque or ArrayDeque

ArrayDeque provides Iterator to traverse through Deque. Lets check those method.

Iterator<E> iterator()Provides Iterator to iterate through deque
Spliterator<E> spliterator()Creates a late-binding and fail-fast Spliterator over the elements in this deque.

Code for above operation

private static void iteratingOverDeque() {
		Deque<String> deque = new ArrayDeque<String>();
		deque.addFirst("India");
		deque.addFirst("America");
		deque.addFirst("Canada");
		deque.addFirst("Japan");
		deque.addFirst("China");
		deque.addFirst("Russia");
		deque.addFirst("Bhutan");

		System.out.println("Deque initialy: "+ deque);
		
		Iterator<String> iterator = deque.iterator();
		System.out.println("Iterating elements using iterator:");
		while(iterator.hasNext()) {
			System.out.print(" "+iterator.next());
		}
		System.out.println();
		System.out.println("Iterating elements using splitIterator:");

		Spliterator<String> splitIterator = deque.spliterator();
		splitIterator.forEachRemaining(s-> System.out.print(" " +s));

		
	}

Output of above code is

Deque initialy: [Bhutan, Russia, China, Japan, Canada, America, India]
Iterating elements using iterator:
Bhutan Russia China Japan Canada America India
Iterating elements using splitIterator:
Bhutan Russia China Japan Canada America India

Converting Deque or ArrayDeque to Array

Code for converting Deque to Array

private static void convertingDequeToArray() {
		Deque<String> deque = new ArrayDeque<String>();
		deque.addFirst("India");
		deque.addFirst("America");
		deque.addFirst("Canada");
		deque.addFirst("Japan");
		deque.addFirst("China");
		deque.addFirst("Russia");
		deque.addFirst("Bhutan");

		System.out.println("Deque initialy: "+ deque);
		
		System.out.println("Deque to Array: ");
		Stream.of(deque.toArray()).forEach(s -> System.out.print(" "+s));
	}

Output for above code

Deque initialy: [Bhutan, Russia, China, Japan, Canada, America, India]
Deque to Array:
Bhutan Russia China Japan Canada America India

Conclusion

Here we learned how Deque which is also called as Doubly Ended Queue works. i.e is in Deque insertion, retrieval and removal can be done from both end( rear or head) of the queue most common operation of the deque are as below.

Operations that Operate on First Element i.e Head

OperationThrows ExceptionDoes Not Throws Exception But return Special Value
insertaddFirst(e)offerFirst(e)
RemoveremoveFirst()pollFirst()
RetrievegetFirst()peekFirst()

Operations that Operate on Last Element i.e Rear/Tail

OperationThrows ExceptionDoes Not Throws Exception But return Special Value
insertaddLast(e)offerLast(e)
RemoveremoveLast()pollLast()
RetrievegetLast()peekLast()

Also, this post we learned about Deque and ArrayDeque class. ArrayDeque class of java provide and implementation of Deque interface and provdies and Iterator and SplitIterator to iterate over element.

Thank’s Note

Thanks for spending your valuable time reading this post. Hope this post taught you something new today. Please share the post if you like it.

Durgesh Kumar

He is the Founder of TechiJournal.com. And have 4+ years of experience as full-stack Java developer. He worked with many reputed product companies and would like to share his experience and knowledge through this blog. He works very hard to provide you with quality content. But as no one is perfect, If you feel that some improvement can be made then feel free to add it in the comment section. We look forward to it.

Leave a Reply