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?

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.

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.

Si, dos

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

• EvictingQueueen Google guayaba
• CircularFifoQueueen Apache Commons

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. 

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

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");
.....

Creo que lo que estás describiendo 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 (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();
    }
}

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

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.

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

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.

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

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.

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.

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