是否有一个固定大小的队列,删除过多的元素?

我需要一个固定大小的队列。 当我添加一个元素和队列已满,它应该自动删除最老的元素。

在Java中是否有现成的实现?

Java语言和运行时没有现有的实现。 所有的队列都扩展了AbstractQueue ,它的文档清楚地表明,添加一个元素到一个完整队列总是以一个exception结束。 将Queue封装到你自己的类中是最好的(也是相当简单的),因为它具有你需要的function。

再一次,因为所有的队列都是AbstractQueue的孩子,所以简单地使用它作为你的内部数据types,你应该有一个灵活的实现在几乎没有时间运行:-)

更新:

如下所述,有两个开放的实现可用(这个答案是相当古老的,人们!),看到这个答案的细节。

其实LinkedHashMap正是你想要的。 您需要重写removeEldestEntry方法。

具有最多10个元素的队列示例:

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

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

是的,两个

从我自己的 这个正确答案 的重复问题中 ,我了解到了两点:

  • 谷歌Guava中的 EvictingQueue
  • CircularFifoQueue在Apache Commons中

我使用了Guava EvictingQueue ,效果很好。

我只是这样实现了一个固定大小的队列:

 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 - 1); } return r; } public K getYongest() { return get(size() - 1); } public K getOldest() { return get(0); } } 

我想你所描述的是一个循环队列。 这里是一个例子 ,这里是一个更好的例子

这是我用Queue封装的LinkedList ,我在这里给定的大小是2;

 public static Queue<String> pageQueue; pageQueue = new LinkedList<String>(){ private static final long serialVersionUID = -6707803882461262867L; public boolean add(String object) { boolean result; if(this.size() < 2) result = super.add(object); else { super.removeFirst(); result = super.add(object); } return result; } }; .... TMarket.pageQueue.add("ScreenOne"); .... TMarket.pageQueue.add("ScreenTwo"); ..... 

这个类使用组合而不是inheritance(这里的其他答案)来解决某些副作用的可能性(正如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(); } } 

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

如果这太简单,那么你可能需要编辑你的问题描述。

也看到这个SO问题 ,或ArrayBlockingQueue (小心封锁,这可能是不需要在你的情况下)。

你有什么要求导致你问这个问题还不是很清楚。 如果你需要一个固定大小的数据结构,你可能也想看看不同的caching策略。 然而,由于你有一个队列,我最好的猜测是你正在寻找某种types的路由器function。 在这种情况下,我会用一个环形缓冲区:一个具有第一个和最后一个索引的数组。 每当添加一个元素时,只需递增最后一个元素索引,并且当元素被移除时,递增第一个元素索引。 在这两种情况下,添加都是以数组大小为模数执行的,并且确保在需要时增加其他索引,即当队列满或空时。

另外,如果它是一个路由器types的应用程序,你可能也想尝试一种algorithm,比如Random Early Dropping(RED),它在队列被填满之前随机地从队列中删除元素。 在某些情况下,RED被发现比简单的方法让队列填满之前有更好的整体性能下降。

其实你可以编写你自己的基于LinkedList的impl,这是非常简单的,只是重写add方法,并做的工作人员。

我认为最好的答案是来自另一个问题 。

阿帕奇公共收集4有一个CircularFifoQueue这是你在找什么。 引用javadoc:

CircularFifoQueue是一个固定大小的先进先出队列,如果已满,它将replace其最早的元素。

一个简单的解决scheme,下面是一个队列的“string”

 LinkedHashMap<Integer, String> queue; int queueKeysCounter; queue.put(queueKeysCounter++, "My String"); queueKeysCounter %= QUEUE_SIZE; 

请注意,这不会维护队列中项目的顺序,但会replace最旧的项目。