Java Collections: Queue and Deque Interfaces

Introduction

The Java Collections Framework is a fundamental and essential framework that any strong Java developer should know like the back of their hand.

A Collection in Java is defined as a group or collection of individual objects that act as a single object.

There are many collection classes in Java and all of them extend the java.util.Collection and java.util.Map interfaces. These classes mostly offer different ways to formulate a collection of objects within a single one.

Java Collections is a framework that provides numerous operations over a collection - searching, sorting, insertion, manipulation, deletion, etc.

This is the fourth and final part of a series of articles on Java Collections:

• The List Interface
• The Set Interface
• The Map Interface
• Queues, Deques, Stacks (you are here)

Queue

Let's start this final article of the series with the java.util.Queue interface.

Principle

First of all, what's it good for? The Queue is designed to hold elements prior to their processing. Some can be of a fixed capacity, meaning they can contain only up to a certain number of elements.

So, the idea is to push some elements into a Queue, and then retrieve them afterwards. Generally, queues are returning elements respecting the First-In First-Out (FIFO) pattern, meaning the oldest element of the queue is returned first, then the oldest after that, etc.

You can think of FIFO as a line in front of a store. The first one to stand in the line is the first one to enter.

But there can be other implementations which respect the Last-In First-Out (LIFO) pattern, or even answer to some kind of priority system (e.g. using Comparator).

You can think of LIFO as a stack of coins. The last one to be put on the top of the stack is the first one to be taken off.

Let's now explore the features of the Queue interface!

Adding an Element

We'll begin by adding an element to a Queue. First, let's instantiate one using the ArrayDeque implementation, which also implements the Deque interface we'll cover later:

Queue<Integer> queue = new ArrayDeque<>();

In order to add an element in this Queue, we have two possibilities: the add() method or the offer() method.

Let's start with the former:

queue.add(3);

And with the latter:

queue.offer(4);

Both return a boolean value indicating if the element was added to the Queue or not, according to its capacity (if it applies). What's the difference between both methods then?

Well, the first will in fact never return false, rather throwing an Exception when adding an element to a full Queue. On the other hand, the second one will return false in such cases.

Instead of ArrayDeque, which is unbounded, let's use the LinkedBlockingQueue which can be assigned a capacity:

Queue<Integer> queue = new LinkedBlockingQueue<>(1);

Here, we've instantiated a queue which can hold a maximum of one element at a time. Therefore, we can't use the add() method two times consecutively without having an exception:

queue.add(3);
queue.add(4);

Trying to add these two elements will result in:

java.lang.IllegalStateException: Queue full
    at java.base/java.util.AbstractQueue.add(AbstractQueue.java:98)

On the other hand, using the offer() method instead will do nothing and return false as a result.

Retrieving an Element

As stated earlier, a Queue generally respects FIFO, which means that it'll return the first entered element first, if we're retrieving one.

The interface offers a few methods to retrieve elements. Two of them, remove() and poll(), remove the element before returning it. The two others, element() and peek() just return it but don't remove it.

The remove() and element() methods will throw an exception when called on an empty Queue:

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(3);
queue.offer(4);

queue.poll();
queue.peek();

Here, our we'll gather the elements 3 and 4, but the first time the element will be removed (via poll()), and the second time not (via peek()), leaving our queue with element 4 in it.

Using remove() and element() instead of poll() and peek(), respectively, would've had the same results, as the queue is never empty in our case.

Iterating over Elements

Besides indexed while and for loops, the Queue interface implements Iterable and provides an Iterator, therefore making it eligible for the for-each loop:

for (Integer element: queue) {
    System.out.println(element);
}

That loop would print each element of the queue to the console.

Since Java 8, of course, there's the possibility to call the forEach() method, passing a Method Reference:

queue.forEach(System.out::println);

This achieves the same result as the previous loop.

If you'd like to read more about the Iterable Interface in Java, we've got you covered!

Implementations

Now, what are the classes that implements the Queue interface? There are several implementations of the interface, though these are really the most relevant ones:

• LinkedList: Although mainly known to be a List implementation, this class also implements the Queue interface. This implementation works by linking its elements together and going through that chain when iterating or searching for elements.
• ArrayDeque: An implementation of both Queue and Deque. Its backed up by an array, which can be increased when the number of elements increase over its current capacity.
• DelayQueue: Can only contain elements which implement the Delayed interface - elements that become active after a certain time. The DelayQueue will only deliver elements whose delays have expired.
• PriorityQueue: Orders its elements according to their natural order or a Comparator (if provided). This means it doesn't work using the FIFO principle, but rather returns the element with the highest priority (defined by how they compare to each other).

Let's imagine an anomaly system, with an enum defining their severity:

public class Anomaly implements Comparable<Anomaly> {
    private String log;
    private Severity severity;

    public Anomaly(String log, Severity severity) {
        this.log = log;
        this.severity = severity;
    }

