ZOFTINO.COM android and web dev tutorials

Java Collections Deque Tutorial

Deque is a double ended queue meaning it allows elements addition and removal at both ends of the queue. Deque implementations can be with fixed capacity or without capacity limitation on the number of elements it can hold.

BlockingDeque interface extends Deque interface and defines blocking operations at both ends. In addition to providing operations for adding and removing elements at both ends, Deque and BlockingDeque supports all queue and blocking queue and collection operations.

Table of Contents

Deque Hierarchy

Java collections framework provides implementations of Deque such as ArrayDeque, ConcurrentLinkedDeque and LinkedList. Implementation of BlockingQueue interface is LinkedBlockingDeque.

java deque hierarchy

ArrayDeque

ArrayDeque holds elements in an internal array which is resizable. It can grow as elements are added to it. Null elements can’t be added to array deque. It can be instantiated using no argument constructor which set the initial capacity of array to 16 or using constructor which takes initial capacity as argument.

	ArrayDeque<String> arrayDeque = new ArrayDeque<String>();
	
	ArrayDeque<String> stores = new ArrayDeque<String>(2);
	stores.add("amazon");
	stores.add("walmart");
	stores.add("ebay");
	
	System.out.println("size of array deque: "+stores.size());

Output

size of array deque: 3

Following sections use ArrayDeque to provide details about deque operations.

LinkedBlockingDeque

LinkedBlockingDeque implements BlockingDeque and provides blocking add and remove operations when queue is full or empty. LinkedBlockingDeque can be instantiated as bounded deque using default constructor or unbounded deque by passing capacity to its constructor.

		LinkedBlockingDeque<Integer> nums = 
				new LinkedBlockingDeque<Integer>();
		System.out.println("capacity : "+nums.remainingCapacity());
		
		LinkedBlockingDeque<Integer> numsLimited = 
				new LinkedBlockingDeque<Integer>(5);
		System.out.println("capacity : "+numsLimited.remainingCapacity());

Output

capacity : 2147483647
capacity : 5

Deque Add Operations

Since elements can be added at both ends of deque, it provides addFirst and addLast operations in addition to add operation. Following example shows that addFirst adds the given element at the front of queue and similar to add operation, addLast operation adds the given element at the end of deque.

	ArrayDeque<String> brands = new ArrayDeque<String>();
	brands.add("lee");
	brands.add("levis");
	
	System.out.println("elements in deque: "+brands);
	
	brands.addFirst("polo");
	brands.addLast("nautica");
	
	System.out.println("elements in deque: "+brands);

Output

elements in deque: [lee, levis]
elements in deque: [polo, lee, levis, nautica]

Another set of add operations that the deque supports are offer, offerFirst and offerLast. The difference between add set of operations and offer set of operations is that offer operations return false in case if it can’t add the given element to deque, whereas add operations throw exceptions. For example, when adding elements to a capacity bounded deque (LinkedBlockingDeque), add operations throw exception and offer operations return false if deque is full.

Following example throws exception as add operation is trying to add an element after deque is full.

	LinkedBlockingDeque<Integer> mrp = 
			new LinkedBlockingDeque<Integer>(2);
	mrp.offer(22);
	mrp.offerFirst(120);
	mrp.add(130);

Output

java.lang.IllegalStateException: Deque full

Using any of the offer methods, you can check the status of the operation as offer methods return false if they can’t add element to the deque.

	LinkedBlockingDeque<Integer> mrp = 
			new LinkedBlockingDeque<Integer>(2);
	mrp.offer(22);
	mrp.offerFirst(120);
	if(!mrp.offerLast(130)){
		System.out.println("deque is full");
	}

Output

deque is full

Deque Remove Operations

In addition to remove() operation, deque provides removeFirst() and removeLast() operations to remove first element and last element of the deque respectively. Methods remove and removeFirst operations removes first element in deque.

	ArrayDeque<String> categories = new ArrayDeque<String>();
	categories.add("fashion");
	categories.add("electronics");
	categories.add("appliance");
	categories.add("bags");
	
	System.out.println("removed last element: "+categories.removeLast());
	System.out.println("removed first element: "+categories.removeFirst());
	System.out.println("removed element: "+categories.remove());

Output

removed last element: bags
removed first element: fashion
removed element: electronics

There is another set of remove operations such as poll, pollFirst and pollLast, which can be used to remove elements from deque. The difference between remove and poll operations is that remove operations throw exception if deque is empty, whereas poll operation returns null.

Following examples shows that if any remove operations is called on an empty deque, it will throw an exception.

		ArrayDeque<String> categories = new ArrayDeque<String>();
		System.out.println("last element: "+categories.removeLast());

Output

java.util.NoSuchElementException

Following example shows that poll, pollFirst or pollLast return null if deque is empty.

	ArrayDeque<String> categories = new ArrayDeque<String>();
	System.out.println("last element: "+categories.pollLast());
	System.out.println("first element: "+categories.pollFirst());
	System.out.println("element: "+categories.poll());

