Cola de tamaño limitado que contiene los últimos N elementos en Java

Una pregunta muy simple y rápida sobre las bibliotecas de Java: ¿hay una clase preparada que implemente una Queuecon un tamaño máximo fijo?

Por supuesto, es trivial implementarlo manualmente:

import java.util.LinkedList;

public class LimitedQueue<E> extends LinkedList<E> {
    private int limit;

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

    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > limit) { super.remove(); }
        return true;
    }
}

Por lo que veo, no hay una implementación estándar en las stdlibs de Java, pero ¿puede haber una en Apache Commons o algo así?

Apache commons collections 4 tiene un CircularFifoQueue <> que es lo que está buscando. Citando al javadoc:

CircularFifoQueue es una cola de primero en entrar, primero en salir con un tamaño fijo que reemplaza su elemento más antiguo si está lleno.

    import java.util.Queue;
    import org.apache.commons.collections4.queue.CircularFifoQueue;

    Queue<Integer> fifo = new CircularFifoQueue<Integer>(2);
    fifo.add(1);
    fifo.add(2);
    fifo.add(3);
    System.out.println(fifo);

    // Observe the result: 
    // [2, 3]

Si está utilizando una versión anterior de las colecciones comunes de Apache (3.x), puede utilizar el CircularFifoBuffer, que es básicamente lo mismo sin genéricos.

Actualización : respuesta actualizada después del lanzamiento de la versión 4 de colecciones comunes que admite genéricos.

Guava ahora tiene un EvictingQueue , una cola sin bloqueo que desaloja automáticamente los elementos del encabezado de la cola cuando intenta agregar nuevos elementos a la cola y está llena.

import java.util.Queue;
import com.google.common.collect.EvictingQueue;

Queue<Integer> fifo = EvictingQueue.create(2); 
fifo.add(1); 
fifo.add(2); 
fifo.add(3); 
System.out.println(fifo); 

// Observe the result: 
// [2, 3]

Me gusta la solución @FractalizeR. ¡Pero además mantendría y devolvería el valor de super.add (o)!

public class LimitedQueue<E> extends LinkedList<E> {

    private int limit;

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

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
           super.remove();
        }
        return added;
    }
}

Usar composición no se extiende (sí, me refiero a extensiones, como en una referencia a la palabra clave extend en java y sí, esto es herencia). La composición es superior porque protege completamente su implementación, permitiéndole cambiarla sin afectar a los usuarios de su clase.

Recomiendo probar algo como esto (estoy escribiendo directamente en esta ventana, así que el comprador tenga cuidado con los errores de sintaxis):

public LimitedSizeQueue implements Queue
{
  private int maxSize;
  private LinkedList storageArea;

  public LimitedSizeQueue(final int maxSize)
  {
    this.maxSize = maxSize;
    storageArea = new LinkedList();
  }

  public boolean offer(ElementType element)
  {
    if (storageArea.size() < maxSize)
    {
      storageArea.addFirst(element);
    }
    else
    {
      ... remove last element;
      storageArea.addFirst(element);
    }
  }

  ... the rest of this class

Una mejor opción (basada en la respuesta de Asaf) podría ser envolver el Apache Collections CircularFifoBuffer con una clase genérica. Por ejemplo:

public LimitedSizeQueue<ElementType> implements Queue<ElementType>
{
    private int maxSize;
    private CircularFifoBuffer storageArea;

    public LimitedSizeQueue(final int maxSize)
    {
        if (maxSize > 0)
        {
            this.maxSize = maxSize;
            storateArea = new CircularFifoBuffer(maxSize);
        }
        else
        {
            throw new IllegalArgumentException("blah blah blah");
        }
    }

    ... implement the Queue interface using the CircularFifoBuffer class
}

Lo único que sé que tiene espacio limitado es la interfaz BlockingQueue (que, por ejemplo, está implementada por la clase ArrayBlockingQueue), pero no eliminan el primer elemento si está lleno, sino que bloquean la operación de colocación hasta que el espacio esté libre (eliminado por otro hilo )

Que yo sepa, su implementación trivial es la forma más fácil de obtener ese comportamiento.

Puede usar un MinMaxPriorityQueue de Google Guava , de javadoc:

Se puede configurar una cola de prioridad min-max con un tamaño máximo. Si es así, cada vez que el tamaño de la cola excede ese valor, la cola elimina automáticamente su elemento más grande de acuerdo con su comparador (que podría ser el elemento que se acaba de agregar). Esto es diferente de las colas acotadas convencionales, que bloquean o rechazan nuevos elementos cuando están llenos.

Un LRUMap es otra posibilidad, también de Apache Commons.

http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/LRUMap.html

    public class ArrayLimitedQueue<E> extends ArrayDeque<E> {

    private int limit;

    public ArrayLimitedQueue(int limit) {
        super(limit + 1);
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
            super.remove();
        }
        return added;
    }

    @Override
    public void addLast(E e) {
        super.addLast(e);
        while (size() > limit) {
            super.removeLast();
        }
    }

    @Override
    public boolean offerLast(E e) {
        boolean added = super.offerLast(e);
        while (added && size() > limit) {
            super.pollLast();
        }
        return added;
    }
}