Guide to Guava MinMaxPriorityQueue and EvictingQueue – Guava MinMaxPriorityQueue和EvictingQueue指南

1. Overview

1.概述

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.

在这篇文章中，我们将关注Guava库中的EvictingQueue, 和MinMaxPriorityQueue 结构。EvictingQueue是循环缓冲区概念的一个实现。MinMaxPriorityQueue使用提供的Comparator.让我们可以访问其最低和最大的元素。

2. EvictingQueue

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.

当我们想向EvictingQueue添加一个新的项目，而队列已经满了，它就会自动将一个元素从其头部驱逐出去。

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.

我们可以把EvictingQueue想象成一个环，我们以仅有的append方式将元素插入其中。如果在我们想要添加新元素的位置上有一个元素，我们只需覆盖给定位置上的现有元素。

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

让我们构建一个最大尺寸为10的EvictingQueue的实例。接下来，我们将向其添加10个元素。

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实现的情况。向它添加一个新元素将导致头部被移除，而新元素将被添加到尾部。

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.

通过使用EvictingQueue作为循环缓冲区，我们可以创建非常高效的并发程序。

3. MinMaxPriorityQueue

3.MinMaxPriorityQueue

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

MinMaxPriorityQueue提供了对其最小和最大元素的持续时间访问。

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.

为了得到最小的元素，我们需要调用peekFirst() 方法。要获得最大的元素，我们可以调用peekLast() 方法。注意，这些并不从队列中移除元素，它们只是检索它。

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:

假设我们有一个CustomClass类，它有一个整数类型的value域。

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，它将对int类型使用比较器。接下来，我们将向队列中添加10个CustomClass类型的对象。

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:

由于MinMaxPriorityQueue和通过的Comparator的特性，队列头部的元素将等于1，队列尾部的元素将等于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:

由于我们队列的容量是10，而我们添加了10个元素，队列已经满了。添加一个新元素将导致队列中的最后一个元素被移除。让我们添加一个CustomClass，其值等于-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:

在这个动作之后，队列中的最后一个元素将被删除，其尾部的新项目将等于9。新的头部将是-1，因为根据我们在构建队列时传递的Comparator，这是新的最小元素。

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.

根据MinMaxPriorityQueue的规范，在队列已满的情况下，添加一个大于当前最大元素的元素将移除同一元素–有效地忽略它。

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

让我们添加一个100号，并测试该操作后该项目是否在队列中。

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.

正如我们所看到的，队列中的第一个元素仍然等于-1，最后一个元素等于9。因此，添加一个整数被忽略了，因为它大于队列中已经最大的元素。

4. Conclusion

4.结论

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

在这篇文章中，我们看了一下Guava库中的EvictingQueue和MinMaxPriorityQueue结构。

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

我们看到了如何使用EvictingQueue作为循环缓冲区来实现非常高效的程序。

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

我们使用MinMaxPriorityQueue与Comparator相结合的方式，对其最小和最大的元素进行恒定时间访问。

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.

记住这两个呈现的队列的特性是很重要的，因为向它们添加一个新的元素将覆盖已经在队列中的元素。这与标准队列的实现相反，在标准队列中，向完整的队列中添加新元素将阻塞生产者线程或抛出一个异常。

The implementation of all these examples and code snippets can be found in the GitHub project – this is a Maven project, so it should be easy to import and run as it is.

所有这些例子和代码片段的实现都可以在GitHub项目中找到–这是一个Maven项目，所以应该很容易导入并按原样运行。