Deque

java.util.Deque – Deque Java Example

In this example, we are going to explain the java.util.Deque Deque Java interface. The interface name is an abbreviation of “Double Ended Queue”, and it is essentially a queue that implements methods which allows the developer to add elements to both ends of the queue (head and tail). We are going to show the most important methods of this interface, as well as explain their usage of java deque implementation.

1. Deque Java Example

Deque is an interface, so we cannot instantiate it by itself. We can use any of the following implementations,

  • java.util.LinkedList – it is quite common to use Linked List for implementing Queue and the implementation of Deque in Java. This internally uses the Linked List. A new instance can be created as Deque deque = new LinkedList()
  • java.util.ArrayDeque – it internally uses a dynamically resizable array. A new instance can be created as Deque deque = new ArrayDeque()

Below diagram shows the class hierarchy of java.util.Deque,

Deque Java - Deque hierarchy
Deque hierarchy

We are using a LinkedList implementation of java deque in the example. Let’s see how this works.

DequeExample.java

/**
 * @author: Santsoh Balgar Sachchidananda
 */

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

public class DequeExample {

    public static void main(String[] args) {
        Deque deque = new LinkedList();

        // We can add elements to the queue in various ways
        deque.add("Element 1 (Tail)"); // add to tail
        deque.addFirst("Element 2 (Head)");
        deque.addLast("Element 3 (Tail)");
        deque.push("Element 4 (Head)"); //add to head
        deque.offer("Element 5 (Tail)");
        deque.offerFirst("Element 6 (Head)");
        deque.offerLast("Element 7 (Tail)");

        System.out.println("Deque elements: ");
        System.out.println(deque);
        System.out.println("*********************************************");
        // Iterate through the queue elements.
        System.out.println("Iterating over Deque with Standard Iterator");
        Iterator iterator = deque.iterator();
        while (iterator.hasNext()) {
            System.out.println("\t" + iterator.next());
        }
        System.out.println("*********************************************");

        // Reverse order iterator
        Iterator reverse = deque.descendingIterator();
        System.out.println("Iterating over Deque with Reverse Iterator");
        while (reverse.hasNext()) {
            System.out.println("\t" + reverse.next());
        }
        System.out.println("*********************************************");

        // Peek returns the head, without deleting it from the deque
        System.out.println("Peek into the Deque" + deque.peek());
        System.out.println("After peek: \n");
        System.out.println(deque);
        System.out.println("*********************************************");

        // Pop returns the head, and removes it from the deque
        System.out.println("Pop from Deque" + deque.pop());
        System.out.println("After pop: \n");
        System.out.println(deque);
        System.out.println("*********************************************");

        // We can check if a specific element exists in the deque
        System.out.println("Contains element 3: " + deque.contains("Element 3 (Tail)"));
        System.out.println("*********************************************");
        // We can remove the first / last element.
        deque.removeFirst();
        deque.removeLast();
        System.out.println("Deque after removing first and last: " + deque);
    }
}

Output

DequeExample output

Follow below instructions to run the program,

  • Copy java code and save it as DequeExample.java in a directory of your choice
  • Open command prompt, navigate to the directory where java file is saved and run the command javac DequeExample.java
  • The previous step generates a .class file. To run the program, run command java DequeExample (Note that, no extension is specified)

2. Method explanation

Now we will explain the usage of the methods presented in the example above. Some of them exist in the standard LinkedList implementation, so we mostly used Deque-specific methods, that have to do with the element insertion/removal from the head and the tail of the Deque.

Deque methods can be summarized as,

First Element – Throws ExceptionFirst Element – Special ValueLast Element – Throws ExceptionLast Element – Special Value
InsertaddFirst(e)offerFirst(e)addLast(e)offerLast(e)
RemoveremoveFirst()pollFirst()removeLast()pollLast()
ExaminegetFirst()peekFirst()getLast()peekLast()

Each of the Deque method explanation is given below,

Return typeFunctionDescription
boolean add(E e)Inserts an element to the queue. Returns true upon success, otherwise throws an IllegalStateException
voidaddFirst(E e)Inserts specified element to the front of queue
void ddLast(E e)Inserts specified element at the tail of the queue
Iterator<E>descendingIterator()Returns an iterator over the queue in reverse order
Eelement()Retrieves head of the queue, but doesn’t remove the item
EgetFirst()Retrives but doesn’t remove the first element
EgetLast()Retrieves but doesn’t remove the last element
Iterator<E>iterator()Returns an iterator over the elements
boolean offer(E e)Inserts an element at the front of the queue. returns true on success, if space isn’t available returns false
booleanofferFirst(E e)Inserts an element at the front of the queue. Returns true on success, if space isn’t available returns false.
booleanofferLast(E e)Inserts an element to the end of the queue. Returns true on success, if space isn’t available returns false.
Epeek()Returns head of queue or returns null if queue is empty
EpeekFirst()Returns the first element of the queue. If the queue is empty, then returns null
EpeekLast()Returns last returns null. element of queue, if empty
Epoll()Retrieves and removes the head of the queue. Returns null if queue is empty.
EpollFirst()Retrieves and removes the first element of the queue. Returns null if queue is empty.
EpollLast()Retrieves and removes the last element of the queue. Returns null if queue is empty.
Epop()Pops an element from the stack represented by this deque
voidpush(E e)Pushes an element to the stack represented by this deque. Throws a IllegalStateException if the queue is empty.
Eremove()Retrieves and removes an element from the deque
booleanremove(Object o)Removes specified object from the queue
EremoveFrist()Retrieves and removes the first element from the queue
booleanremoveFirstOccurence(Object o)Removes the first occurrence of the specified object from the queue
EremoveLast()Retrieves and removes the last element from the queue
booleanremoveLastOccurence(Object o)Removes the last occurence of the specified object
intsize()Returns number of elements in the queue

Apart from these methods, java.util.Deque inherits a number of methods from java.util.Collection interface.

3. Use cases for Deque

Below are some use cases to use java.util.Deque,

  • Deque can be used to implement Stack, Queue, and List.
  • Deque can be used to implement priority queues.
  • implement undo or history – each new item is inserted at the front of the queue and older item can be removed from the tail of the queue.
  • Can be used to implement recursive processes.

4. Considerations

  • Deque is not threadsafe. Hence, can’t be used in concurrent processing.
  • Null items can’t be inserted to Deque.

5. Download the Source Code

In this section, I have provided a link to download the example program.

Download
You can download the full source code of this example here: java.util.Deque – Deque Java Example

Last updated on Sept. 12, 2019

Ilias Koutsakis

Ilias has graduated from the Department of Informatics and Telecommunications of the National and Kapodistrian University of Athens. He is interested in all aspects of software engineering, particularly data mining, and loves the challenge of working with new technologies. He is pursuing the dream of clean and readable code on a daily basis.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments
Back to top button