Gibt es eine Warteschlange mit fester Größe, die übermäßige Elemente entfernt?

127

Ich brauche eine Warteschlange mit einer festen Größe. Wenn ich ein Element hinzufüge und die Warteschlange voll ist, sollte das älteste Element automatisch entfernt werden.

Gibt es dafür eine Implementierung in Java?

c0d3x
quelle
1
Wie wäre es mit stackoverflow.com/a/6058025/1392882
Miguel

Antworten:

19

In Java Language und Runtime ist keine Implementierung vorhanden. Alle Warteschlangen erweitern AbstractQueue , und in seinem Dokument wird eindeutig angegeben, dass das Hinzufügen eines Elements zu einer vollständigen Warteschlange immer mit einer Ausnahme endet. Es ist am besten (und ganz einfach), eine Warteschlange in eine eigene Klasse zu packen, um die Funktionalität zu erhalten, die Sie benötigen.

Da alle Warteschlangen untergeordnete Elemente von AbstractQueue sind, verwenden Sie dies einfach als internen Datentyp, und Sie sollten eine flexible Implementierung haben, die praktisch in kürzester Zeit ausgeführt werden kann :-)

AKTUALISIEREN:

Wie unten beschrieben, stehen zwei offene Implementierungen zur Verfügung (diese Antwort ist ziemlich alt, Leute!). Weitere Informationen finden Sie in dieser Antwort .

moritz
quelle
4
Verwenden Sie Queue anstelle von AbstractQueue. Möglicherweise gibt es Warteschlangen, die die Schnittstelle implementieren, die abstrakte Klasse jedoch nicht erweitern.
TofuBeer
1
In Python können Sie ein collection.dequemit einem angegebenen verwenden maxlen.
Jonas Gröger
2
UPDATE Es stehen jetzt zwei solcher Klassen zur Verfügung. Sie müssen keine eigenen schreiben. Siehe meine Antwort auf dieser Seite.
Basil Bourque
107

Eigentlich macht die LinkedHashMap genau das, was Sie wollen. Sie müssen die removeEldestEntryMethode überschreiben .

Beispiel für eine Warteschlange mit maximal 10 Elementen:

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

Wenn "removeEldestEntry" true zurückgibt, wird der älteste Eintrag aus der Karte entfernt.

Mavrik
quelle
7
Dies macht eigentlich nicht das, was eine Warteschlange macht. Wie kann ich das Neueste abrufen? Objekt?
Alex
69

Ja, zwei

Aus meiner eigenen doppelten Frage mit dieser richtigen Antwort habe ich zwei gelernt:


Ich habe die Guave produktiv genutzt EvictingQueueund gut gearbeitet.

Um einen EvictingQueueAnruf zu instanziieren, rufen Sie die statische Factory-Methode auf createund geben Sie Ihre maximale Größe an.

EvictingQueue< Person > people = com.google.common.collect.EvictingQueue.create( 100 ) ;  // Set maximum size to 100. 
Basil Bourque
quelle
... und wenn Sie Commons Collection 4.0 nicht verwenden können, scheint CircularFifoBuffer CircularFifoQueue in Version 3.0 ähnlich zu sein.
Sridhar Sarnobat
CircularFifoQueueLink ist tot, verwenden Sie stattdessen commons.apache.org/proper/commons-collections/apidocs/org/…
user7294900
@ user7294900 Danke, Link behoben. Zu Ihrer Information, Stack Overflow lädt Sie ein, solche Änderungen direkt an einer Antwort selbst vorzunehmen. Jeder kann bearbeiten, nicht nur der ursprüngliche Autor. Der Stapelüberlauf soll in dieser Hinsicht eher Wikipedia ähneln.
Basil Bourque
@BasilBourque ja, aber solche Änderungen können auch von mir abgelehnt werden , wenn Links zu ändern , es ist ein Graubereich
user7294900
18

