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

127

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

¿Existe una implementación para esto en Java?

c0d3x
fuente

Respuestas:

19

No existe una implementación existente en Java Language and 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ícelo como su tipo de datos interno y debería tener una implementación flexible ejecutándose en muy poco tiempo :-)

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.

Moritz
fuente
44
Use Queue en lugar de AbstractQueue ... puede haber colas que implementen la interfaz pero no extiendan la clase abstracta.
TofuBeer
1
En Python puede usar un collection.dequecon un especificado maxlen.
Jonas Gröger
2
ACTUALIZACIÓN Ahora hay dos clases disponibles. No es necesario que escribas el tuyo. Vea mi respuesta en esta página.
Basil Bourque
108

En realidad, LinkedHashMap hace exactamente lo que quieres. Necesita anular el removeEldestEntrymétodo.

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

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

Si "removeEldestEntry" devuelve verdadero, la entrada más antigua se elimina del mapa.

Mavrik
fuente
77
esto en realidad no hace lo que hace una cola, ¿cómo puedo recuperar el más nuevo? ¿objeto?
Alex
69

Si, dos

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


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

Para instanciar una EvictingQueuellamada, utilice el método de fábrica estático createy especifique su tamaño máximo.

EvictingQueue< Person > people = com.google.common.collect.EvictingQueue.create( 100 ) ;  // Set maximum size to 100. 
Albahaca Bourque
fuente
... y si no puede usar Commons Collection 4.0, entonces CircularFifoBuffer parece ser similar a CircularFifoQueue en v 3.0.
Sridhar Sarnobat
CircularFifoQueueel enlace está muerto, use en su lugar commons.apache.org/proper/commons-collections/apidocs/org/…
user7294900
@ user7294900 Gracias, enlace arreglado. Para su información, Stack Overflow lo invita a realizar tales ediciones directamente a una Respuesta usted mismo. Cualquiera puede editar, no solo el autor original. Stack Overflow está destinado a gustar más de Wikipedia en ese sentido.
Basil Bourque
@BasilBourque sí, pero tales ediciones pueden ser rechazadas incluso por mí al cambiar los enlaces es un área gris
user7294900
18

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

    public K getYoungest() {
        return get(size() - 1);
    }

    public K getOldest() {
        return get(0);
    }
}
Rugido Skullestad
fuente
1
Debería serremoveRange(0, size() - maxSize)
Ahmed Hegazy
@AhmedHegazy removeRange (0, size () - maxSize - 1) es correcto
Ashish Doneriya
Estoy de acuerdo con Amhed arriba. Elimine el - 1. De lo contrario, a la capacidad máxima, terminará con una matriz que es maxSize + 1 ya que estamos hablando de 0 basado. Por ejemplo. Si maxSize = 50, al agregar un nuevo objeto, la fórmula removeRange en la publicación original será 51 - 50 - 1 = 0 (es decir, nada eliminado).
Etep
8

Esto es lo que hice con Queueenvuelto LinkedList, tiene un tamaño fijo 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");
.....
Berkay Turancı
fuente
4

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


fuente
4

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 la 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();
    }
}
Dave Moten
fuente
3
public class CircularQueue<E> extends LinkedList<E> {
    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<String> 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]
}
León
fuente
0

Suena como una lista ordinaria donde el método add contiene un fragmento adicional que trunca la lista si se hace demasiado larga.

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

Thorbjørn Ravn Andersen
fuente
En realidad, necesitaría eliminar el primer elemento (es decir, el primero), truncar eliminaría el último elemento. Todavía práctico con LinkedList.
MAK
0

No está muy claro qué requisitos tiene que lo llevaron a hacer esta pregunta. Si necesita una estructura de datos de tamaño fijo, es posible que también desee ver diferentes políticas de almacenamiento en caché. Sin embargo, dado que tiene una cola, mi mejor conjetura es que está buscando algún tipo de funcionalidad de enrutador. En ese caso, iría con un buffer de anillo: una matriz que tiene un primer y último índice. Cada vez que se agrega un elemento, simplemente incrementa el índice del último elemento, y cuando se elimina un elemento, incrementa el índice del primer elemento. En ambos casos, la adición se realiza por módulo el 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 Random Early Dropping (RED), que elimina elementos de la cola al azar, incluso antes de que se llene. En algunos casos, se ha descubierto que RED tiene un mejor rendimiento general que el método simple de permitir que la cola se llene antes de caer.

JaakkoK
fuente
0

En realidad, puede escribir su propio impl basado en LinkedList, es bastante sencillo, simplemente anule el método de agregar y haga el personal.

Miguel
fuente
0

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 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.

Diego
fuente
0

Una solución simple, 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 mantendrá el orden de los elementos en la cola, pero reemplazará la entrada más antigua.

M. Usman Khan
fuente
0

Como se recomienda en los OOP, deberíamos preferir la Composición a la Herencia

Aquí mi solución teniendo eso en cuenta.

package com.choiceview;

import java.util.ArrayDeque;

class Ideone {
    public static void main(String[] args) {
        LimitedArrayDeque<Integer> q = new LimitedArrayDeque<>(3);
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q);

        q.add(4);
        // First entry ie 1 got pushed out
        System.out.println(q);
    }
}

class LimitedArrayDeque<T> {

    private int maxSize;
    private ArrayDeque<T> queue;

    private LimitedArrayDeque() {

    }

    public LimitedArrayDeque(int maxSize) {
        this.maxSize = maxSize;
        queue = new ArrayDeque<T>(maxSize);
    }

    public void add(T t) {
        if (queue.size() == maxSize) {
            queue.removeFirst();
        }
        queue.add(t);
    }

    public boolean remove(T t) {
        return queue.remove(t);
    }

    public boolean contains(T t) {
        return queue.contains(t);
    }

    @Override
    public String toString() {
        return queue.toString();
    }
}
Abhishek
fuente