Java

Java Deque

A queue in computing is a first-in_first-out (FIFO) list data structure. This means to add a new element, the element is enqueued at the back of the list; and to remove an element, the element is dequeued from the front of the list. The front element can also be peeked, meaning reading it but not removing it.

A stack in computing is a last-in_first-out (LIFO) list data structure. This means to add a new element, the element is pushed to the front of the list; and to remove an element, the element is pop out from the front of the list. The front element can also be peeked, meaning reading it but not removing it.

The name “deque” is the short form for “double-ended queue”, pronounced “deck”. The deque is a FIFO and a LIFO list data structure in Java. Well, also in Java, the deque is an Interface from which classes can be implemented. Java already has the following classes implemented: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList. The ArrayDeque class has been chosen to be studied in this article.

The following are Java ArrayDeque corresponding methods for queue:

Queue ArrayDeque
enqueue add
dequeue remove
peek peek

The following are Java ArrayDeque corresponding methods for stack:

Stack ArrayDeque
push push
pop pop
peek peek

Note: The peek() method is the same for both behaviours. Also, remove() and pop() are very similar; they are explained below.

Constructing an ArrayDeque

The ArrayDeque class is in the java.util.* package, which has to be imported. It has three constructors, two of which are explained here.

public ArrayDeque()
This creates an empty deque, as the following code segment shows:

            ArrayDeque<Character> dq = new ArrayDeque<Character>();
            dq.add('F'); dq.add('G'); dq.add('H'); dq.add('I'); dq.add('J');

Five elements were added. The name of the deque here is, dq.

public ArrayDeque(Collection<? extends E> c)
This overloaded constructor, creates a deque from another deque. The following code segment illustrates this:

            ArrayDeque<Character> dq = new ArrayDeque<Character>();
            dq.add('F'); dq.add('G'); dq.add('H'); dq.add('I'); dq.add('J');

            ArrayDeque<Character> dq1 = new ArrayDeque<Character>(dq);

dq1 has been created from dq.

Methods of the ArrayDeque Class

public boolean add(E e)
This is the equivalent of enqueue. It adds an element at the end of the deque. The following program illustrates this:

    import java.util.*;
    public class TheClass {
        public static void main(String[] args) {
            ArrayDeque<Character> dq = new ArrayDeque<Character>();
            dq.add('F'); dq.add('G'); dq.add('H'); dq.add('I'); dq.add('J');
        }
    }

public int size()
This returns the size (length) of the deque. The following program illustrates this:

    import java.util.*;
    public class TheClass {
        public static void main(String[] args) {
            ArrayDeque<Character> dq = new ArrayDeque<Character>();
            dq.add('F'); dq.add('G'); dq.add('H'); dq.add('I'); dq.add('J');

            int sz = dq.size();

            System.out.println(sz);            
        }
    }

The output is 5.

public E remove()
This is the equivalent of dequeue. It removes an element from the front of the list. The following program illustrates this:

    import java.util.*;
    public class TheClass {
        public static void main(String[] args) {
            ArrayDeque<Character> dq = new ArrayDeque<Character>();
            dq.add('F'); dq.add('G'); dq.add('H'); dq.add('I'); dq.add('J');

            char ch1 = dq.remove(); char ch2 = dq.remove(); char ch3 = dq.remove();
            char ch4 = dq.remove(); char ch5 = dq.remove();

            System.out.print(ch1); System.out.print(' '); System.out.print(ch2); System.out.print(' ');
            System.out.print(ch3); System.out.print(' '); System.out.print(ch4); System.out.print(' ');
            System.out.print(ch5); System.out.print(' ');
            System.out.println();
        }
    }

The output is:

    F G H I J

showing a FIFO behavior.

public E peek()
This reads the element at the front of the deque without removing it. The following program illustrates this:

    import java.util.*;
    public class TheClass {
        public static void main(String[] args) {
            ArrayDeque<Character> dq = new ArrayDeque<Character>();
            dq.add('F'); dq.add('G'); dq.add('H'); dq.add('I'); dq.add('J');

            char ch1 = dq.peek(); char ch2 = dq.peek(); char ch3 = dq.peek();
            char ch4 = dq.peek(); char ch5 = dq.peek();

            System.out.print(ch1); System.out.print(' '); System.out.print(ch2); System.out.print(' ');
            System.out.print(ch3); System.out.print(' '); System.out.print(ch4); System.out.print(' ');
            System.out.print(ch5); System.out.print(' ');
            System.out.println();
        }
    }

