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

tamaño de un array java

Question

Una pregunta muy simple y rápida sobre las bibliotecas Java: ¿hay una clase preparada que implemente una Queue con un tamaño máximo fijo? Es decir, siempre permite la adición de elementos, pero eliminará silenciosamente los elementos principales para acomodar el espacio para los elementos recién agregados.

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 stdlibs de Java, pero ¿puede haber una en Apache Commons o algo así?

Answer 1

Apache commons collections 4 tiene un CircularFifoQueue<> que es lo que estás buscando. Citando el 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 de Apache commons (3.x), puede usar 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 commons collections que admite genéricos.

Answer 2

Guava ahora tiene una EvictingQueue , una cola sin bloqueo que expulsa automáticamente elementos del jefe 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]

Answer 3

La composición de uso no se extiende (sí, quiero decir se extiende, como en una referencia a la palabra clave extends en java y sí, esto es herencia). La composición es más completa porque protege por completo su implementación, lo que le permite cambiar la implementación sin afectar a los usuarios de su clase.

Recomiendo probar algo como esto (estoy escribiendo directamente en esta ventana, para 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 ajustar las Colecciones de Apache 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
}

Answer 4

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

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

Answer 5

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;
    }
}

Answer 6

Puede usar MinMaxPriorityQueue de Google Guava , desde 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 acaba de agregar). Esto es diferente de las colas limitadas convencionales, que bloquean o rechazan nuevos elementos cuando están llenos.

Answer 7

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

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

Answer 8

    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;
    }
}