Output

last element: null
first element: null
element: null

A specific element can be removed using remove, removeFirstOccurrence or removeLastOccurrence.

	ArrayDeque<Integer> marks = new ArrayDeque<Integer>();
	marks.add(22);
	marks.add(33);
	marks.add(44);
	marks.add(33);
	marks.add(22);
	marks.add(44);
	
	System.out.println(""+marks);
	
	marks.remove(22);
	System.out.println("after remove 22: "+marks);
	
	marks.removeLastOccurrence(33);
	System.out.println("after remove last occurrence of 33: "+marks);
	
	marks.removeFirstOccurrence(44);
	System.out.println("after remove first occurence of 44: "+marks);

Output

[22, 33, 44, 33, 22, 44]
after remove 22: [33, 44, 33, 22, 44]
after remove last occurrence of 33: [33, 44, 22, 44]
after remove first occurence of 44: [33, 22, 44]

Deque Examine Operations

To obtain element without removing it from deque, you can use peek, peekFirst or peekLast or element, getFirst or getLast methods. Peek methods return null and element and get methods throw exception if queue is empty.

	ArrayDeque<String> categories = new ArrayDeque<String>();
	System.out.println("last element: "+categories.peekLast());
	
	categories.add("travel");
	categories.add("home");
	categories.add("kitchen");
	
	System.out.println("last element: "+categories.peekLast());
	System.out.println("first element: "+categories.peekFirst());
	System.out.println("element: "+categories.peek());
	
	System.out.println("elements in deque after peek operations:\n"
						+categories);

Output

last element: null
last element: kitchen
first element: travel
element: travel
elements in deque after peek operations:
[travel, home, kitchen]

Deque Iterator

Elements in deque can be traversed in both directions using iterator() and descendingIterator() operations.

	ArrayDeque<Integer> points = new ArrayDeque<Integer>();
	points.add(356);
	points.add(298);
	points.add(127);
	
	Iterator<Integer> iterator = points.iterator();	
	System.out.println("normal iterator");
	iterator.forEachRemaining(s -> {
		System.out.println(""+s);
	});
	
	System.out.println("descending iterator");
	Iterator<Integer> iteratorDesc = points.descendingIterator();		
	iteratorDesc.forEachRemaining(s -> {
		System.out.println(""+s);
	});

Output

normal iterator
356
298
127
descending iterator
127
298
356

Deque Stack Operations

Deque defines stack operations such as push and pop. Push operation adds element at head of the deque and pop operation removes element at the head.

	ArrayDeque<Integer> points = new ArrayDeque<Integer>();
	points.push(340);
	points.push(230);
	System.out.println("pop element: "+points.pop());

Output

pop element: 230

BlockingDeque Operations

Like BlockingQueue defines blocking operations when queue is empty or full, BlockingDeque defines blocking operations such as put, putFirst, putLast, take, takeFirst and takeLast operations for adding or removing elements at both ends.

For example, if takeFirst is called on the blocking deque, it will return first element if elements exist, otherwise it will wait till an element is added to the deque and return it.

	LinkedBlockingDeque<Integer> offers = 
			new LinkedBlockingDeque<Integer>();
	
	new Thread(new Runnable() {
		@Override
		public void run() {		
			try {
				System.out.println("waiting for element");
				System.out.println("element :"+offers.takeFirst());
			} catch (InterruptedException e1) {
				e1.printStackTrace();
			}				
		}			
	}).start();	
	
	try {
		Thread.sleep(20);
	} catch (InterruptedException e) {
		e.printStackTrace();
	}
	
	System.out.println("adding an element to deque");		
	offers.add(22);

Output

waiting for element
adding an element to deque
element :22

Similarly, put operation blocks if deque is full.

	LinkedBlockingDeque<Integer> offers = 
			new LinkedBlockingDeque<Integer>(2);
	
	new Thread(new Runnable() {
		@Override
		public void run() {		
			try {
				System.out.println("adding element one and two");
				offers.put(35);
				offers.put(45);
				System.out.println("waiting for space in deque");	
				offers.put(55);
				System.out.println("space avaialbe added element to deque");	
			} catch (InterruptedException e1) {
				e1.printStackTrace();
			}				
		}			
	}).start();	
	
	try {
		Thread.sleep(20);
	} catch (InterruptedException e) {
		e.printStackTrace();
	}
	
	System.out.println("removing an element from deque");		
	offers.remove();

Output

adding element one and two
waiting for space in deque
removing an element from deque
space avaialbe added element to deque

Operations such as poll, pollFirst, pollLast, offer, offerFirst and offerLast can be used in blocking way by specifying amount of time the operation needs to wait in case if deque is empty or full.

ConcurrentLinkedDeque

In your application, if multiple threads need to access deque safely, you can use ConcurrentLinkedDeque. ConcurrentLinkedDeque is an unbound deque, capacity grows as you add elements. It doesn’t permit null values. It supports all deque operations.