Ich habe gerade eine Warteschlange mit fester Größe folgendermaßen implementiert:

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);
    }
}
Brüllen Sie Skullestad
quelle
1
Es sollte seinremoveRange(0, size() - maxSize)
Ahmed Hegazy
@ AhmedHegazy removeRange (0, Größe () - maxSize - 1) ist korrekt
Ashish Doneriya
Ich stimme Amhed oben zu. Entfernen Sie die - 1. Andernfalls erhalten Sie bei maximaler Kapazität ein Array mit maxSize + 1, da es sich um 0 handelt. Zum Beispiel. Wenn maxSize = 50 ist, lautet die removeRange-Formel im ursprünglichen Beitrag beim Hinzufügen eines neuen Objekts 51 - 50 - 1 = 0 (dh nichts entfernt).
Etep
8

Dies ist, was ich mit Queueeingewickelt gemacht habe LinkedList. Es hat eine feste Größe, die ich hier gebe, ist 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");
.....
Berkay Turancı
quelle
4

Ich denke, was Sie beschreiben, ist eine kreisförmige Warteschlange. Hier ist ein Beispiel , und hier ist ein besser ein


quelle
4

Diese Klasse erledigt die Arbeit mit Komposition anstelle von Vererbung (andere Antworten hier), wodurch die Möglichkeit bestimmter Nebenwirkungen ausgeschlossen wird (wie von Josh Bloch in Essential Java behandelt). Das Trimmen der zugrunde liegenden LinkedList erfolgt für die Methoden add, addAll und angeboten.

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();
    }
}
Dave Moten
quelle
3
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);
    }
}

Verwendung und Testergebnis:

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]
}
Leon
quelle
0

Klingt wie eine normale Liste, in der die Methode add ein zusätzliches Snippet enthält, das die Liste abschneidet, wenn sie zu lang wird.

Wenn das zu einfach ist, müssen Sie wahrscheinlich Ihre Problembeschreibung bearbeiten.

Thorbjørn Ravn Andersen
quelle
Tatsächlich müsste er das erste Element löschen (dh frühestens), das Abschneiden würde das letzte Element entfernen. Immer noch praktisch mit einer LinkedList.
MAK
0

Siehe auch diese SO-Frage oder ArrayBlockingQueue (Vorsicht beim Blockieren, dies kann in Ihrem Fall unerwünscht sein).

Zoran Regvart
quelle
0

Es ist nicht ganz klar, welche Anforderungen Sie dazu veranlasst haben, diese Frage zu stellen. Wenn Sie eine Datenstruktur mit fester Größe benötigen, sollten Sie sich auch verschiedene Caching-Richtlinien ansehen. Da Sie jedoch eine Warteschlange haben, ist meine beste Vermutung, dass Sie nach einer Art Router-Funktionalität suchen. In diesem Fall würde ich einen Ringpuffer verwenden: ein Array mit einem ersten und einem letzten Index. Wenn ein Element hinzugefügt wird, erhöhen Sie einfach den letzten Elementindex. Wenn ein Element entfernt wird, erhöhen Sie den ersten Elementindex. In beiden Fällen erfolgt das Hinzufügen modulo der Arraygröße, und stellen Sie sicher, dass der andere Index bei Bedarf erhöht wird, dh wenn die Warteschlange voll oder leer ist.

Wenn es sich um eine Anwendung vom Typ Router handelt, können Sie auch mit einem Algorithmus wie Random Early Dropping (RED) experimentieren, mit dem Elemente zufällig aus der Warteschlange entfernt werden, noch bevor sie voll sind. In einigen Fällen wurde festgestellt, dass RED eine bessere Gesamtleistung aufweist als die einfache Methode, mit der die Warteschlange vor dem Löschen gefüllt werden kann.

JaakkoK
quelle
0

Eigentlich können Sie Ihr eigenes Impl basierend auf LinkedList schreiben, es ist ganz einfach, überschreiben Sie einfach die Add-Methode und erledigen Sie die Mitarbeiter.

Mike
quelle
0

Ich denke, die am besten passende Antwort stammt von dieser anderen Frage .

Apache Commons Collections 4 verfügt über eine CircularFifoQueue, nach 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.

Diego
quelle
0

Eine einfache Lösung, unten ist eine Warteschlange von "String"

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

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

Beachten Sie, dass dadurch die Reihenfolge der Elemente in der Warteschlange nicht beibehalten wird, sondern der älteste Eintrag ersetzt wird.

M. Usman Khan
quelle
0

Wie in OOPs empfohlen, sollten wir die Komposition der Vererbung vorziehen

Hier meine Lösung, die das berücksichtigt.

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