Deque interface and ArrayDeque - Java Example

The Deque interface in java is a subtype of Queue interface. A deque is a double-ended-queue, usually pronounced as “deck”. It supports the addition and removal of items from both the ends. It can act like both stacks (LIFO) and queues (FIFO).

We can say deque provides a more versatile data structure than either stack or a queue. However it is not used often compared to stacks and queues in practice.

The hierarchy of deque interface in java is shown below

Deque Interface Java SE 8

The 12 deque methods for insertion, removal and retrieval of Deque elements are listed below

public interface Deque<E> extends Queue<E> {
     
    //Insert operations
    void addFirst(E e)
    void addLast(E e)
    boolean offerFirst(E e);
    boolean offerLast(E e);
    
    //Remove operations
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();

    //Examine operations
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();   

}

Deque Example

Let’s create deque using linked list and experiment some of the deque methods as shown in example below.

package com.sneppets.java.collections;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Program to demonstrate deque interface
 * @author sneppets.com
 */
public class DequeInterfaceExample {

	public static void main(String[] args)
	{
		Deque<String> dq = new LinkedList<String>();
		
		//insert operations
		System.out.println("Inserting elements..");
		dq.addFirst("A");
		dq.addLast("Z");
		dq.offerFirst("B");
		dq.offerLast("Y");		
		System.out.println("Deque after insert operations : " + dq);
		
		//examine operations
		System.out.println("Examining elements...");
		System.out.println("getFirst()..." + dq.getFirst());
		System.out.println("peekLast()..." + dq.peekLast());		
		System.out.println("Deque after examine operations : "+ dq);
		
		//remove operations
		System.out.println("Removing elements...");
		System.out.println("removeFirst()..." + dq.removeFirst());
		System.out.println("pollLast()..." +dq.pollLast());		
		System.out.println("Deque after remove operations : "+ dq);		
		
	}
}

Output

Inserting elements..
Deque after insert operations : [B, A, Z, Y]
Examining elements...
getFirst()...B
peekLast()...Y
Deque after examine operations : [B, A, Z, Y]
Removing elements...
removeFirst()...B
pollLast()...Y
Deque after remove operations : [A, Z]

Deque in Collection Hierarchy

ArrayDeque

ArrayDeque is the resizable-array implementation of the Deque interface. It extends AbstractCollection and implements Deque interface. It does not have any capacity restrictions and they grow the array size as necessary.

They are not thread safe and it does not allow to insert Null elements. ArrayDeque is faster than Stack when used as a stack and faster than Linked List when used as a queue.

Example: ArrayDeque

package com.sneppets.java.collections;

import java.util.ArrayDeque;

/**
 * Program to demonstrate ArrayDeque
 * @author sneppets.com
 */
public class ArrayDequeExample {

	public static void main(String[] args)
	{
		ArrayDeque<String> aq = new ArrayDeque<String>();
		
		aq.add("A");
		aq.add("B");
		aq.add("C");
		aq.add("D");
		
		System.out.println(aq);
		
		//insert operations
		aq.addFirst("X");
		aq.addLast("Y");
		
		System.out.println(aq);
		
		//remove operations
		aq.removeFirst();
		aq.removeLast();
		
		System.out.println(aq);
	}
}

Output

[A, B, C, D]
[X, A, B, C, D, Y]
[A, B, C, D]

Related Posts

Reference

Oracle Documentation