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

Question

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.

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

Answer 1

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, ya que todas las colas son hijos de AbstractQueue, sólo tiene que usar eso como su tipo de datos interna y usted debe tener una aplicación flexible correr en prácticamente ningún momento :-)

ACTUALIZACIÓN:

Como se ha señalado a continuación, hay dos implementaciones abiertas disponibles (esta respuesta es bastante antigua, amigos!), vea this answer para más detalles.

Answer 2

Suena como una lista normal 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 del problema.

Answer 3

También vea this SO question, o ArrayBlockingQueue (tenga cuidado con el bloqueo, esto puede ser no deseado en su caso).

Answer 4

Creo que lo que estás describiendo es una cola circular. Aquí hay un example y aquí hay un better uno

Answer 5

No está del todo claro qué requisitos tiene que le hayan hecho 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 tipo enrutador, es posible que también desee experimentar con un algoritmo como Alejamiento anticipado aleatorio (ROJO), que suelta elementos de la cola aleatoriamente 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.

Answer 6

Actualmente, el LinkedHashMap hace exactamente lo que quiere. Debe anular el método removeEldestEntry.

Ejemplo para una cola con 10 elementos max:

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

Si el "removeEldestEntry" devuelve verdadero, la entrada mayor se retira del mapa.

Answer 7

Actualmente, usted puede escribir su propia impl basada en LinkedList, es bastante directa, simplemente anule el método de agregar y haga el personal.

Answer 8

Esta clase hace el trabajo usando composición en lugar de herencia (otras respuestas aquí) que elimina la posibilidad de ciertos efectos secundarios (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<T> implements Queue<T>, Iterable<T> { 

    private final int limit; 
    private final LinkedList<T> list = new LinkedList<T>(); 

    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<T> iterator() { 
     return list.iterator(); 
    } 

    @Override 
    public Object[] toArray() { 
     return list.toArray(); 
    } 

    @Override 
    public <T> 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<? extends T> 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(); 
    } 
} 

Answer 9

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

public class LimitedSizeQueue<K> extends ArrayList<K> { 

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

Answer 10

Sí, dos

De my own duplicate question con this correct answer, supe de dos:

• EvictingQueue en Google Guava
• CircularFifoQueue en Apache Commons

hice uso productivo de la guayaba EvictingQueue, funcionó bien.

Answer 11

Creo que la mejor respuesta coincidente es this other question.

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.

Answer 12

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

public static Queue<String> pageQueue; 

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

Answer 13

una solución sencilla, a continuación es una cola de "Cadena"

LinkedHashMap<Integer, String> queue; 
int queueKeysCounter; 

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

Tenga en cuenta que esto no va a mantener el orden de los elementos de la cola, pero va a sustituir a la entrada más antigua.