The output is:

    F F F F F

indicating that nothing has been removed, and the first element has just been read five times.

public void push(E e)
This adds an element to the front of the deque. The following program illustrates this:

    import java.util.*;
    public class TheClass {
        public static void main(String[] args) {
            ArrayDeque<Character> dq = new ArrayDeque<Character>();
            dq.push('F'); dq.push('G'); dq.push('H'); dq.push('I'); dq.push('J');

            char ch1 = dq.remove(); char ch2 = dq.remove(); char ch3 = dq.remove();
            char ch4 = dq.remove(); char ch5 = dq.remove();

            System.out.print(ch1); System.out.print(' '); System.out.print(ch2); System.out.print(' ');
            System.out.print(ch3); System.out.print(' '); System.out.print(ch4); System.out.print(' ');
            System.out.print(ch5); System.out.print(' ');
            System.out.println();
        }
    }

The output is:

    J I H G F

showing a LIFO behavior.

public E pop()
This removes and returns the first element of the deque. The following program illustrates this:

    import java.util.*;
    public class TheClass {
        public static void main(String[] args) {
            ArrayDeque<Character> dq = new ArrayDeque<Character>();
            dq.push('F'); dq.push('G'); dq.push('H'); dq.push('I'); dq.push('J');

            char ch1 = dq.pop(); char ch2 = dq.pop(); char ch3 = dq.pop();
            char ch4 = dq.pop(); char ch5 = dq.pop();

            System.out.print(ch1); System.out.print(' '); System.out.print(ch2); System.out.print(' ');
            System.out.print(ch3); System.out.print(' '); System.out.print(ch4); System.out.print(' ');
            System.out.print(ch5); System.out.print(' ');
            System.out.println();
        }
    }

The output is:

    J I H G F

showing a LIFO behavior.

public void forEach(Consumer<? super E> action)
This forEach method can be used to access each element in the deque. The following program uses it to print all the elements in the deque:

    import java.util.*;
    public class TheClass {
        public static void main(String[] args) {
            ArrayDeque<Character> dq = new ArrayDeque<Character>();
            dq.push('F'); dq.push('G'); dq.push('H'); dq.push('I'); dq.push('J');

            dq.forEach((item) -> System.out.print(item + " "));
            System.out.println();
        }
    }

The output is:

    J I H G F

item is a dummy variable that represents each element in the deque. Note the way it has been used. Note the use of the arrow operator, -> . The iteration was done in reverse order.

Iterator<E> iterator()
This returns an iterator that can be used to remove an element within the deque. However, this action takes longer than removing an element at the front or back of the deque. The following statement would return the iterator for characters of a deque.

            Iterator<Character> iter = dq.iterator();

where iter is the iterator object, and dq is the deque object.

The iterator has the following methods:

boolean hasNext(): Returns true if the iteration has more elements.

E next(): Returns the next element in the iteration.

default void remove(): Removes from the list, the last element returned by this iterator (next).

Note that it does not have a method to insert an element within the deque.

Removing an Element within Deque

The following program removes ‘H’ in the middle of the deque list: F, G, H, I, J:

    import java.util.*;
    public class TheClass {
        public static void main(String[] args) {
            ArrayDeque<Character> dq = new ArrayDeque<Character>();
            dq.push('F'); dq.push('G'); dq.push('H'); dq.push('I'); dq.push('J');

            Iterator<Character> iter = dq.iterator();

            iter.next(); iter.next(); iter.next();
            iter.remove();

            dq.forEach((item) -> System.out.print(item + " "));
            System.out.println();
        }
    }

The output is:

    J I G F

Note that next() had to be called three times.

Conclusion

In Java, the deque is both a FIFO and LIFO collection. Deque in Java is actually an interface from which a class has to be implemented before the deque can be used. Fortunately, Java already has the following Deque implemented classes: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList. The operation for ArrayDeque has been explained above.

About the author

Chrysanthus Forcha

Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.