Java Deque Interface

Java Deque is a data structure that combines an ordinary Queue and Stack. You may add and remove elements both to the head and to the tail of the Deque. In the “traditional” queue you add elements to the tail of the line (after the last element) and remove elements from the head of the queue. This principle is called First In First Out (FIFO) and it works like any usual line of customers in real life. In Java Queue is an Interface, a part of the Collections Framework. There is also an important data structure called Stack, a list that works with elements in totally reverse principle, LIFO — last in, first out. It is similar to a stack of plates, adding or removing is only possible at the top.

Queue vs Deque

Deque is kinda weird type of Queue: you may add new elements both to the tail and the head of the line. The same story with removing: you may remove the last or the first element from this structure. Hence, it seems to be a mixture of Stack and Queue. The name “Deque” means “Double Ended Queue”. “Deque” is pronounced like a "deck" of cards and you know what? It is somewhat similar to a real deck of cards: you may take a card from the bottom or the top of such a deck. Want to add or remove elements from the both sides of some linear structure? Use Deque. Java 8 or almost any other version supports it. Imagine a typical lego brick and one-column “towers” made of the bricks. You can add a new brick to the top of the tower or to the bottom. You can also remove a brick from both sides. Here we have an example: we add all yellow bricks to the top and all reds to the bottom. We will demonstrate this example with Java code soon. So you can enqueue and dequeue from both ends of a Java Deque, that means you can use a Deque as both queue and stack. Read about Stack in Java: Java Stack 101: Delving into the Stack Class Read about Queue in Java: Java Queue Interface and its implementations

Deque’s features

• Deque in Java is an Interface, which implementations provide the support of a resizable array. So you have an array of restriction-free capacity and you can add new elements according to your needs.
• Сoncurrent access by multiple threads is not supported by Deque
• Deque is not thread-safe in case of the absence of external synchronization.
• No Null elements allowed in array deque.

Deque Java Interface declaration

public interface Deque<E> extends Queue<E>

Java Deque Methods

java.util.Deque is an Interface that extends Java Queue Interface and represents a double ended queue. So you can use all the Java Queue methods while working with a Deque. In spite of Deque doesn’t extending the Stack interface, the Deque interface defines methods that enable you to do typical stack operations such as push, peek and pop.

• boolean add(element) adds an element to the tail of the Deque. Returns true on success, throws an IllegalStateException if no space is currently available.
• addFirst(element) adds an element to the head of the Deque.
• addLast(element) adds an element to the tail of the Deque.
• offer(element) adds an element to the tail and returns a boolean to explain if the insertion was successful.
• offerFirst(element) adds an element to the head and returns a boolean to explain if the insertion was successful.
• offerLast(element) adds an element to the tail and returns a boolean to explain if the insertion was successful.
• iterator() returns an iterator for the deque.
• descendingIterator() returns an iterator that has the reverse order for this deque.
• push(element) adds an element to the head.
• pop(element) removes an element from the head and returns it.
• removeFirst() removes the element at the head.
• removeLast() removes the element at the tail.
• poll() retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty.
• pollFirst() retrieves and removes the first element of this deque, or returns null if this deque is empty.
• pollLast() retrieves and removes the last element of this deque, or returns null if this deque is empty.
• peek() retrieves, but does not remove, the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty.
• peekFirst() retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty.
• peekLast() retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty.

Here in the table below all methods are divided by groups. As you can see there are many different methods to add and to remove an element. For example, both removeFirst() and pop() remove the first element from deque. The second one “came” from stack. That means if you use your ArrayDeque as a stack only, use pop() to remove, push() to add and peek() to examine. This makes your code more sensible for other developers.

Deque Implementations

Java Deque is an interface and has implementations in Java Collections API:

• java.util.LinkedList //List and Deque implementation
• java.util.ArrayDeque //Deque implementation, Java library

The LinkedList class uses a double-linked list internally to model a queue or a deque. ArrayDeque class stores the elements internally in an array. If the number of elements exceeds the volume of the array, a new array is allocated, and all elements moved over. That means ArrayDeque grows by needs.

ArrayDeque class

ArrayDeque <E> class is a general two directional queue, inheriting functionality from the AbstractCollection class and using the Deque interface. ArrayDeque provides the facility of using deque and resizable-array. Initially, the array is initialized with size 16. It is implemented as a two-way queue, where it supports two pointers, namely the head and tail. It inherits AbstractCollection class and implements the Deque interface. The important points about ArrayDeque class are:

• You can add or remove elements from the tail and the head of the ArrayDeque
• Null elements are not allowed
• ArrayDeque is not thread safe, in the absence of external synchronization.
• ArrayDeque has no capacity restrictions.

ArrayDeque class Constructors

• ArrayDeque() creates an empty queue.
• ArrayDeque (Collection <? Extends E> collection) creates a queue filled with Collection collection elements.
• ArrayDeque (int capacity) creates a queue with initial capacity capacity. If you don’t specify the initial capacity, the default capacity is 16.

Java Deque Example — ArrayDeque

Remember the Lego Tower Example from the beginning of the article? Let’s create a class to Build one-column Towers made of Lego Bricks. Bricks can be red, yellow or blue. Our Tower building rule: we put the red bricks to the bottom and yellow bricks to the top. Big Java Deque Example

//enum with colors
public enum Color {
   RED, YELLOW, BLUE;
}

//class for the standard Lego Brick. You can connect or disconnect the Brick, it has color
public class LegoBrick {
   Color color;
   boolean isConnected;

