You Learn Code

Java Queue

Java Queue

—

by

geonikpal
in

In this article, we’ll go through Java Queue Interface, and how to use it.

1. What is a Java Queue?

A Java Queue is a FIFO(First-In-First-Out) data structure which means that the oldest item will be the first item that we will be able to remove from the queue. Moreover, as you should have already guessed, insertion order is maintained in queues.

An example of a real-life queue would be a queue at a supermarket checkout counter:

Java Queue Supermarket
Figure 1 – Supermarket Queue

In this case, we can infer that the customers arrived at the queue in this order:

  1. George
  2. Nikolaos
  3. Mauricio
  4. Akis

Then, each customer will pay when all customers that came before him/her have already finished the transaction.

As for the Java representation of the Queue, it is just an interface and has the following abstract methods:

  • add(E e) – adds an element to the queue, if the queue is at capacity, it will throw an exception
  • offer(E e) – adds an element to the queue, does not throw an exception even if the queue is at capacity
  • remove() – removes the head(or the item with the highest priority) of the queue, throws exception if queue is empty
  • poll() – does the same as remove() but does not throw an exception if the queue is empty
  • element() – returns the head of the queue without removing it and it throws an exception if the queue is empty
  • peek() – same as element() but does not throw any exception

Of course, we will see detailed examples for every method in the following sections

2. Java Queue Example

For this example, we will use the LinkedList implementation ofQueue interface:

Queue<String> queue = new LinkedList<>();

// Add 4 elements to the queue
queue.add("George");
queue.add("Nikolaos");
queue.offer("Mauricio");
queue.offer("Akis");

//Remove George using poll
String george = queue.remove();

//Remove Nikolaos using poll
String nikolaos = queue.poll();

//Check the head of queue using element()
String mauricio = queue.element();

//Remove mauricio
queue.remove();

//Check the head of queue using peek()
String akis = queue.peek();

// Remove Akis
queue.remove();


// Both of this will throw exceptions
// since the queue is empty
try {
    queue.remove();
} catch (NoSuchElementException e) {
    e.printStackTrace();
}

try {
    String el = queue.element();
} catch (NoSuchElementException e) {
    e.printStackTrace();
}

In the example above, we added two elements using add() and two using offer(). Then we removed some elements using remove(), poll() and we checked without altering the queue by using the element() and peek(). Finally, we tried to use remove() and element() on an empty queue and saw that indeed 2 exceptions were thrown, as expected.

3. How to Create a Queue in Java

Since Queue is just an interface, you must choose the implementation in order to create a new Queue.

For example, you can choose LinkedList:

Queue<String> cars = new LinkedList<>();
//or
Queue<String> cars = new LinkedList<>(Arrays.asList("Opel", "VW"));

If the application requires a queue with custom priority logic and not just FIFO, you can use PriorityQueue to create a Queue:

// Natural order PriorityQueue
Queue<String> cars = new PriorityQueue<>();
// Natural order PriorityQueue with initialCapacity 10
Queue<String> cars = new PriorityQueue<>(10);
// Comparator-specified order PriorityQueue
Queue<String> cars = new PriorityQueue<>(Comparator.reverseOrder());

To sum up, you must choose an implementation in order to create a queue, according to the needs of your application.

4. Java Queue Methods

In this section, we’ll take a deeper look at the methods we briefly discussed in the previous sections

4.1 Java Queue Offer & Add

offer() and add() are quite similar, since they both have the same use case, to add an element to the queue.

However, add() will throw an exception if the queue is full; an example of an implementation that does specify a max capacity is ArrayBlockingQueue:

Queue<String> queue = new ArrayBlockingQueue<>(1);

queue.offer("YLC");

// This will fail but not throw any exception
boolean wasInserted = queue.offer("YLC");
// This will throw an exception
queue.add("YLC");

The above will print:

Was 2nd element inserted? false
Exception in thread "main" java.lang.IllegalStateException: Queue full
	at java.base/java.util.AbstractQueue.add(AbstractQueue.java:98)
	at java.base/java.util.concurrent.ArrayBlockingQueue.add(ArrayBlockingQueue.java:329)
	at Main.main(Main.java:24)

Finally, both return a boolean that is true if the addition succeeded and false if not. As for possible exceptions:

add() may throw:

  • IllegalStateException – If the queue is full
  • ClassCastException – Should the class of the element you tried to add cannot be added to this queue
  • NullPointerException – If the implementation forbids null elements
  • IllegalArgumentException – Should any property lead to failure of insertion

While offer() may throw all of them but the first.

4.2 Java Queue Poll & Remove

In the same fashion, both methods fulfill the same purpose, they remove elements from the queue.

Of course, the difference is that remove() will throw an exception if the queue is empty while poll() will not:

Queue<String> queue = new LinkedList<>();

// s is null
String s = queue.poll();

// throws NoSuchElementException
queue.remove();

Finally, both of them will return the element that was removed if they succeed.

4.3 Java Queue Peek & Element

Last but not least, these two methods will retrieve the head of the queue without removing it. Just like the previous two methods, element() will throw NoSuchElementException if the queue is empty while peek() will just return null :

Queue<String> queue = new LinkedList<>();

// s is null
String s = queue.peek();

// throws NoSuchElementException
queue.element();

5. Java Queue Implementations

In this section, we’ll take a brief look at the most commonly used implementations of Queue .