    @Override
    public int compareTo(Anomaly o) {
        return severity.compareTo(o.severity);
    }

    private enum Severity {
        HIGH,
        MEDIUM,
        LOW
    }
}

Here, anomalies are naturally ordered by their severities (as enum are naturally ordered by their declaration order).

So, if we were to add two anomalies to a PriorityQueue without a Comparator, one LOW and one HIGH, then the poll() method would return the second anomaly first rather and the first one:

Queue<Anomaly> anomalies = new PriorityQueue<>();

Anomaly optionalInformationNotRetrievedAnomaly = new Anomaly("Couldn't retrieve optional information", Anomaly.Severity.LOW);
anomalies.offer(optionalInformationNotRetrievedAnomaly);

Anomaly databaseNotReachableAnomaly = new Anomaly("Couldn't contact database", Anomaly.Severity.HIGH);
anomalies.offer(databaseNotReachableAnomaly);

anomalies.poll(); // This would return 'databaseNotReachableAnomaly'

Now, if we pass a Comparator to the PriorityQueue constructor, let's say one that reverses the natural order:

Queue<Anomaly> anomalies = new PriorityQueue<>(Comparator.reverseOrder());

Then in the same scenario as before, the poll() method would return the first anomaly - that is optionalInformationNotRetrievedAnomaly.

Deque

Now that the Queue interface has been covered, let's jump to Deque.

Principle

Deque stands for Double Ended Queue, which means this is a queue that can be accessed by both ends, and therefore can be used with both FIFO and LIFO styles. By default, it organizes its element LIFO style, meaning that getting the first in the Deque would return the last that had been added.

Adding an Element

Let's jump to Deque usages with element insertion. There are multiple possibilities to achieve that:

• Some methods add the element at the top, some at the bottom
• Some methods throw an exception if the Deque is full, some don't

Let's summarize them in a table:

	Top	Bottom
No Exception	offerFirst()	offer(), offerLast()
Exception	addFirst(), push()	add(), addLast()

Let's say we have a Deque of Integer and we call addFirst() with integers 3 and 4:

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(3);
deque.addFirst(4);

Then, the deque will contain 4 and 3, in this order.

If we had used addLast(), then it would've contained 3 and 4, in this order. The same would've happened with offerFirst() and offerLast(), respectively.

Retrieving and Removing an Element

Now, let's see how to retrieve elements from a Deque. Again, there are multiple possibilities:

• Some methods return the first element, some return the last
• Some methods remove the element when returned, some don't
• Some methods throw an exception if the Deque is empty, some don't

To make it a bit easier, we're going to summarize that in a table as well:

	First (top) element, no removal	First (top) element, removal
No Exception	peek(), peekFirst()	poll(), pollFirst()
Exception	getFirst(), element()	remove(), removeFirst(), pop()

	Last (bottom) element, no removal	Last (bottom) element, removal
No Exception	peekLast()	pollLast()
Exception	getLast()	removeLast()

Let's say we have a Deque of Integer with elements 4 and 3, top to bottom. And we call peekFirst():

Deque<Integer> deque = new ArrayDeque<>();
deque.push(3);
deque.push(4);

deque.peekFirst();

Then, this would return 4, without removing the element. If we had used peekLast(), then it would've returned 3.

Now, if we were to use removeFirst() or pop(), we would got 4 but the Deque would only contain 3 in the end.

Iterating over Elements

As for the Queue, we can iterate using the standard mechanisms and the forEach() method. We just have to remember that, by default, the Deque organizes its elements LIFO style and therefore will iterate on them, top to bottom:

Deque<Integer> deque = new ArrayDeque<>();
deque.push(3);
deque.push(4);

deque.forEach(System.out::println);

This would print:

4
3

You could also use an Iterator:

Deque<Integer> deque = new ArrayDeque<>();
deque.push(3);
deque.push(4);

for (Iterator<Integer> iterator = deque.iterator(); iterator.hasNext();) {
    System.out.println(iterator.next());
}

This would also print:

4
3

Implementations

• ArrayDeque: This is the one we used for Queue and which is backed up by an array. Implements both Queue and Deque.
• LinkedList: Implements both Queue, Deque and List. We also see this one earlier.
• LinkedBlockingDeque: This one works a bit like the LinkedList, but can be bounded. Thus the insertion operations we saw earlier would throw an exception if this Deque was full.

Stack?

It's worth noting that a Stack exists as well. It was introduced in the beginning of Java and was to be used as a LIFO collection, with push() and pop() methods.

Why not use it then?

Because the documentation advise us to use the Deque interface which offers a more consistent API. Plus, Stack is subclass of Vector and thus is tightly bound to it, making it a List above all things, which is conceptually different from a stack.

Conclusion

The Java Collections Framework is a fundamental framework that every Java developer should know how to use.

In this article, we've talked about the Queue and Deque interfaces and covered their main operations. The full code for this article can be found over on GitHub.