   public void connect() {
       System.out.println("This brick is connected");
       this.isConnected = true;
   }

   public void disconnect() {
       System.out.println("Disconnected");
       isConnected = false;
   }

   public LegoBrick(Color color, boolean isConnected) {
       this.color = color;
       this.isConnected = isConnected;
   }

   public Color getColor() {
       return color;
   }

   public boolean isConnected() {
       return isConnected;
   }

   @Override
   public String toString() {
       return "LegoBrick{" +
              "color=" + color +
              ", isConnected=" + isConnected +
              '}';
   }
}

Here is our Tower class. We initiate a tower. The initiated tower depends on the quantity of reds and yellows. We can add brick to the tower or remove it. We add brick to the top if it is yellow and add it to the bottom if it is red.

import java.util.ArrayDeque;
public class LegoTower {
   ArrayDeque<LegoBrick> myTower;
   int quantityOfReds;
   int quantityOfYellows;

   public void addBrickToTower(LegoBrick newLegoBrick) {
       if (newLegoBrick.getColor() == Color.YELLOW) {
           this.myTower.offerLast(newLegoBrick);
           quantityOfYellows++;
       }
	//we can use addFirst(e)/push(e) instead of offerFirst here
       if (newLegoBrick.getColor() == Color.RED) {
           myTower.offerFirst(newLegoBrick);
           quantityOfReds++;
       }
   }

   public void removeBrickFromTower (LegoBrick legoBrick) {
       if (legoBrick.getColor() == Color.YELLOW) {
           this.myTower.removeLast();
           quantityOfYellows--;
       }
       if (legoBrick.getColor() == Color.RED) {
           myTower.removeFirst();
           quantityOfReds--;
       }
       legoBrick.isConnected = false;

   }

   public LegoTower(int quantityOfReds, int quantityOfYellows) {

       myTower = new ArrayDeque<>();
       this.quantityOfReds = quantityOfReds;
       this.quantityOfYellows = quantityOfYellows;
       for (int i = 0; i < quantityOfReds; i++) {
           LegoBrick redLegoBrick = new LegoBrick(Color.RED, false);
           myTower.addFirst(redLegoBrick);
           redLegoBrick.isConnected = true;
       }
       for (int i = 0; i < quantityOfYellows; i++) {
           LegoBrick yellowLegoBrick = new LegoBrick(Color.YELLOW, false);
           myTower.addLast(yellowLegoBrick);
           yellowLegoBrick.isConnected = true;
       }
   }

   public void setMyTower(ArrayDeque<legobrick> myTower) {
       this.myTower = myTower;
   }

   public void setQuantityOfReds(int quantityOfReds) {
       this.quantityOfReds = quantityOfReds;
   }

   public void setQuantityOfYellows(int quantityOfYellows) {
       this.quantityOfYellows = quantityOfYellows;
   }

   @Override
   public String toString() {
       return "LegoTower{" +
              "myTower=" + myTower +
              ", quantityOfReds=" + quantityOfReds +
              ", quantityOfYellows=" + quantityOfYellows +
              '}';
   }

   public void drawTower() {
       for (LegoBrick i : myTower) {
           System.out.println(i.color);
       }
   }
}


public class Main {
   public static void main(String[] args) {
       LegoBrick legoBrick1 = new LegoBrick(Color.YELLOW, false);
       legoBrick1.connect();
       System.out.println(legoBrick1.toString());
       legoBrick1.disconnect();
       System.out.println(legoBrick1.toString());
       LegoBrick legoBrick2 = new LegoBrick(Color.YELLOW, false);
       LegoBrick legoBrick3 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick4 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick5 = new LegoBrick(Color.YELLOW, false);

       LegoTower legoTower = new LegoTower(2, 5);
       System.out.println("my Initiated Lego Tower: ");
       legoTower.drawTower();
       legoTower.addBrickToTower(legoBrick1);
       legoTower.addBrickToTower(legoBrick2);
       legoTower.addBrickToTower(legoBrick3);
       legoTower.addBrickToTower(legoBrick4);
       legoTower.addBrickToTower(legoBrick5);
       System.out.println("My LegoTower after adding some elements: ");
       legoTower.drawTower();
       legoTower.removeBrickFromTower(legoBrick1);
       legoTower.removeBrickFromTower(legoBrick3);
       System.out.println("We removed one red and one yellow brick:");
       legoTower.drawTower();

   }

}

The result of running this program:

my Initiated LegoTower:

RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
My LegoTower after adding some elements: 
RED
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
We removed one red and one yellow brick:
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW

Process finished with exit code 0

Wait, what?? Why are the reds on the top? Nope, they don’t. They just printed out to the consol starting from the first (bottom) to the last (top). So if you want to see something like in the picture with the bricks above, you may change the drawTower method of the LegoTower class. It is a very easy task!

LinkedList

The List interface keeps the sequence of adding items and allows access to the item by index. Deque is a two-way queue, and it supports adding and removing elements from both sides. LinkedList is mainly known as a List implementation, but also this class implements the Deque, and it allows us to create a bidirectional queue consisting of any objects including null. LinkedList is a collection of elements. We can see it in the code source of the class, this time pay attention to the fields: Here we add one example, but if you want to learn more about LinkedList, welcome to this CodeGym article.

Linked list implementation in Java, adding and removing elements. Example

Let’s try these operations out in practice. First, Java LinkedList implementation: creating a LinkedList of Strings, adding there 3 elements. Then remove one, then add one in the middle.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<string> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

The result of running this program:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]