Guava MinMaxPriorityQueue 和 EvictingQueue简介

1 . 概述

在本文中，我们将研究来自 Guava 库的*EvictingQueue 和MinMaxPriorityQueue 构造。EvictingQueue是循环缓冲区概念的实现。MinMaxPriorityQueue使我们可以使用提供的Comparator*访问其最小和最大元素。

2. EvictingQueue

让我们从构造开始——在构造队列实例时，我们需要提供最大队列大小作为参数。

当我们想向EvictingQueue添加一个新项目时，队列已满，它会自动从其 head 中逐出一个元素。

与标准队列行为相比，将元素添加到完整队列不会阻塞，而是删除头元素并将新元素添加到尾部。

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

让我们构造一个最大大小为 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);

如果我们有标准的队列实现，向完整队列添加新项目会阻塞生产者。

EvictingQueue实现并非如此。向其中添加新元素将导致头部从其中移除，新元素将添加到尾部：

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

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

3. MinMaxPriorityQueue

MinMaxPriorityQueue提供对其最小和最大元素的恒定时间访问。

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

元素的排序由Comparator完成，需要传递给此队列的构造函数。

假设我们有一个CustomClass类，它有一个整数类型的*value *字段：

class CustomClass {
    private Integer value;
    // standard constructor, getters and setters
}

让我们创建一个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)));

由于MinMaxPriorityQueue和传递的Comparator的特性，队列头部的元素将等于 1，队列尾部的元素将等于 10：

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

由于我们队列的容量为 10，并且我们添加了 10 个元素，因此队列已满。向其中添加新元素将导致队列中的最后一个元素被删除。让我们添加一个值为*-1的CustomClass*：

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

在该操作之后，队列中的最后一个元素将被删除，并且它尾部的新元素将等于 9。新的头部将是 -1，因为这是根据我们传递的Comparator时新的最小元素构建了我们的队列：

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

根据*MinMaxPriorityQueue 的规范，*如果队列已满，添加大于当前最大元素的元素将删除相同的元素——实际上忽略它。

让我们添加一个 100 数字并测试该项目在该操作之后是否在队列中：

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

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