The Queue in Java

In this post we learn how to implement a queue in Java using the linked list and priority queue data structures provided by Java.

What is a Queue in Java?

A queue is a data structure in Java and many other programming languages. Elements are added according to the FIFO (first-in, first-out) principle. An element is enqueued at the end of the queue and dequeued at the beginning of the queue. A queue is an abstract data type. This means that it only provides an interface and defines behavior but doesn’t provide a concrete implementation. A queue is usually implemented using a linked list or a priority queue in Java. Those are concrete data types.

Java Queue Methods

The queue interface provides the following operations:

• Enqueue an element to the end of the queue
• Dequeue an element from the beginning of the queue
• Retrieve the first element in a queue but do not remove it
• Retrieve the last element in a queue but do not remove it

How to Create a Queue in Java: The Linked List Option

A common way to implement queues is via the LinkedList Java data structure. In a linked list elements are not stored in a contiguous manner but each element contains a reference to the next element and its location in memory. This makes adding elements to the end of the queue and removing them from the beginning very fast.

To create a queue using a linked list, we initialize the LinkedList and assign it to a variable of type queue. We can do that since the linked list conforms to the queue interface in Java

Queue queueLL = new LinkedList();

Since the advent of Java generics, you can also type constrain the queue.

Queue<Integer> queueLL = new LinkedList<Integer>();

I highly encourage you to do that if possible because it makes your code less error-prone. Every other component in the system retrieving elements from the queue now knows that it can expect an integer. There is no need for type checking and casting.

Add Elements to the Java Queue

To add elements the Java queue interface offers the two options “offer” and “add”. They both behave in a similar manner when adding elements to the queue. The only difference in behavior emerges when the queue is full. Then, the add method will throw an exception whereas the offer method simply returns false, indicating that the element has not been added. In the case of the linked list, this distinction is irrelevant because linked lists are not size-limited. In other data structures like arrays, memory for items is allocated when the data structure is initialized. Therefore, Java needs to know the number of elements the array can contain. In linked lists, memory allocation happens as items are added, so length limitation doesn’t make sense

Accordingly, you can use any method you like.

Queue<Integer> queueLL = new LinkedList<Integer>();
queueLL.add(1);
queueLL.offer(3);

Poll Elements From the Java Queue

For removing elements from the queue, the Java queue interface offers the “remove” and the “poll” methods. Both methods remove and subsequently return an element from a queue. The only difference in behavior is that when called on an empty queue, “poll” returns null, whereas “remove” throws an exception.

Queue<Integer> queueLL = new LinkedList<Integer>();

System.out.println(queueLL.poll());
System.out.println(queueLL.remove());

When the queue contains elements, they are polled or removed in first-in, first-out order.

Queue<Integer> queueLL = new LinkedList<Integer>();

queueLL.add(1);
queueLL.add(2);
System.out.println(queueLL.poll());
System.out.println(queueLL.remove());

To remove all elements from the queue you can use the clear method.

queueLL.clear();

Peek at the First Element in the Java Queue

If you just want to retrieve the first element in the queue without removing it, the Java queue interface offers the “element” and the “peek” methods. Calling an element on an empty queue results in an exception whereas the peek method returns null without throwing an exception.

Queue<Integer> queueLL = new LinkedList<Integer>();

System.out.println(queueLL.peek());
System.out.println(queueLL.element());

Use the Java Queue Iterator

Java Queue implements the iterator interface. To iterate through the queue, we can define an iterator object and use it to iterate through the queue.

Iterator<Integer> it = queueLL.iterator();
while(it.hasNext()){
    Integer item = it.next();
    System.out.println(item);
}

Checking Java Queue Length

The queue interface offers a method to retrieve the current number of elements contained in the queue.

queueLL.size()

Check Elements Contained in the Java Queue

The method “contains” allows you to check whether an element is contained in the queue returning the boolean true if the element is present and false if it is not.

Queue<Integer> queueLL = new LinkedList<Integer>();

queueLL.add(1);
queueLL.add(2);

System.out.println(queueLL.contains(2));

How to Create a Queue in Java: The Priority Queue Option

Instead of using a linked list, we can also use a priority queue to create a concrete implementation of the queue. Like the linked list, the priority queue conforms to Java’s queue interface and we can assign the instantiated priority queue to a variable of type queue.

Queue queuePQ = new PriorityQueue();

#type constrained priority queue
Queue<Integer> queuePQ = new PriorityQueue<Integer>();

Accordingly, we are now dealing with the queue interface and the methods we can call are exactly the same as for the linked list. For the consumer calling these methods, there is no difference between the linked list and the priority queue if he is interacting with them through the queue interface.

There are some underlying differences that you should keep in mind when choosing which implementation to use.

First of all, the priority queue orders items according to priority. By default, it orders items numerically and alphabetically in ascending order. Contrary to the linked list, you won’t get the items in the same order as you’ve added them.

Furthermore, you can also limit the length of the linked list when you initialize it.

Queue queuePQ = new PriorityQueue(3);

Note on the Priority Blocking Queue

PriorityQueue and LinkedList are fine if the queue is used by one thread. If your queue needs to be thread-safe, the priority blocking queue is an option to consider. For a guide to the priority blocking queue, I recommend checking out this article on Baeldung.