Мне нужна очередь фиксированного размера. Когда я добавляю элемент и очередь заполняется, он должен автоматически удалять самый старый элемент.

Есть ли для этого реализация на Java?

В языке Java и среде выполнения нет существующей реализации. Все очереди расширяют AbstractQueue , и в его документе четко указано, что добавление элемента в полную очередь всегда заканчивается исключением. Было бы лучше (и довольно просто) обернуть Queue в собственный класс для обеспечения необходимой вам функциональности.

Еще раз, поскольку все очереди являются дочерними по отношению к AbstractQueue, просто используйте это как свой внутренний тип данных, и у вас должна быть гибкая реализация, работающая практически в кратчайшие сроки :-)

ОБНОВИТЬ:

Как указано ниже, доступны две открытые реализации (этот ответ довольно старый, ребята!), Подробности см. В этом ответе .

На самом деле LinkedHashMap делает именно то, что вы хотите. Вам нужно переопределить removeEldestEntryметод.

Пример очереди с максимум 10 элементами:

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

Если removeEldestEntry возвращает true, самая старая запись удаляется с карты.

Да, два

Из моего собственного повторяющегося вопроса с этим правильным ответом я узнал о двух:

• EvictingQueueв Google Guava
• CircularFifoQueueв Apache Commons

Я продуктивно пользовался Гуавой EvictingQueue, работал хорошо.

Чтобы создать экземпляр EvictingQueueвызова статического фабричного метода createи указать свой максимальный размер.

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

Я только что реализовал очередь фиксированного размера таким образом:

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

Это то, что я сделал с Queueупаковкой. LinkedListЭто фиксированный размер, который я указываю здесь - 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");
.....

Я думаю, что вы описываете круговую очередь. Вот пример , и вот лучше один

Этот класс выполняет свою работу, используя композицию вместо наследования (другие ответы здесь), что устраняет возможность определенных побочных эффектов (как описано Джошем Блохом в Essential Java). Обрезка нижележащего LinkedList происходит в методах add, addAll и 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);
    }
}

Использование и результат тестирования:

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

Звучит как обычный список, в котором метод добавления содержит дополнительный фрагмент, который обрезает список, если он становится слишком длинным.

Если это слишком просто, вам, вероятно, нужно отредактировать описание проблемы.

Также см. Этот вопрос SO или ArrayBlockingQueue (будьте осторожны с блокировкой, это может быть нежелательным в вашем случае).

Не совсем понятно, какие у вас требования, которые заставили вас задать этот вопрос. Если вам нужна структура данных фиксированного размера, вы можете также изучить другие политики кэширования. Однако, поскольку у вас есть очередь, я предполагаю, что вы ищете какой-то тип функциональности маршрутизатора. В этом случае я бы выбрал кольцевой буфер: массив с первым и последним индексами. Всякий раз, когда добавляется элемент, вы просто увеличиваете индекс последнего элемента, а когда элемент удаляется, увеличиваете индекс первого элемента. В обоих случаях сложение выполняется по модулю размера массива, и обязательно увеличивайте другой индекс, когда это необходимо, то есть когда очередь заполнена или пуста.

Кроме того, если это приложение типа маршрутизатора, вы также можете поэкспериментировать с таким алгоритмом, как Random Early Dropping (RED), который случайным образом удаляет элементы из очереди еще до того, как она будет заполнена. В некоторых случаях было обнаружено, что RED имеет лучшую общую производительность, чем простой метод, позволяющий очереди заполняться перед отбрасыванием.

На самом деле вы можете написать свой собственный impl на основе LinkedList, это довольно просто, просто переопределите метод добавления и выполните команду.

Я думаю, что лучший подходящий ответ - это другой вопрос .

В коллекциях Apache Commons 4 есть CircularFifoQueue, которую вы ищете. Цитата из javadoc:

CircularFifoQueue - это очередь «первым пришел - первый вышел» с фиксированным размером, которая заменяет самый старый элемент, если он заполнен.

Простое решение, ниже - очередь "String"

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

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

Обратите внимание, что это не будет поддерживать порядок элементов в очереди, но заменит самую старую запись.

Как сказано в ООП, мы должны предпочесть композицию наследованию.

Вот мое решение с учетом этого.

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