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.

Below diagram will explain how Dque Works

Deque in Java Or ArrayDeque In Java

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

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

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.

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

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.

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

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.

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

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

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.