Java - 环形缓冲区

Question

我有一个流式时间序列，其中我有兴趣保留最后4个元素，这意味着我希望能够弹出第一个，并添加到最后。哪个Java Collection最适合这个？矢量？

Answer 1

使用Queue

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

• 元素（）的五个简单的方法 - 获取，但不移除此 队列的头。

• offer（E o） - 将指定的元素插入此队列中，如果
  可能。

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

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

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

Answer 2

考虑来自Apache 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是第一个与固定 大小如果完全替换其最古老的元素先出缓冲器。
• CircularFifoBuffer的移除顺序基于插入 顺序;元素将以与添加的 相同的顺序被删除。迭代顺序与删除顺序相同。
• 添加（Object），BoundedFifoBuffer.remove（）和 BoundedFifoBuffer.get（）操作全部在恒定时间执行。 所有其他操作在线性时间或更糟的情况下执行。

但是，您应该考虑它的局限性 - 例如，您不能将缺少的时间序列添加到此集合中，因为它不允许空值。

Answer 3

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

编辑：这是原来的（虽然略有不同）代码：CircularArrayList for 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 4

如果您需要

• O（1）插入和移除
• O（1）分度到内饰元素
从单个线程只
• 通用元素类型

那么你就可以以这种方式使用this 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

由于Java 1.6，有ArrayDeque，它实现Queue，似乎是比LinkedList更快，更高效的内存和不具备ArrayBlockingQueue的线程同步开销：从API文档：“这个类在用作堆栈时可能比Stack快，并且在用作队列时比LinkedList快。“

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

Answer 6

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

非阻塞队列试图将新元素添加到队列时自动从队列的头部 逐出元件而它 已满。驱逐队列必须配置为最大尺寸。 每次将元素添加到完整队列时，队列会自动删除其头元素。这与传统的有界的队列有所不同，当队列满时阻塞或拒绝新元素。

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

使用例：

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 7

先前给出的例子没有被完全满足我的需求，所以我写了我自己的队列，允许以下功能：迭代，索引访问，的indexOf，lastIndexOf，获得第一，获取最后一个，提供剩余容量，扩展容量，最后一个出列，首先出列，入队/添加元素，出列/删除元素，subQueueCopy，subArrayCopy，toArray，快照，基本知识如大小，移除或包含。

EjectingQueue

EjectingIntQueue

Answer 8

一个非常有趣的项目是破坏者。它有一个环缓冲器，用于我在金融应用领域所知道的。

在这里看到：code of ringbuffer