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:
In this case, we can infer that the customers arrived at the queue in this order:
- George
- Nikolaos
- Mauricio
- 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 exceptionoffer(E e)
– adds an element to the queue, does not throw an exception even if the queue is at capacityremove()
– removes the head(or the item with the highest priority) of the queue, throws exception if queue is emptypoll()
– does the same asremove()
but does not throw an exception if the queue is emptyelement()
– returns the head of the queue without removing it and it throws an exception if the queue is emptypeek()
– same aselement()
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 fullClassCastException
– Should the class of the element you tried to add cannot be added to this queueNullPointerException
– If the implementation forbids null elementsIllegalArgumentException
– 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)
andcontains(Object)
haveO(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 likeConcurrentLinkedQueue
but it can be optionally bounded.LinkedBlockingDeque
– Just likeConcurrentLinkedDeque
but it can be optionally bounded.LinkedTransferQueue
– A transfer queue backed by a singly-linked listPriorityBlockingQueue
– A boundless blocking queue with the same logic asPriorityQueue
.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