Eine Warteschlange, die die Einzigartigkeit der Elemente gewährleistet?

Question

Ich bin auf der Suche nach einer Implementierung von java.util.Queue oder etwas in der Google-Sammlung, die sich wie eine Warteschlange verhalten, aber auch sicherstellen, dass jedes Element der Warteschlange eindeutig ist. (alle weiteren Insertionen haben keine Wirkung)

Es ist möglich, oder muss ich es manuell machen?

Momentan verwende ich eine Warteschlange mit einer LinkedList-Implementierung, und ich überprüfe die Eindeutigkeit vor dem Einfügen. (Ich benutze dazu eine Side Map, um Elemente aus der Side Map vor/nach der Queue hinzuzufügen/zu entfernen). Ich mag es nicht zu sehr.

Jede Eingabe ist willkommen. Wenn es nicht im Paket java.util ist, ist es vielleicht eine schlechte Idee?

Answer 1

Wie wäre es mit einem LinkedHashSet? Sein Iterator behält die Reihenfolge der Einfügung bei, aber da es sich um eine Set handelt, sind seine Elemente eindeutig.

Wie die Dokumentation sagt,

anzumerken, dass Einsetzfolge nicht betroffen ist, wenn ein Element in die Menge wieder eingesetzt.

Um effizient Elemente aus dem Kopf dieser „queue“ zu entfernen, geht durch seinen Iterator:

Iterator<?> i = queue.iterator(); 
... 
Object next = i.next(); 
i.remove(); 

Answer 2

Ich wäre versucht, eine HashSet mit einem Schlüssel zu halten, der die Elemente in der Warteschlange neben ihm eindeutig identifiziert. Überprüfen Sie dann einfach das HashSet, um festzustellen, ob sich das Element in der Warteschlange befindet, bevor Sie es hinzufügen. Wenn Sie ein Element aus der Warteschlange entfernen, entfernen Sie einfach auch den Schlüssel aus dem HashSet.

Answer 3

Diese existiert nicht, soweit ich weiß, aber wäre ziemlich einfach zu implementieren sein Verwendung eines LinkedList in Verbindung mit einem Set:

/** 
* Thread unsafe implementation of UniqueQueue. 
*/ 
public class UniqueQueue<T> implements Queue<T> { 
    private final Queue<T> queue = new LinkedList<T>(); 
    private final Set<T> set = new HashSet<T>(); 

    public boolean add(T t) { 
    // Only add element to queue if the set does not contain the specified element. 
    if (set.add(t)) { 
     queue.add(t); 
    } 

    return true; // Must always return true as per API def. 
    } 

    public T remove() throws NoSuchElementException { 
    T ret = queue.remove(); 
    set.remove(ret); 
    return ret; 
    } 

    // TODO: Implement other Queue methods. 
} 

Answer 4

Checking Einzigartigkeit natürlich mit Kosten verbunden ist (entweder in Raum oder Zeit). Es scheint, dass es interessant sein könnte, von etwas wie einer PriorityQueue aus zu arbeiten, die einen nach dem Komparator der Elemente sortierten Heap verwaltet. Sie können dies möglicherweise effizienter nutzen (O (log n)), um das Vorhandensein zu prüfen, ohne eine Nebenkarte zu verwalten.

Wenn Sie eine Warteschlange mit einer Eindeutigkeitsprüfung umschließen möchten, empfehle ich Ihnen dringend, die Google Collections ForwardingQueue zu verwenden, um so etwas zu erstellen.

Answer 5

Das ist eine sehr gute Frage. Es gibt keine einfache Lösung. Ich werde etwas Code ausgraben, den ich vor einiger Zeit geschrieben habe und der versucht hat, dies zu tun, und zurückkommen und diese Antwort bearbeiten.

