¿Hay una cola de tamaño fijo que elimina elementos excesivos?

Necesito una cola con un tamaño fijo. Cuando agrego un elemento y la cola está llena, debe eliminar automáticamente el elemento más antiguo.

¿Hay una implementación existente para esto en Java?

No existe una implementación en Java Language y Runtime. Todas las colas extienden AbstractQueue , y su documento establece claramente que agregar un elemento a una cola completa siempre termina con una excepción. Sería mejor (y bastante simple) incluir una cola en una clase propia para tener la funcionalidad que necesita.

Una vez más, debido a que todas las colas son elementos secundarios de AbstractQueue, simplemente utilícela como su tipo de datos interno y debe tener una implementación flexible que se ejecute en prácticamente ningún momento 🙂

ACTUALIZAR:

Como se describe a continuación, hay dos implementaciones abiertas disponibles (esta respuesta es bastante antigua, amigos!), Vea esta respuesta para más detalles.

En realidad, LinkedHashMap hace exactamente lo que quieres. removeEldestEntry anular el método removeEldestEntry .

Ejemplo para una cola con un máximo de 10 elementos:

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

Si “removeEldestEntry” devuelve verdadero, la entrada más antigua se eliminará del mapa.

Si, dos

De mi propia pregunta duplicada con esta respuesta correcta , aprendí de dos:

  • EvictingQueue en Google Guava
  • CircularFifoQueue en Apache Commons

Hice un uso productivo de la Guava EvictingQueue , funcionó bien.

Acabo de implementar una cola de tamaño fijo de esta manera:

 public class LimitedSizeQueue extends ArrayList { 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); } } 

Esto es lo que hice con Queue envuelto con LinkedList , es de tamaño fijo, lo que doy aquí es 2;

 public static Queue pageQueue; pageQueue = new LinkedList(){ 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"); ..... 

Creo que lo que describes es una cola circular. Aquí hay un ejemplo y aquí hay uno mejor

Esta clase hace el trabajo usando composición en lugar de herencia (otras respuestas aquí) que elimina la posibilidad de ciertos efectos secundarios (tal como lo cubre Josh Bloch en Essential Java). El recorte de LinkedList subyacente se produce en los métodos add, addAll y offer.

 import java.util.Collection; import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; public class LimitedQueue implements Queue, Iterable { private final int limit; private final LinkedList list = new LinkedList(); 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 iterator() { return list.iterator(); } @Override public Object[] toArray() { return list.toArray(); } @Override public  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 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(); } } 

Suena como una lista ordinaria donde el método de agregar contiene un fragmento adicional que trunca la lista si es demasiado larga.

Si eso es demasiado simple, entonces probablemente necesite editar la descripción de su problema.

También vea esta pregunta SO , o ArrayBlockingQueue (tenga cuidado con el locking, esto puede ser no deseado en su caso).

No está del todo claro qué requisitos tienes que te hayan llevado a hacer esta pregunta. Si necesita una estructura de datos de tamaño fijo, es posible que también desee ver las diferentes políticas de almacenamiento en caché. Sin embargo, como tiene una cola, mi mejor opción es que está buscando algún tipo de funcionalidad de enrutador. En ese caso, iría con un buffer de anillo: un array que tiene un primer y último índice. Cada vez que se agrega un elemento, simplemente se incrementa el índice del último elemento, y cuando se elimina un elemento, se incrementa el índice del primer elemento. En ambos casos, la adición se realiza en función del tamaño de la matriz, y asegúrese de incrementar el otro índice cuando sea necesario, es decir, cuando la cola esté llena o vacía.

Además, si se trata de una aplicación de tipo enrutador, es posible que también desee experimentar con un algoritmo, como Alejamiento anticipado aleatorio (RED), que suelta elementos de la cola al azar incluso antes de que se llene. En algunos casos, se ha encontrado que RED tiene un mejor rendimiento general que el método simple de permitir que la cola se llene antes de caer.

De hecho, puedes escribir tu propia impl basada en LinkedList, es bastante directa, simplemente anula el método add y haz el staff.

Creo que la mejor respuesta coincidente es de esta otra pregunta .

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.

Una solución simple, a continuación es una cola de “Cadena”

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

Tenga en cuenta que esto no mantendrá el orden de los elementos en la cola, pero reemplazará la entrada más antigua.

 public class CircularQueue extends LinkedList { private int capacity = 10; public CircularQueue(int capacity){ this.capacity = capacity; } @Override public boolean add(E e) { if(size() >= capacity) removeFirst(); return super.add(e); } } 

Uso y resultado de la prueba:

 public static void main(String[] args) { CircularQueue queue = new CircularQueue<>(3); queue.add("a"); queue.add("b"); queue.add("c"); System.out.println(queue.toString()); //[a, b, c] String first = queue.pollFirst(); //a System.out.println(queue.toString()); //[b,c] queue.add("d"); queue.add("e"); queue.add("f"); System.out.println(queue.toString()); //[d, e, f] }