Kolejka zapewniająca unikalność elementów?

To nie istnieje, o ile wiem, ale byłoby dość proste do zaimplementowania przy użyciu LinkedList w połączeniu z 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.
}

Chciałbym zachować HashSet zawierający klucz, który jednoznacznie identyfikuje elementy w kolejce obok siebie. Następnie po prostu sprawdź HashSet, aby sprawdzić, czy element znajduje się w kolejce przed dodaniem go. Gdy usuniesz element z kolejki, po prostu usuń klucz z HashSet.

Sprawdzanie wyjątkowości oczywiście wiąże się z kosztami (zarówno w przestrzeni, jak i w czasie). Wydaje się, że może być interesująca praca z czymś takim jak PriorityQueue, który utrzyma stertę posortowaną według komparatora elementów. Być może będziesz w stanie wykorzystać to do bardziej wydajnego (o(log n)) sprawdzania istnienia bez utrzymywania mapy bocznej.

Jeśli chcesz zawinąć kolejkę za pomocą sprawdzania unikalności, zdecydowanie polecam użycie kolekcji Google ForwardingQueue do budowania coś takiego.

Żeby uzupełnić odpowiedź Adamskiego:

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

To bardzo dobre pytanie. Nie istnieje żadne proste rozwiązanie. Wykopię jakiś kod, który jakiś czas temu próbował to zrobić, i wrócę i edytuję tę odpowiedź.

EDIT: wróciłem. Naprawdę, jeśli nie potrzebujesz współbieżności, lepiej zachowaj kolejkę i ustaw osobno. Dla tego, co robiłem, współbieżność była celem, ale najlepsze rozwiązanie, jakie mogłem wymyślić, biorąc pod uwagę, że ograniczenie było problematyczne; zasadniczo, ponieważ używało ConcurrentHashMap, im bardziej usuwałeś element "head" z kolejki (podstawowa rzecz związana z kolejką), tym z czasem stała się bardziej niezrównoważona tabela hash. Nadal mogę podzielić się z Tobą tym kodem, ale wątpię, czy naprawdę tego chcesz.

EDIT: W przypadku gdy wymagana jest współbieżność dałem taką odpowiedź: Kolejka Zestawów Współbieżnych

Niestety nie istnieje. Ponieważ potrzebowałem takiej kolejki, opracowałem kolejkę blokującą wspieraną przez Zestaw, zainspirowany java.util./ align = "left" / LinkedBlockingQueue .

Znajdziesz go tutaj:

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

Przykład:

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

Możesz go używać z Maven:

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