5.1 LinkedList

This is the linked list implementation of the Dequeue(Double-ended Queue) interface that extends Queue and uses nodes that have one pointer for the next item and one for the previous.

To learn everything about LinkedList class, you should read Java LinkedList.

5.2 PriorityQueue

This implementation should be used when you do not want to poll items based on the insertion order but are given a custom priority based on some characteristics. Moreover, internally it uses an object array to hold the data and it represents a balanced binary heap. Furthermore, this implementation does not allow null elements.

With regard to time complexity:

  • offer, add, remove() and poll have O(log(n) time complexity
  • While remove(Object) and contains(Object) have O(n) time complexity

Last but not least, when you do use any of the methods used to remove or retrieve elements(remove(), poll() and element(), peek() respectively), the highest priority item will be retrieved.

For example, let’s say you have a queue of people waiting at a public service but you want to prioritize the elderly. You could use a PriorityQueue like this:

Queue<Citizen> queue = new PriorityQueue<>(Comparator.comparing(Citizen::age).reversed());

queue.add(new Citizen("AD7484", 20));
queue.add(new Citizen("AD7474", 80));
queue.add(new Citizen("AD7584", 45));
queue.add(new Citizen("AD7284", 65));
queue.add(new Citizen("AD7285", 32));

System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());

// Citizen record
public record Citizen(String id, int age){};

Of course, the above will print:

Citizen[id=AD7474, age=80]
Citizen[id=AD7284, age=65]
Citizen[id=AD7584, age=45]
Citizen[id=AD7285, age=32]
Citizen[id=AD7484, age=20]

As a final note, to traverse a priority queue, Java 8 forEach, for loop, for each loop or iterators can not guarantee the correct order. However, you can do it like this:

Citizen[] sorted = queue.toArray(i -> new Citizen[0]);
Arrays.sort(sorted);

for (Citizen citizen : sorted) {
    System.out.println(citizen);
}

// the Record must implement Comparable
// according to descending age order logic
public record Citizen(String id, int age) implements Comparable<Citizen> {

    @Override
    public int compareTo(Citizen o) {
        return Integer.compare(o.age, this.age);
    }
}

As a result, if we run the snippet above, it will print:

Citizen[id=AD7474, age=80]
Citizen[id=AD7284, age=65]
Citizen[id=AD7584, age=45]
Citizen[id=AD7285, age=32]
Citizen[id=AD7484, age=20]

This means that you can’t use the queue directly to print all the elements in the correct order but you have to do it by converting the queue to an array and then sorting it.

5.3 ArrayDeque

This is the array implementation of a double-ended queue and uses a resizable array of type Object internally.

Finally, this implementation might lead to better performance than that of LinkedList.

5.4 Synchronized Implementations

Before we begin, a BlockingQueue is an implementation of the Queue that has additional operations so it will be able to handle insertions and removals in an efficient way while multiple threads are trying to add and remove elements.

Moreover, there is a more specific type of blocking queue, the TransferQueue, that waits for consumers to receive elements and it may be useful in messaging applications when producers want a confirmation that a message was actually received by a consumer.

Finally, before we dive into the synchronized implementations of Queue, there are 3 types of queues based on the boundary:

  • A queue with a mandatory boundary(you cannot create it without specifying a maximum capacity)
  • A queue with an optional boundary(you can specify a maximum capacity or have limitless capacity)
  • A queue without any boundaries

Now let’s explain briefly all the synchronized implementations:

  • ArrayBlockingQueue – A blocking and fixed-capacity queue(mandatory boundary) that is backed by an array.
  • ConcurrentLinkedDeque – A thread-safe double-ended queue without any bounds, backed by a doubly-linked list.
  • ConcurrentLinkedQueue – A thread-safe queue without any bounds, backed by a linked list with nodes that only point to the next element.
  • DelayQueue – An unbounded blocking queue in which an element can be taken only after the expiration of its delay.
  • LinkedBlockingQueue – Just like ConcurrentLinkedQueue but it can be optionally bounded.
  • LinkedBlockingDeque – Just like ConcurrentLinkedDeque but it can be optionally bounded.
  • LinkedTransferQueue – A transfer queue backed by a singly-linked list
  • PriorityBlockingQueue – A boundless blocking queue with the same logic as PriorityQueue .
  • SynchronousQueue – A zero-capacity blocking queue that blocks upon insertion until the consumer receives the element. Likewise, the consumer blocks until a message is available.

6. When to Use a Queue

First of all, you should use a classic queue(LinkedList or ArrayDeque implementation) when you want FIFO logic in your application.

On the other hand, you should use the PriorityQueue implementation, if you’d like to poll or just peek at elements from the queue based on some custom criteria and not just insertion order.

Last but not least, if you are in a multithreaded environment and you want FIFO or any custom ordering logic, you should use any of the implementations that we described before, based on the requirements of your application.

7. Conclusion

After reading this article, you should have a basic understanding of what is a Queue, how it is implemented in Java, and what options you have regarding the implementations of the Queue interface. Moreover, you will be able to choose an implementation that suits the needs of the application you are trying to build.

8. Sources

[1]: The Queue Interface (The Java™ Tutorials > Collections > Interfaces) – Oracle

[2]: Queue (Java SE 11 & JDK 11 ) – Oracle

[3]: Queue Implementations (The Java™ Tutorials > Collections > Implementations) – Oracle