Guide to Guava MinMaxPriorityQueue and EvictingQueue

1. Overview

In this article, we’ll be looking at the EvictingQueue, and MinMaxPriorityQueue constructs from the Guava library. The EvictingQueue is an implementation of the circular buffer concept. The MinMaxPriorityQueue gives us an access to its lowest and greatest element using the supplied Comparator.

2. EvictingQueue

Let’s start with construction – when constructing an instance of the queue, we need to supply the maximum queue size as an argument.

When we want to add a new item to the EvictingQueue, and the queue is full, it automatically evicts an element from its head.

When comparing to the standard queue behavior, adding an element to the full queue does not block but removes the head element and adds a new item to the tail.

We can imagine the EvictingQueue as a ring to which we are inserting elements in the append-only fashion. If there is an element on the position on which we want to add a new element, we just override the existing element at the given position.

Let’s construct an instance of the EvictingQueue with the maximum size of 10. Next, we will add 10 elements to it:

Queue<Integer> evictingQueue = EvictingQueue.create(10);

IntStream.range(0, 10)
  .forEach(evictingQueue::add);

assertThat(evictingQueue)
  .containsExactly(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);

If we had the standard queue implementation, adding a new item to the full queue would block the producer.

That is not a case with the EvictingQueue implementation. Adding a new element to it will cause the head to be removed from it, and the new element will be added to the tail:

evictingQueue.add(100);

assertThat(evictingQueue)
  .containsExactly(1, 2, 3, 4, 5, 6, 7, 8, 9, 100);

By using the EvictingQueue as the circular buffer, we can create very efficient concurrent programs.

3. MinMaxPriorityQueue

The MinMaxPriorityQueue provides constant-time access to its least and greatest elements.

To get the least element, we need to call the peekFirst() method. To get the greatest element we can call the peekLast() method. Note that these do not remove elements from a queue, they only retrieve it.

The ordering of elements is done by the Comparator that needs to be passed to the constructor of this queue.

Let’s say that we have a CustomClass class that has a value field of the integer type:

class CustomClass {
    private Integer value;

    // standard constructor, getters and setters
}

Let’s create a MinMaxPriorityQueue that will be using the comparator on int types. Next, we will add 10 objects of the CustomClass type to the queue:

MinMaxPriorityQueue<CustomClass> queue = MinMaxPriorityQueue
  .orderedBy(Comparator.comparing(CustomClass::getValue))
  .maximumSize(10)
  .create();

IntStream
  .iterate(10, i -> i - 1)
  .limit(10)
  .forEach(i -> queue.add(new CustomClass(i)));

Due to the characteristics of the MinMaxPriorityQueue and passed Comparator, the element at the head of the queue will be equal to 1 and the element at the tail of the queue will be equal to 10:

assertThat(
  queue.peekFirst().getValue()).isEqualTo(1);
assertThat(
  queue.peekLast().getValue()).isEqualTo(10);

As the capacity of our queue is 10, and we added 10 elements, the queue is full. Adding a new element to it will cause the last element in the queue to be removed. Let’s add a CustomClass with the value equal to -1:

queue.add(new CustomClass(-1));

After that action, the last element in the queue will be deleted and the new item at the tail of it will be equal to 9. The new head will be -1 as this is the new least element according to the Comparator that we passed when constructed our queue:

assertThat(
  queue.peekFirst().getValue()).isEqualTo(-1);
assertThat(
  queue.peekLast().getValue()).isEqualTo(9);

According to the specification of the MinMaxPriorityQueue, in case the queue is full, adding an element that is greater than the currently greatest element will remove that same element – effectively ignoring it.

Let’s add a 100 number and test if that item is in the queue after that operation:

queue.add(new CustomClass(100));
assertThat(queue.peekFirst().getValue())
  .isEqualTo(-1);
assertThat(queue.peekLast().getValue())
  .isEqualTo(9);

As we see the first element in the queue is still equal to -1 and last is equal to 9. Therefore, adding an integer was ignored as it is greater that already greatest element in the queue.

4. Conclusion

In this article, we had a look at the EvictingQueue and MinMaxPriorityQueue construct from the Guava library.

We saw how to use the EvictingQueue as the circular buffer to implement very efficient programs.

We used the MinMaxPriorityQueue combined with the Comparator to have the constant-time access to its least and greatest element.

It is important to remember the characteristics of both presented queues, as adding a new element to them will override an element that is already in the queue. This is contrary to the standard queue implementations, where adding a new element to the full queue will block the producer thread or throw an exception.