Queue

For most people, the word "queue" brings to mind very few pleasant associations. But today we're talking about different queues — Java queues. In Java, a queue is anything that inherits the Queue interface, which in turn extends the Collection interface. That means that queues can be treated like collections.

Queues in Java support two operating principles: FIFO and LIFO.

The FIFO (First In, First Out) principle governs a regular queue — the first element added to the queue is the first to leave it.

The LIFO (Last In, First Out) principle describes the behavior of a stack — the last element added to the queue is the first to leave it. For example, this is how you work with a deck of cards: you take cards off of the top one at a time until you reach the bottom of the deck.

The Queue hierarchy in Java looks like this:

Here you can see that Queue has 3 implementation classes: LinkedList, ArrayDeque and PriorityQueue. LinkedList and ArrayDeque directly inherit not Queue, but Deque.

Deque is an interface that was added in Java 6. It includes several methods that are useful for queues and allows a queue to function as a double-ended (or bidirectional) queue. That means it can be FIFO and LIFO.

One of the Deque interface's two descendants is ArrayDeque. It supports a doubled-ended queue that lets you insert and remove elements from both ends. It is also a dynamic array that automatically grows in size.

There is also a PriorityQueue class, which is a direct descendant of Queue: it behaves differently than the classes that implement Deque.

PriorityQueue is a priority queue that organizes elements according to their natural ordering by default. Here the sorting uses the Comparable and Comparator interfaces. The principle is the same as with TreeSet or TreeMap — classes that use the Comparable interface and have their own sort order.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

If you run this example, here's what you'll see in the console:

Since we are working with queues and not regular collections, we need to remove the elements from the list. To do this, we use this construct:

while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

The Deque interface inherits the Queue methods and adds several of its own interesting methods:

Let's now look at a few of these methods in practice.

First, let's add an element to a queue:

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); // Adds "Apple" to the end of the queue
        deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
        deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue

        System.out.println(deque);

Now let's get values from a queue:

Deque<String> deque = new ArrayDeque<>();

deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");


        System.out.println("The first element is: "+ deque.getFirst());

        System.out.println("The last element is: " + deque.getLast());

    }

This code displays the first and last element of the queue.

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");
        deque.add("Lemon");

System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue

System.out.println(deque);

Running this code, we get:

The difference between pop() and poll() is that pop() will throw a NoSuchElementException if the list is empty list, but poll() will return null.

Now we'll consider the pollFirst() and pollLast() methods.

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
System.out.println(deque);

Both methods return and remove a value from the queue.

Here's an example of using the peekFirst() and peekLast() methods:

Deque<String> friends = new ArrayDeque<>();

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);

Both methods return the first/last element from the queue and do not remove them. If the queue is empty, null will be returned.

Well done! Today we learned how to work with queues in Java. Now you know how to use them in practice.