Ограниченная по размеру очередь, которая содержит последние N элементов в Java

Question

Очень простой и быстрый вопрос по библиотекам Java: есть ли готовый класс, который реализует Queue с фиксированным максимальным размером - то есть он всегда позволяет добавлять элементы, но он будет молча удалять элементы заголовка, чтобы вместить пространство для вновь добавленных элементов.

Конечно, реализовать это вручную тривиально:

import java.util.LinkedList;

public class LimitedQueue<E> extends LinkedList<E> {
    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > limit) { super.remove(); }
        return true;
    }
}

Насколько я вижу, в Java stdlibs нет стандартной реализации, но может быть, есть такая в Apache Commons или что-то в этом роде?

Answer 1

Коллекции Apache commons 4 имеют CircularFifoQueue <> , который вы ищете.Цитирование javadoc:

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

    import java.util.Queue;
    import org.apache.commons.collections4.queue.CircularFifoQueue;

    Queue<Integer> fifo = new CircularFifoQueue<Integer>(2);
    fifo.add(1);
    fifo.add(2);
    fifo.add(3);
    System.out.println(fifo);

    // Observe the result: 
    // [2, 3]

Если выиспользуя более старую версию коллекций Apache (3.x), вы можете использовать CircularFifoBuffer , который в основном то же самое без шаблонов.

Обновление : обновленоответить на следующий выпуск сборников общих версий версии 4, который поддерживает дженерики.

Answer 2

У Guava теперь есть EvictingQueue , неблокирующая очередь, которая автоматически вытесняет элементы из головы очереди при попытке добавить новые элементы в очередь, и она заполнена.

import java.util.Queue;
import com.google.common.collect.EvictingQueue;

Queue<Integer> fifo = EvictingQueue.create(2); 
fifo.add(1); 
fifo.add(2); 
fifo.add(3); 
System.out.println(fifo); 

// Observe the result: 
// [2, 3]

Answer 3

Мне нравится решение @FractalizeR.Но я бы дополнительно сохранил и вернул значение из super.add (o)!

public class LimitedQueue<E> extends LinkedList<E> {

    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
           super.remove();
        }
        return added;
    }
}

Answer 4

Использовать состав не расширяет (да, я имею в виду расширяет, как в ссылке на ключевое слово extends в Java, и да, это наследование). Композиция выше, потому что она полностью защищает вашу реализацию, позволяя вам изменять реализацию, не влияя на пользователей вашего класса.

Я рекомендую попробовать что-то вроде этого (я печатаю прямо в этом окне, поэтому покупатель остерегается синтаксических ошибок):

public LimitedSizeQueue implements Queue
{
  private int maxSize;
  private LinkedList storageArea;

  public LimitedSizeQueue(final int maxSize)
  {
    this.maxSize = maxSize;
    storageArea = new LinkedList();
  }

  public boolean offer(ElementType element)
  {
    if (storageArea.size() < maxSize)
    {
      storageArea.addFirst(element);
    }
    else
    {
      ... remove last element;
      storageArea.addFirst(element);
    }
  }

  ... the rest of this class

Лучший вариант (на основе ответа Асафа) может заключаться в том, чтобы обернуть Apache Collections CircularFifoBuffer универсальным классом. Например:

public LimitedSizeQueue<ElementType> implements Queue<ElementType>
{
    private int maxSize;
    private CircularFifoBuffer storageArea;

    public LimitedSizeQueue(final int maxSize)
    {
        if (maxSize > 0)
        {
            this.maxSize = maxSize;
            storateArea = new CircularFifoBuffer(maxSize);
        }
        else
        {
            throw new IllegalArgumentException("blah blah blah");
        }
    }

    ... implement the Queue interface using the CircularFifoBuffer class
}

Answer 5

Единственное, что я знаю, что имеет ограниченное пространство - это интерфейс BlockingQueue (который, например, реализован классом ArrayBlockingQueue) - но они не удаляют первый элемент, если он заполнен, а вместо этого блокируют операцию put до тех пор, пока пространство не станет свободным (удалено)другим потоком).

Насколько мне известно, ваша тривиальная реализация - самый простой способ получить такое поведение.

Answer 6

LRUMap - это еще одна возможность, также от Apache Commons.

http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/LRUMap.html

Answer 7

Вы можете использовать MinMaxPriorityQueue из Google Guava , из javadoc:

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

Answer 8

    public class ArrayLimitedQueue<E> extends ArrayDeque<E> {

    private int limit;

    public ArrayLimitedQueue(int limit) {
        super(limit + 1);
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
            super.remove();
        }
        return added;
    }

    @Override
    public void addLast(E e) {
        super.addLast(e);
        while (size() > limit) {
            super.removeLast();
        }
    }

    @Override
    public boolean offerLast(E e) {
        boolean added = super.offerLast(e);
        while (added && size() > limit) {
            super.pollLast();
        }
        return added;
    }
}