Java – 环形缓冲区

我有一个stream媒体时间序列，其中我有兴趣保留最后4个元素，这意味着我想能够popup第一个，并添加到最后。 哪个Java Collection最适合这个？ vector？

Answer 1

考虑Common.Collections中的CircularFifoBuffer 。 与Queue不同，您不必维护底层集合的有限大小，并在达到限制时将其封装起来。

 Buffer buf = new CircularFifoBuffer(4); buf.add("A"); buf.add("B"); buf.add("C"); buf.add("D"); //ABCD buf.add("E"); //BCDE 

由于以下属性，CircularFifoBuffer将为您执行此操作：

• CircularFifoBuffer是具有固定大小的先进先出缓冲区，如果已满则replace其最早的元素。
• CircularFifoBuffer的删除顺序基于插入顺序; 元素将以与添加元素相同的顺序被删除。 迭代顺序与删除顺序相同。
• add（Object），BoundedFifoBuffer.remove（）和BoundedFifoBuffer.get（）操作都在不变的时间内执行 。 所有其他操作在线性时间或更糟的情况下执行

但是你也应该考虑到它的局限性，例如，你不能在这个集合中添加缺less的时间序列，因为它不允许空值。

Answer 2

自番石榴15.0（2013年9月发布）有EvictingQueue ：

当尝试向队列添加新元素并且已满时，会自动从队列头部逐出元素的非阻塞队列。 一个驱逐队列必须configuration最大的大小。 每次将一个元素添加到完整队列中时，队列会自动删除其头元素。 这与传统的有界队列不同，当队列满时阻塞或拒绝新的元素。

这个类不是线程安全的，不接受空元素。

使用示例：

 EvictingQueue<String> queue = EvictingQueue.create(2); queue.add("a"); queue.add("b"); queue.add("c"); queue.add("d"); System.out.print(queue); //outputs [c, d] 

Answer 3

自从Java 1.6以来，就有ArrayDeque ，它实现了Queue ，似乎比LinkedList更快，更有效率，并且没有ArrayBlockingQueue的线程同步开销：来自API文档： “这个类可能比堆栈用作堆栈时，比用作队列时的LinkedList速度快。

 final Queue<Object> q = new ArrayDeque<Object>(); q.add(new Object()); //insert element q.poll(); //remove element 

Answer 4

如果你需要

• O（1）插入和移除
• O（1）索引到内部元素
• 仅从单个线程访问
• 通用元素types

那么您可以通过这种方式使用此CircularArrayList for Java （例如）：

 CircularArrayList<String> buf = new CircularArrayList<String>(4); buf.add("A"); buf.add("B"); buf.add("C"); buf.add("D"); // ABCD String pop = buf.remove(0); // A <- BCD buf.add("E"); // BCDE String interiorElement = buf.get(i); 

所有这些方法都在O（1）中运行。

Answer 5

前段时间我也有同样的问题，很失望，因为找不到满足我需求的解决scheme，于是我写了自己的课。 老实说，当时我确实发现了一些代码，但即使这样也不是我正在寻找的，所以我改编了它，现在我正在分享它，就像那段代码的作者一样。

编辑：这是原来的（虽然略有不同）代码： CircularArrayList为Java

我没有源代码的链接，因为这是以前的代码，但是这是代码：

 import java.util.AbstractList; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.RandomAccess; public class CircularArrayList<E> extends AbstractList<E> implements RandomAccess { private final int n; // buffer length private final List<E> buf; // a List implementing RandomAccess private int leader = 0; private int size = 0; public CircularArrayList(int capacity) { n = capacity + 1; buf = new ArrayList<E>(Collections.nCopies(n, (E) null)); } public int capacity() { return n - 1; } private int wrapIndex(int i) { int m = i % n; if (m < 0) { // modulus can be negative m += n; } return m; } @Override public int size() { return this.size; } @Override public E get(int i) { if (i < 0 || i >= n-1) throw new IndexOutOfBoundsException(); if(i > size()) throw new NullPointerException("Index is greater than size."); return buf.get(wrapIndex(leader + i)); } @Override public E set(int i, E e) { if (i < 0 || i >= n-1) { throw new IndexOutOfBoundsException(); } if(i == size()) // assume leader's position as invalid (should use insert(e)) throw new IndexOutOfBoundsException("The size of the list is " + size() + " while the index was " + i +". Please use insert(e) method to fill the list."); return buf.set(wrapIndex(leader - size + i), e); } public void insert(E e) { int s = size(); buf.set(wrapIndex(leader), e); leader = wrapIndex(++leader); buf.set(leader, null); if(s == n-1) return; // we have replaced the eldest element. this.size++; } @Override public void clear() { int cnt = wrapIndex(leader-size()); for(; cnt != leader; cnt = wrapIndex(++cnt)) this.buf.set(cnt, null); this.size = 0; } public E removeOldest() { int i = wrapIndex(leader+1); for(;;i = wrapIndex(++i)) { if(buf.get(i) != null) break; if(i == leader) throw new IllegalStateException("Cannot remove element." + " CircularArrayList is empty."); } this.size--; return buf.set(i, null); } @Override public String toString() { int i = wrapIndex(leader - size()); StringBuilder str = new StringBuilder(size()); for(; i != leader; i = wrapIndex(++i)){ str.append(buf.get(i)); } return str.toString(); } public E getOldest(){ int i = wrapIndex(leader+1); for(;;i = wrapIndex(++i)) { if(buf.get(i) != null) break; if(i == leader) throw new IllegalStateException("Cannot remove element." + " CircularArrayList is empty."); } return buf.get(i); } public E getNewest(){ int i = wrapIndex(leader-1); if(buf.get(i) == null) throw new IndexOutOfBoundsException("Error while retrieving the newest element. The Circular Array list is empty."); return buf.get(i); } } 

Answer 6

之前给出的例子都没有完全满足我的需求，所以我编写了自己的队列，允许以下function：迭代，索引访问，indexOf，lastIndexOf，先取得，取得最后一个，报价，剩余容量，扩展容量，最后一个出列，退出首先，入队/添加元素，出列/删除元素，subQueueCopy，subArrayCopy，toArray，快照，基本大小，删除或包含。

EjectingQueue

EjectingIntQueue

Answer 7

一个非常有趣的项目是破坏者。 它有一个ringbuffer，用于我所知的金融应用。

看到这里： ringbuffer的代码

Answer 8

使用队列

 Queue<String> qe=new LinkedList<String>(); qe.add("a"); qe.add("b"); qe.add("c"); qe.add("d"); System.out.println(qe.poll()); //returns a System.out.println(qe.poll()); //returns b System.out.println(qe.poll()); //returns c System.out.println(qe.poll()); //returns d 

Queue有五个简单的方法

• element（） – 检索但不移除此队列的头部。

• offer（E o） – 将指定的元素插入到此队列中
  可能。

• peek（） – 检索但不移除此队列的头部，如果此队列为空，则返回null。

• poll（） – 检索并删除此队列的头部，如果此队列为空，则返回null。

• remove（） – 检索并删除此队列的头部。