EDIT: Ich bin zurück. Wenn Sie keine Nebenläufigkeit benötigen, sollten Sie Warteschleife und Set getrennt verwalten. Für das, was ich tat, war Nebenläufigkeit ein Ziel, aber die beste Lösung, die ich angesichts dieser Einschränkung finden konnte, war problematisch; Im Prinzip, je mehr Sie das "head" -Element aus der Warteschlange entfernen (eine grundlegende Sache, die mit einer Warteschlange zu tun hat), desto unausgeglichener wird die Hash-Tabelle im Laufe der Zeit. Ich kann diesen Code immer noch mit dir teilen, aber ich bezweifle, dass du das wirklich willst.

EDIT: Für den Fall, dass die Parallelität benötigt habe ich diese Antwort: Concurrent Set Queue

Answer 6

TreeSet. Es ist ein sortierter Satz, und Set impliziert "keine doppelten Elemente".

Answer 7

Gerade Adamskis Antwort zu vervollständigen:

/** 
* A queue that keeps each element only once. 
* If you try to add an element that already exists - nothing will happen. 
* 
* @author Adamski http://stackoverflow.com/a/2319156/827927 
* @NotThreadSafe 
*/ 
public class UniqueQueue<T> implements Queue<T> { 

private final Queue<T> queue = new LinkedList<T>(); 
private final Set<T> set = new HashSet<T>(); 

@Override public boolean add(T t) { 
    // Only add element to queue if the set does not contain the specified element. 
    if (set.add(t)) 
     queue.add(t); 
    return true; // Must always return true as per API def. 
} 

@Override public boolean addAll(Collection<? extends T> arg0) { 
    boolean ret = false; 
    for (T t: arg0) 
     if (set.add(t)) { 
      queue.add(t); 
      ret = true; 
     } 
    return ret; 
} 

@Override public T remove() throws NoSuchElementException { 
    T ret = queue.remove(); 
    set.remove(ret); 
    return ret; 
} 

@Override public boolean remove(Object arg0) { 
    boolean ret = queue.remove(arg0); 
    set.remove(arg0); 
    return ret; 
} 

@Override public boolean removeAll(Collection<?> arg0) { 
    boolean ret = queue.removeAll(arg0); 
    set.removeAll(arg0); 
    return ret; 
} 

@Override public void clear() { 
    set.clear(); 
    queue.clear(); 
} 

@Override public boolean contains(Object arg0) { 
    return set.contains(arg0); 
} 

@Override public boolean containsAll(Collection<?> arg0) { 
    return set.containsAll(arg0); 
} 

@Override public boolean isEmpty() { 
    return set.isEmpty(); 
} 

@Override public Iterator<T> iterator() { 
    return queue.iterator(); 
} 

@Override public boolean retainAll(Collection<?> arg0) { 
    throw new UnsupportedOperationException(); 
} 

@Override public int size() { 
    return queue.size(); 
} 

@Override public Object[] toArray() { 
    return queue.toArray(); 
} 

@Override public <T> T[] toArray(T[] arg0) { 
    return queue.toArray(arg0); 
} 

@Override public T element() { 
    return queue.element(); 
} 

@Override public boolean offer(T e) { 
    return queue.offer(e); 
} 

@Override public T peek() { 
    return queue.peek(); 
} 

@Override public T poll() { 
    return queue.poll(); 
} 
} 

Answer 8

Leider existiert es nicht. Da ich eine solche Queue brauchte, habe ich eine Blocking Queue entwickelt, die von einem Set unterstützt wird, inspiriert von java.util.concurrent.LinkedBlockingQueue.

Sie können es hier finden:

https://github.com/bvanalderweireldt/concurrent-unique-queue

Beispiel:

final BlockingQueue<Integer> queue = new ConcurrentSetBlockingQueue<>(1); 
queue.offer(new Integer(1)); //True 
queue.offer(new Integer(1)); //False 

Sie können es mit Maven verwenden:

<dependency> 
    <groupId>com.hybhub</groupId> 
    <artifactId>concurrent-util</artifactId> 
    <version>0.1</version> 
</dependency>