Kolejka o ograniczonym rozmiarze, która przechowuje ostatnie N elementów w Javie

Bardzo proste i szybkie pytanie o biblioteki Java: czy istnieje gotowa klasa, która implementuje a Queueo ustalonym maksymalnym rozmiarze - tzn. Zawsze pozwala na dodawanie elementów, ale po cichu usunie elementy główne, aby pomieścić miejsce dla nowo dodanych elementów.

Oczywiście wdrożenie go ręcznie jest trywialne:

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

O ile mi wiadomo, nie ma standardowej implementacji w stdlibs Java, ale może jest taka w Apache Commons czy coś takiego?

Kolekcje Apache commons 4 mają CircularFifoQueue <>, czego szukasz. Cytując javadoc:

CircularFifoQueue to kolejka „pierwsze weszło pierwsze wyszło” o stałym rozmiarze, która zastępuje najstarszy element, jeśli jest pełny.

    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]

Jeśli używasz starszej wersji wspólnych kolekcji Apache (3.x), możesz użyć CircularFifoBuffer, który jest zasadniczo taki sam bez generycznych.

Aktualizacja : zaktualizowano odpowiedź po wydaniu wspólnej kolekcji w wersji 4, która obsługuje generyczne.

Guava ma teraz EvictingQueue , kolejkę nieblokującą, która automatycznie eksmituje elementy z głowy kolejki podczas próby dodania nowych elementów do kolejki i jest pełna.

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]

Lubię rozwiązanie @FractalizeR. Ale dodatkowo zatrzymałbym i zwrócił wartość z 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;
    }
}

Użyj kompozycji nie rozszerza (tak mam na myśli rozszerzenie, ponieważ w odniesieniu do słowa kluczowego extends w Javie i tak jest to dziedziczenie). Kompozycja jest lepsza, ponieważ całkowicie chroni twoją implementację, pozwalając ci na zmianę implementacji bez wpływu na użytkowników twojej klasy.

Polecam wypróbowanie czegoś takiego (piszę bezpośrednio w tym oknie, więc kupujący uważaj na błędy składniowe):

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

Lepszą opcją (na podstawie odpowiedzi Asafa) może być owinięcie CircularFifoBuffer kolekcji Apache klasą ogólną. Na przykład:

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
}

Jedyne, co wiem, że ma ograniczoną przestrzeń to interfejs BlockingQueue (który jest np. Zaimplementowany przez klasę ArrayBlockingQueue) - ale nie usuwają pierwszego elementu, jeśli są wypełnione, ale zamiast tego blokują operację put, dopóki przestrzeń nie będzie wolna (usuwana przez inny wątek ).

Według mojej wiedzy trywialna implementacja jest najprostszym sposobem na uzyskanie takiego zachowania.

Możesz użyć MinMaxPriorityQueue z Google Guava , z javadoc:

Kolejka priorytetowa min. Maks. Może być skonfigurowana z maksymalnym rozmiarem. Jeśli tak, za każdym razem, gdy rozmiar kolejki przekracza tę wartość, kolejka automatycznie usuwa swój największy element zgodnie z jego komparatorem (którym może być właśnie dodany element). Różni się to od konwencjonalnych ograniczonych kolejek, które blokują lub odrzucają nowe elementy, gdy są pełne.

LRUMap to kolejna możliwość, również z Apache Commons.

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

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