Eu preciso de uma fila com um tamanho fixo. Quando adiciono um elemento e a fila está cheia, ele deve remover automaticamente o elemento mais antigo.

Existe uma implementação existente para isso em Java?

Não há implementação existente no Java Language and Runtime. Todas as filas estendem o AbstractQueue e seu documento afirma claramente que a adição de um elemento a uma fila completa sempre termina com uma exceção. Seria melhor (e bastante simples) agrupar uma Fila em uma classe própria para ter a funcionalidade necessária.

Mais uma vez, como todas as filas são filhos do AbstractQueue, basta usá-lo como seu tipo de dados interno e você deverá ter uma implementação flexível em execução praticamente em nenhum momento :-)

ATUALIZAR:

Conforme descrito abaixo, existem duas implementações abertas disponíveis (essa resposta é bastante antiga, pessoal!), Consulte esta resposta para obter detalhes.

Na verdade, o LinkedHashMap faz exatamente o que você deseja. Você precisa substituir o removeEldestEntrymétodo

Exemplo para uma fila com no máximo 10 elementos:

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

Se "removeEldestEntry" retornar true, a entrada mais antiga será removida do mapa.

Sim dois

Da minha própria pergunta duplicada com esta resposta correta , aprendi de duas:

• EvictingQueueno Google Guava
• CircularFifoQueueno Apache Commons

Fiz uso produtivo da goiaba EvictingQueue, funcionou bem.

Para instanciar uma EvictingQueuechamada, o método estático de fábrica createe especifique seu tamanho máximo.

EvictingQueue< Person > people = com.google.common.collect.EvictingQueue.create( 100 ) ;  // Set maximum size to 100. 

Acabei de implementar uma fila de tamanho fixo desta maneira:

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

Isto é o que eu fiz com Queueembrulhado LinkedList, é de tamanho fixo que eu cito aqui é 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");
.....

Eu acho que o que você está descrevendo é uma fila circular. Aqui está um exemplo e aqui é um melhor um

Essa classe faz o trabalho usando composição em vez de herança (outras respostas aqui), o que remove a possibilidade de certos efeitos colaterais (conforme coberto por Josh Bloch no Essential Java). O corte do LinkedList subjacente ocorre nos métodos add, addAll e 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 e resultado do teste:

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

Soa como uma lista comum, em que o método add contém um trecho extra que trunca a lista se ela for muito longa.

Se isso for muito simples, você provavelmente precisará editar a descrição do seu problema.

Consulte também esta questão do SO , ou ArrayBlockingQueue (tenha cuidado com o bloqueio, isso pode ser indesejável no seu caso).

Não está claro quais requisitos você o levou a fazer essa pergunta. Se você precisar de uma estrutura de dados de tamanho fixo, também poderá procurar políticas de armazenamento em cache diferentes. No entanto, como você tem uma fila, meu melhor palpite é que você está procurando algum tipo de funcionalidade do roteador. Nesse caso, eu usaria um buffer de anel: uma matriz que possui um primeiro e último índice. Sempre que um elemento é adicionado, você apenas incrementa o índice do último elemento e, quando um elemento é removido, incrementa o índice do primeiro elemento. Nos dois casos, a adição é realizada modulando o tamanho da matriz e certifique-se de incrementar o outro índice quando necessário, ou seja, quando a fila estiver cheia ou vazia.

Além disso, se for um aplicativo do tipo roteador, convém experimentar um algoritmo como o Random Early Dropping (RED), que remove elementos da fila aleatoriamente antes mesmo de ser preenchido. Em alguns casos, verificou-se que o RED possui um desempenho geral melhor do que o método simples de permitir que a fila se encha antes de cair.

Na verdade, você pode escrever seu próprio impl com base no LinkedList, é bastante direto, basta substituir o método add e fazer a equipe.

Eu acho que a melhor resposta correspondente é dessa outra pergunta .

O Apache commons collections 4 possui um CircularFifoQueue, que é o que você está procurando. Citando o javadoc:

CircularFifoQueue é uma fila primeiro a entrar, primeiro a sair, com um tamanho fixo que substitui o elemento mais antigo se estiver cheio.

Uma solução simples, abaixo, é uma fila de "String"

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

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

Observe que isso não manterá a ordem dos itens na fila, mas substituirá a entrada mais antiga.

Como é recomendado nas OOPs, devemos preferir Composição ao invés de Herança

Aqui está minha solução tendo isso em mente.

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