Queues data structure in Java

April 3, 2020

by — Posted in Core Java

Hello! This post explores queues in Java and covers core queues operations.

Queue as a data structure

Before going to concrete implementations of queue data structure in Java, let review first a scientific definition of queue. In computer science, queue stands for a linear collection of elements that are inserted and removed based on FIFO principle. FIFO is First-in-First-out. In other words, element that was inserted first, will be removed first (unlike stacks, where first element is removed last).

Technically, queues support only two operations: enqueue and dequeue:

  • Enqueue means an insertion of an element into the back of the queue
  • Dequeue means a removing of an element from the front of the queue

The first front element is also called head and elements that are positioned after are called tail.

Work with queues in Java

Java supplies its own implementation of queue data structure as part of Java Collections Framework. There are two main implementations used ArrayDeque and PriorityQueue. The most important difference between these implementations is an order of elements. ArrayDeque holds elements on FIFO basis, so head element is the first inserted. PriorityQueue in its regard holds elements based on their natural ordering. Therefore, head element in this case will be the least element.

Enqueue

There are two main ways to handle enqueue operation. As Java queues are subclasses of java.util.Collection, they inherit common collection methods to insert and remove elements. When it comes to queues, they also provide own methods offer and poll, where the first one stands for adding elements. Both of these insertion methods insert an element into the tail.

Advice

Code examples in this post use AssertJ library to write fluent assertions. You can learn more on how to utilize AssertJ with Java Collections in this tutorial

Take a look on the code snippet below:

@Test
public void enqueueTest(){
    Queue<Person> people = new ArrayDeque<>();

    // people are inserted in the tail, so head is same

    people.offer(new Person("Alejandra", "Morales"));
    people.offer(new Person("Beatriz", "Sanchez"));
    people.offer(new Person("Carmen", "Hidalgo"));

    // head of queue is Alejandra Morales
    assertThat(people.peek()).isEqualTo(new Person("Alejandra", "Morales"));
}

What is a difference and when to use which one? Java recommends to use native queue methods, so for addition use offer method. Difference comes when it is not possible to insert a new element. In such situation:

  • offer returns false
  • add throws IllegalStateException

Special note must be made in a case of ArrayDeque. This class also inherits Deque – a collection that permits to add/remove elements on both ends compare to the classical queue. This adds some methods that are specific only for this class:

  • offerFirst and addFirst = insert an element to the head. Difference between them is same as between offer and add
  • offerLast and addLast = insert an element to the tail
  • push = is an equvalent for addFirst. On an insertion of null element throws NullPointerException

Handling dequeue operation

Removing an element in queue is called dequeue. As with addition, Java provides two methods to handle deletion of an element – one inherited from java.util.Collectionremove() and native for queues poll(). Both remove a head element (based on FIFO logic).

Here is an example of dequeue operation:

@Test
public void dequeueTest(){
    Queue<Car> cars = new ArrayDeque<>();
    cars.offer(new Car(4567, "Skoda Rapid"));
    assertEquals(4567, cars.peek().getLicensePlateNumber());
    cars.offer(new Car(1234, "Mazda 3"));
    cars.offer(new Car(2345, "Kia Cerato"));

    // remove previous head (Skoda) -> new head = mazda

    cars.poll();
    assertThat(cars.peek().getLicensePlateNumber()).isEqualTo(1234);
}

The difference between both methods is same with enqueue methods and Java recommends to stick with the native one method poll(). We also need to mention here methods that are inherited by ArrayDeque from Deque:

  • pollFirst and removeFirst = handle deletion of head element
  • pollLast and removeLast = handle deletion of the last element

Get the head

Queues don’t permit you to have an access to an arbitary element. You can get only head element (with exception again with ArrayDeque that allows to get both head and last elements).

@Test
public void getHeadTest(){
    Queue<Person> people = new ArrayDeque<>();
    people.offer(new Person("Alejandra", "Morales"));
    people.offer(new Person("Beatriz", "Sanchez"));
    people.offer(new Person("Carmen", "Hidalgo"));

    Person element = people.element();
    Person peek = people.peek();
    assertThat(element).isEqualTo(peek);
}

For getting the_head element you can use both Collection’s element and native peek methods. The difference comes on an empty queue:

  • element throws NoSuchElementException on empty queue
  • peek returns null if the queue is empty

As it was mentioned already, ArrayDeque permits to get both the head and the last elements therefore provides two own methods to get the head: getFirst and peekFirst. These methods differ on the aforesaid manner.

Get the tail

Tail means all elements after head. In other words, this is collection, rather than one single element. Although, Java does not provide a method to get a tail of queue, but you can write you own if you need like this:

@Test
public void getTailTest(){
    Queue<Person> people = new ArrayDeque<>();
    people.offer(new Person("Alejandra", "Morales"));
    people.offer(new Person("Beatriz", "Sanchez"));
    people.offer(new Person("Carmen", "Hidalgo"));

    // step 1 Copy existing queue
    Queue<Person> tail = new ArrayDeque<>(people);

    // step 2 remove head
    tail.poll();

    assertThat(tail).hasSize(2);
}

In this implementation we perform a chain of three actions:

  1. Create new queue from the target one
  2. Remove head
  3. Return queue without head (e.g. tail)

Source code

You can find the full source code for this post in this github repository. If you have questions regarding this post, don’t hesitate to contact me. Have a nice day!