Warteschlange mit begrenzter Größe, die die letzten N Elemente in Java enthält

Eine sehr einfache und schnelle Frage zu Java-Bibliotheken: Gibt es eine vorgefertigte Klasse, die eine Queuemit einer festen maximalen Größe implementiert - dh sie ermöglicht immer das Hinzufügen von Elementen, entfernt jedoch stillschweigend Kopfelemente, um Platz für neu hinzugefügte Elemente zu schaffen.

Natürlich ist es trivial, es manuell zu implementieren:

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

Soweit ich sehe, gibt es keine Standardimplementierung in Java stdlibs, aber vielleicht gibt es eine in Apache Commons oder so?

Apache Commons Collections 4 verfügt über eine CircularFifoQueue <> der Sie suchen. Javadoc zitieren:

CircularFifoQueue ist eine First-In-First-Out-Warteschlange mit einer festen Größe, die das älteste Element ersetzt, wenn es voll ist.

    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]

Wenn Sie eine ältere Version der Apache Commons-Sammlungen (3.x) verwenden, können Sie den CircularFifoBuffer verwenden, der ohne Generika im Grunde dasselbe ist.

Update : Aktualisierte Antwort nach Veröffentlichung von Commons Collections Version 4, die Generika unterstützt.

Guava hat jetzt eine EvictingQueue , eine nicht blockierende Warteschlange, die automatisch Elemente aus dem Kopf der Warteschlange entfernt, wenn versucht wird, neue Elemente zur Warteschlange hinzuzufügen, und diese ist voll.

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]

Ich mag die @ FractalizeR-Lösung. Aber ich würde zusätzlich den Wert von super.add (o) behalten und zurückgeben!

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

Verwenden Sie Komposition nicht erweitert (ja, ich meine erweitert, wie in einem Verweis auf das Schlüsselwort erweitert in Java und ja, dies ist Vererbung). Die Komposition ist besser, da sie Ihre Implementierung vollständig abschirmt und es Ihnen ermöglicht, die Implementierung zu ändern, ohne die Benutzer Ihrer Klasse zu beeinträchtigen.

Ich empfehle, so etwas zu versuchen (ich tippe direkt in dieses Fenster, damit der Käufer auf Syntaxfehler achtet):

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

Eine bessere Option (basierend auf der Antwort von Asaf) könnte darin bestehen, den Apache Collections CircularFifoBuffer mit einer generischen Klasse zu versehen. Beispielsweise:

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
}

Das einzige, was ich weiß, das nur über begrenzten Speicherplatz verfügt, ist die BlockingQueue-Schnittstelle (die z. B. von der ArrayBlockingQueue-Klasse implementiert wird). Sie entfernen jedoch nicht das erste Element, wenn es gefüllt ist, sondern blockieren die Put-Operation, bis Speicherplatz frei ist (von einem anderen Thread entfernt) ).

Meines Wissens ist Ihre triviale Implementierung der einfachste Weg, um ein solches Verhalten zu erreichen.

Sie können eine MinMaxPriorityQueue von Google Guava aus dem Javadoc verwenden:

Eine Warteschlange mit Min-Max-Priorität kann mit einer maximalen Größe konfiguriert werden. In diesem Fall entfernt die Warteschlange jedes Mal, wenn die Größe der Warteschlange diesen Wert überschreitet, automatisch das größte Element gemäß ihrem Komparator (möglicherweise das gerade hinzugefügte Element). Dies unterscheidet sich von herkömmlichen begrenzten Warteschlangen, die neue Elemente blockieren oder ablehnen, wenn sie voll sind.

Eine LRUMap ist eine weitere Möglichkeit, auch von 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;
    }
}