Java 是否有固定大小的队列可以删除过多的元素？

Is there a fixed sized queue which removes excessive elements?

提问by c0d3x

I need a queue with a fixed size. When I add an element and the queue is full, it should automatically remove the oldest element.

我需要一个固定大小的队列。当我添加一个元素并且队列已满时，它应该自动删除最旧的元素。

Is there an existing implementation for this in Java?

Java 中是否有针对此的现有实现？

采纳答案by moritz

There is no existing implementation in the Java Language and Runtime. All Queues extend AbstractQueue, and its doc clearly states that adding an element to a full queue always ends with an exception. It would be best ( and quite simple ) to wrap a Queue into a class of your own for having the functionality you need.

Java 语言和运行时中没有现有的实现。所有队列都扩展了AbstractQueue，其文档明确指出将元素添加到完整队列总是以异常结束。最好（并且非常简单）将 Queue 包装到您自己的类中以获得您需要的功能。

Once again, because all queues are children of AbstractQueue, simply use that as your internal data type and you should have a flexible implementation running in virtually no time :-)

再一次，因为所有队列都是 AbstractQueue 的子级，只需将其用作您的内部数据类型，您就应该有一个几乎立即运行的灵活实现:-)

UPDATE:

更新：

As outlined below, there are two open implementations available (this answer is quite old, folks!), see this answerfor details.

如下所述，有两个可用的开放实现（这个答案很旧，伙计们！），请参阅此答案以了解详细信息。

回答by Thorbj?rn Ravn Andersen

Sounds like an ordinary List where the add method contains an extra snippet which truncates the list if it gets too long.

听起来像一个普通的 List，其中 add 方法包含一个额外的片段，如果列表太长，它会截断列表。

If that is too simple, then you probably need to edit your problem description.

如果这太简单了，那么您可能需要编辑问题描述。

回答by Zoran Regvart

Also see this SO question, or ArrayBlockingQueue(be careful about blocking, this might be unwanted in your case).

另请参阅此 SO question或ArrayBlockingQueue（注意阻塞，这在您的情况下可能是不需要的）。

回答by Zoran Regvart

I think what you're describing is a circular queue. Here is an exampleand here is a betterone

我认为你所描述的是一个循环队列。下面是一个例子，这里是一个好一个

回答by JaakkoK

It is not quite clear what requirements you have that led you to ask this question. If you need a fixed size data structure, you might also want to look at different caching policies. However, since you have a queue, my best guess is that you're looking for some type of router functionality. In that case, I would go with a ring buffer: an array that has a first and last index. Whenever an element is added, you just increment the last element index, and when an element is removed, increment the first element index. In both cases, addition is performed modulo the array size, and make sure to increment the other index when needed, that is, when the queue is full or empty.

不太清楚您有什么要求导致您提出这个问题。如果您需要固定大小的数据结构，您可能还需要查看不同的缓存策略。但是，由于您有一个队列，我最好的猜测是您正在寻找某种类型的路由器功能。在那种情况下，我会使用环形缓冲区：一个具有第一个和最后一个索引的数组。每当添加一个元素时，您只需增加最后一个元素的索引，当删除一个元素时，增加第一个元素的索引。在这两种情况下，加法都是以数组大小为模进行的，并确保在需要时增加另一个索引，即当队列已满或为空时。

Also, if it is a router-type application, you might also want to experiment with an algorithm such as Random Early Dropping (RED), which drops elements from the queue randomly even before it gets filled up. In some cases, RED has been found to have better overall performance than the simple method of allowing the queue to fill up before dropping.

此外，如果它是一个路由器类型的应用程序，您可能还想尝试一种算法，例如随机早期丢弃 (RED)，它甚至在队列被填满之前从队列中随机丢弃元素。在某些情况下，已发现 RED 比允许队列在丢弃前填满的简单方法具有更好的整体性能。

回答by Mavrik

Actually the LinkedHashMapdoes exactly what you want. You need to override the removeEldestEntrymethod.

实际上LinkedHashMap正是您想要的。您需要覆盖该removeEldestEntry方法。

Example for a queue with max 10 elements:

最多 10 个元素的队列示例：

  queue = new LinkedHashMap<Integer, String>()
  {
     @Override
     protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest)
     {
        return this.size() > 10;   
     }
  };

If the "removeEldestEntry" returns true, the eldest entry is removed from the map.

如果“removeEldestEntry”返回true，则从地图中删除最旧的条目。

回答by Mike

Actually you can write your own impl based on LinkedList, it is quite straight forward, just override the add method and do the staff.

其实你可以基于 LinkedList 编写你自己的 impl，它非常简单，只需覆盖 add 方法并完成工作人员。

回答by Dave Moten

This class does the job using composition instead of inheritance (other answers here) which removes the possibility of certain side-effects (as covered by Josh Bloch in Essential Java). Trimming of the underlying LinkedList occurs on the methods add,addAll and offer.

这个类使用组合而不是继承（这里有其他答案）来完成这项工作，这消除了某些副作用的可能性（如基本 Java 中的 Josh Bloch 所涵盖）。底层 LinkedList 的修剪发生在方法 add、addAll 和 offer 上。

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class LimitedQueue<T> implements Queue<T>, Iterable<T> {

    private final int limit;
    private final LinkedList<T> list = new LinkedList<T>();

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    private boolean trim() {
        boolean changed = list.size() > limit;
        while (list.size() > limit) {
            list.remove();
        }
        return changed;
    }

    @Override
    public boolean add(T o) {
        boolean changed = list.add(o);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return list.contains(o);
    }

    @Override
    public Iterator<T> iterator() {
        return list.iterator();
    }

    @Override
    public Object[] toArray() {
        return list.toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return list.toArray(a);
    }

    @Override
    public boolean remove(Object o) {
        return list.remove(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return list.containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean changed = list.addAll(c);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return list.removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return list.retainAll(c);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean offer(T e) {
        boolean changed = list.offer(e);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public T remove() {
        return list.remove();
    }

    @Override
    public T poll() {
        return list.poll();
    }

    @Override
    public T element() {
        return list.element();
    }

    @Override
    public T peek() {
        return list.peek();
    }
}

回答by Roar Skullestad

I just implemented a fixed size queue this way:

我只是通过这种方式实现了一个固定大小的队列：

public class LimitedSizeQueue<K> extends ArrayList<K> {

    private int maxSize;

    public LimitedSizeQueue(int size){
        this.maxSize = size;
    }

    public boolean add(K k){
        boolean r = super.add(k);
        if (size() > maxSize){
            removeRange(0, size() - maxSize);
        }
        return r;
    }

    public K getYoungest() {
        return get(size() - 1);
    }

    public K getOldest() {
        return get(0);
    }
}

回答by Basil Bourque

Yes, Two

是的，两个

From my own duplicate questionwith this correct answer, I learned of two:

从我自己的重复问题和这个正确答案中，我了解到两个：

• EvictingQueuein Google Guava
• CircularFifoQueuein Apache Commons

• EvictingQueue在谷歌番石榴
• CircularFifoQueue在Apache Commons 中

I made productive use of the Guava EvictingQueue, worked well.

我有效地使用了 Guava EvictingQueue，效果很好。