Een wachtrij die ervoor zorgt dat de elementen uniek zijn?

Ik ben op zoek naar een implementatie van java.util.Queue of iets in de Google-verzameling die zich als een wachtrij gedraagt, maar er ook voor zorgt dat elk element van de wachtrij uniek is. (alle verdere toevoegingen hebben geen effect)

Kan dat, of moet ik het met de hand doen?

Voorlopig gebruik ik een wachtrij, met een LinkedList-implementatie, en ik controleer de uniciteit voordat ik deze invoeg. (Ik gebruik hiervoor een zijkaart, voeg een element toe aan / verwijder het element uit de zijkaart voor / na de wachtrij). Ik vind het niet zo leuk.

Alle input is welkom. Als het niet in het pakket java.util zit, is het misschien een slecht idee?

Antwoord 1, autoriteit 100%

Wat dacht je van een LinkedHashSet? De iterator behoudt de invoegvolgorde, maar omdat het een Setis, zijn de elementen ervan uniek.

Zoals de documentatie zegt,

Houd er rekening mee dat de invoegvolgorde nietwordt beïnvloed als een element opnieuw wordt ingevoegdin de set.

Om efficiënt elementen uit de kop van deze “wachtrij” te verwijderen, moet u de iterator doorlopen:

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

Antwoord 2, autoriteit 45%

Voor zover ik weet bestaat dit niet, maar het zou vrij eenvoudig te implementeren zijn met een LinkedListin combinatie met een 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.
}

Antwoord 3, autoriteit 9%

Ik zou in de verleiding komen om een ​​HashSetdie een sleutel bevat die de items in de wachtrij er op unieke wijze mee identificeert. Controleer vervolgens de HashSet om te zien of het item in de wachtrij staat voordat u het toevoegt. Wanneer u een item uit de wachtrij verwijdert, verwijdert u ook gewoon de sleutel uit de HashSet.

Antwoord 4, autoriteit 9%

Om Adamski’s antwoord aan te vullen:

/**
 * 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();
}
}

5, Autoriteit 7%

Controle uniciteit heeft natuurlijk een kostprijs (qua ruimte en tijd). Het lijkt erop dat het zou interessant zijn om te werken aan iets als een PriorityQueue die zal handhaven een heap gesorteerd per vergelijker van de elementen. Je zou in staat zijn om invloed die om efficiënter (O (log n)) check bestaan ​​zonder het handhaven van een side map.

Als u wilt een wachtrij wrap met een uniciteit checker, ik zou ten zeerste het gebruik van de Google Verzamelingen ForwardingQueue om zoiets te bouwen.