Une file d'attente qui assure l'unicité des éléments?

cela n'existe pas autant que je sache mais serait assez simple à mettre en œuvre en utilisant un LinkedList en conjonction avec un 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.
}

je serais tenté de maintenir un" HashSet contenant une clé qui identifie de façon unique les éléments dans la file d'attente côte à côte avec elle. Puis il suffit de vérifier le HashSet pour voir si l'élément est dans la file d'attente avant de l'ajouter. Lorsque vous retirez un élément de la file d'attente, retirez simplement la clé du HashSet ainsi.

vérifier l'unicité a bien sûr un coût (dans l'espace ou dans le temps). Il semble qu'il pourrait être intéressant de travailler à partir de quelque chose comme Unequeue de priorité qui maintiendra un tas trié par comparateur des éléments. Vous pourriez être en mesure de tirer parti de cela pour plus efficacement (o(log n)) vérifier l'existence sans maintenir une carte de côté.

si vous souhaitez envelopper une file d'attente avec un vérificateur d'unicité, je recommande fortement d'utiliser les Collections Google ForwardingQueue pour construire une telle chose.

juste pour compléter la réponse D'Adamski:

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

C'est une très bonne question. Il n'existe pas de solution simple. Je vais déterrer un code que j'ai écrit il y a quelques temps qui a tenté de faire ça, et revenir et éditer cette réponse.

EDIT: je suis de retour. En vérité, si vous n'avez pas besoin de la concurrence, vous êtes mieux de maintenir une file d'attente et mis séparément. Pour ce que je faisais, la concurrence était un objectif, mais la meilleure solution que j'ai pu trouver étant donné que la contrainte était problématique; fondamentalement, puisqu'il a utilisé un Competienthashmap, plus vous retiriez l'élément "tête" de la file (une chose de base à faire avec une file), plus déséquilibré la table de hachage deviendrait au fil du temps. Je peux encore partager ce code avec toi, mais je doute que tu le veuilles vraiment.

modifier: pour le cas où la concurrence est requise j'ai donné cette réponse: Simultaneous Set Queue

Malheureusement, il n'existe pas. Depuis que j'ai eu besoin d'une telle file d'attente, j'ai développé une file D'attente de blocage soutenue par un ensemble, inspiré de java.util.simultané.LinkedBlockingQueue .

vous pouvez le trouver ici:

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

exemple:

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

vous pouvez l'utiliser avec Maven :

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