Queues in vanilla Java and vavr.collection.Queue

Hello! Let me continue a series of posts that talks about Vavr library and possibilites it offers to Java developers. We already started a topic of Vavr immutable collections and how they correspond to their Java analogs. In the previous article we researched difference between vanilla Java arrays and Vavr arrays.

Here we talk about queue data structure and how it is implemented in Java Collections Framework (JCF) and in Vavr. If you are not familiar with Java collections, I’d like you to refer to this guide. In this post we will describe queue as a data structure and then observe both vanilla Java and Vavr versions. We will explore enqueue and dequeue operations and how to access head element (first one) and tail of the queue.

Table of Contents

Queue as a data structure

Before going to concrete implementations of queue data structure in Java and Vavr, 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 means First-in-First-out. In other words, element that was inserted first, will be removed first (unlike stacks, where first element is removed last). To describe this principle, let take an example with ferry. The first car that was embarked on a ferry, will disembarked first.

Graph 1. Queue on a car ferry

Another example is a queue in a ticket office to buy tickets on this ferry. There governs FIFO principle: person that came first to the ticket gate, will buy and exit a queue first.

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.

Queues in Java Collections Framework

Java supplies its own implementation of queue data structure as part of Java Collections Framework. There are two main classes used: ArrayDeque and PriorityQueue:

Graph 2. Queue in Java Collections Framework

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 (if they implement Comparable interface) or based on specified Comparator. Therefore, head element in this case will be the least element.

Queue declaration

In order to use a queue you should declare it (obviously, Sherlock!). Queues can be defined using public constructors that help specify capacity. No args constuctors create queues with an initial capacity sufficient to hold 16 elements:

// initial capacity = 16

Queue<Person> people = new ArrayDeque<>();

// for the ferry that can transport 50 cars

Queue<Car> cars = new ArrayDeque<>(50);

Handling enqueue operation

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. 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("Zuzana", "Cermakova"));
people.offer(new Person("Tereza", "Vodickova"));

people.add(new Person("Carolina", "Prokopova"));

Person head = people.peek();

// head of queue is Zuzana Cermakova

assertEquals("Zuzana", head.getFirstName());
assertEquals("Cermakova", head.getLastName());

// there are 3 elements in queue

assertEquals(3, people.size());
}

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();
Car head = cars.peek();
assertEquals(1234, head.getLicensePlateNumber());
}

The difference between both methods is same with enqueue methods and again Java recommends to use 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 unlike for instance lists or maps 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 dequeueTest(){
    Queue<Car> cars = new ArrayDeque<>();
    cars.offer(new Car(4567, "Skoda Rapid"));
    Car head = cars.peek();
    assertEquals(4567, head.getLicensePlateNumber());
}

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. Unfortunately, Java does not provide a method to get a tail of queue, but you can write you own if you need like this:

Queue<Person> getTail(Queue<Person> queue){
    Queue<Person> tail = new ArrayDeque(queue);
    tail.poll();
    return tail;
}

@Test
public void getTailTest(){
    Queue<Person> people = new ArrayDeque<>();
    people.offer(new Person("Zuzana", "Cermakova"));
    people.offer(new Person("Tereza", "Vodickova"));
    people.offer(new Person("Carolina", "Prokopova"));

    Queue<Person> tail = getTail(people);  

    assertEquals(2, tail.size());  
    assertEquals("Tereza", tail.peek().getFirstName());
}

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)

Although, if you need to get tail in your code, I suggest you to take a look on other implementations, for instance Vavr.

Queues in Vavr

Vavr provides its own version of queue data structure. As well as Vavr arrays that we mentioned previously, queues (and all other Vavr collections) are immutable. So, operations don’t affect a target queue, rather return modified version.

Take a look on the graph, that presents the place of vavr.collection.Queue among other Vavr data structures:

Graph 3. Queue in Vavr collections hierarchy

Queue declaration

From a technical point of view, in immutable collections you can’t affect data. So you declare Vavr queues with specified elements using static methods, inherited from Traversable:

Queue<Person> people = Queue.of(
new Person("Aneta", "Fialova"), 
new Person("Jana", "Dvorakova"), 
new Person("Patricia", "Shvecova"));

Another approach is ofAll method that differs from of, that accepts primitives.

Handling enqueue operation

What is cool about Vavr, that enqueue operation is named enqueue. This method inserts new element at the tail:

@Test
public void enqueueTest(){
    Queue<Person> people = Queue.of(
    new Person("Aneta", "Fialova"), 
    new Person("Jana", "Dvorakova"), 
    new Person("Patricia", "Shvecova"));

// vavr queues are immutable
    Queue<Person> result = people.enqueue(new Person("Marketa", "Dietrichova"));
    assertEquals(3, people.size());
    assertEquals(4, result.size());

// queue is FIFO; elements are added to tail
    Person peopleHead = people.head();
    Person resultHead = result.head();
    assertEquals(peopleHead, resultHead);
}

Due to the immutable nature of Vavr collections, they can’t be affected after declaration. That means, that addition of new element creates new queue: in our example enqueue method creates new queue result, but old queue people is not affected.

Handling dequeue operation

As in the previous situation, Vavr naming is amazing. Dequeue operation is performed using dequeue method:

@Test
public void dequeueTest(){
    Queue<Person> people = Queue.of(
        new Person("Aneta", "Fialova"), 
        new Person("Jana", "Dvorakova"), 
        new Person("Patricia", "Shvecova"));

    Tuple2<Person, Queue<Person>> result = people.dequeue();

// first is head

    Person head = result._1();
    Queue<Person> remainingPeople = result._2();
    assertEquals("Aneta", head.getFirstName());
    assertEquals(2, remainingPeople.size());
    assertEquals("Jana", remainingPeople.head().getFirstName());

}

Observe, that the return object in dequeue method. Unlike enqueue, here we obtain Tuple object as the result of the operation. It contains two values (named _1 and _2):

  1. Head element that was removed
  2. Remaining elements as a new queue

NB you can access elements of tuple in two ways: using field names or (like it is in the code snippet above) using getters methods.

Get the head

Getting head element in Vavr is easy and performed using head() method. Take a look on the code below:

Queue<Person> people = Queue.of(
	new Person("Aneta", "Fialova"), 
	new Person("Jana", "Dvorakova"), 
	new Person("Patricia", "Shvecova"));

Person head = people.head();

Get the tail

Finally, let see how to get tail in queue. We already defined, that tail stands for rear elements in the queue. In Vavr you don’t need to do any magic, as it has built-in method to get the tail of queue. This code snippet persents how to do it:

@Test
public void getTailTest(){
    Queue<Person> people = Queue.of(
        new Person("Aneta", "Fialova"), 
        new Person("Jana", "Dvorakova"), 
        new Person("Patricia", "Shvecova"));
    Queue<Person> tail = people.tail();
    assertEquals(2, tail.size());
}

Conclusion

In this post we explored queue as a data structure and then its implementation in vanilla Java (as a part of Java Collections Framework) and Vavr version. Note, that unlike Java queues, Vavr queues are immutable. We reviewed how to handle enqueue and dequeue operations and access head element and tail of queue.

References

  • Clifford A. Shaffer Data Structures & Algorithm Analysis 3 edn, Dover Publications, 2013
  • Grzegorz Piwowarek. Vavr Collections and Java Stream API Collectors (2017) 4Comprehension, read here
  • Queue Implementations Oracle Java SE Tutorials, read here

Leave a Reply

Your email address will not be published. Required fields are marked *