Guava 有限大小队列 (EvictingQueue) 介绍和分析

置顶 | 发表于 | 阅读次数：

在实际场景中总会遇到这样的需求：

需要一个先进先出（FiFo）的队列，其大小是一定的，往队列中插值时，如果队列已经填满了，则移出队列的第一个元素。即所谓的有限大小的队列。

当然，我们能想到的 Guava 也想到了，它提供了的 EvictingQueue 类可以满足上述需求。

简单使用

先来个简单示例，创建一个大小为 3 的 EvictingQueue，循环往队列中添加 6 个元素，再打印出队列中元素情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
@Test
public void test() {
    EvictingQueue<Integer> queue = EvictingQueue.create(3);
    for (int i = 0; i < 6; i++) {
        queue.add(i);
        System.out.println("添加元素：" + i);
        System.out.println("当前队列中元素集合：" + StringUtils.join(queue.iterator(), ',') + "\n");
    }
}

// 输出：
添加元素：0
当前队列中元素集合：0

添加元素：1
当前队列中元素集合：0,1

添加元素：2
当前队列中元素集合：0,1,2

添加元素：3
当前队列中元素集合：1,2,3

添加元素：4
当前队列中元素集合：2,3,4

添加元素：5
当前队列中元素集合：3,4,5

可以看出，当添加元素 4 时，队列的元素变成了 2,3,4，原先队列头部的 1 去掉了；再添加元素 5 时，队列头部的 2 又去掉了。

与上面描述的需求一致。

源码分析

EvictingQueue 内部维护了两个重要的成员属性：maxSize 和 delegate。

maxSize 表示队列的最大长度，而且是 final 的，代表初始化后不能改变；delegate 是真正维护元素的队列，EvictingQueue 使用的是 JDK 的 ArrayDeque，它是一个数组结构的双端队列。

1
2
3
4
5
6
7
8
9
private final Queue<E> delegate;

final int maxSize;

private EvictingQueue(int maxSize) {
    checkArgument(maxSize >= 0, "maxSize (%s) must >= 0", maxSize);
    this.delegate = new ArrayDeque<E>(maxSize);
    this.maxSize = maxSize;
}

EvictingQueue 与普通队列的不同在于 add 方法：

1
2
3
4
5
6
7
8
9
10
11
public boolean add(E e) {
    checkNotNull(e); // check before removing
    if (maxSize == 0) {
        return true;
    }
    if (size() == maxSize) {
        delegate.remove();
    }
    delegate.add(e);
    return true;
}

在执行添加元素前，会判断当队列大小达到 maxSize 时，调用 ArrayDeque 的 remove 方法，这个方法会移除队列头部元素。

其它的常用方法都是直接调用 ArrayDeque 的对应方法：

1
2
3
4
5
6
7
8
9
@Override
public boolean contains(Object object) {
    return delegate().contains(checkNotNull(object));
}

@Override
public boolean remove(Object object) {
    return delegate().remove(checkNotNull(object));
}

总的来说 EvictingQueue 类似一个 ArrayDeque 的包装类，重写了 ArrayDeque 的 add 方法，其它特性与 ArrayDeque 没什么区别。

补充

除了 Guava 的 EvictingQueue 外，Apache commons-collections 包也提供了类似的类：CircularFifoQueue。

它的原理则是直接操作内部维护的一个固定长度数组，通过控制游标的方式删除、添加、遍历元素。

相关文章