A Queue that ensure uniqueness of the elements?

Question

I'm looking for a implementation of java.util.Queue or something in the Google collection who behave like a Queue, but also ensure that each element of the queue is unique. (all further insertion will have no effect)

It's that possible, or will I have to do it by hand?

For now I'm using a Queue, with a LinkedList implementation, and I check the uniqueness before insertion. ( I use a side Map for doing this, add / remove element from the side map before / after the queu ). I don't like it too much.

Any input is welcome. If it's not in the java.util package, then maybe it's a bad idea?

Answer 1

How about a LinkedHashSet? Its iterator preserves insertion order, but because it's a Set, its elements are unique.

As its documentation says,

Note that insertion order is not affected if an element is re-inserted into the set.

In order to efficiently remove elements from the head of this "queue", go through its iterator:

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

Answer 2

This doesn't exist as far as I know but would be fairly simple to implement using a LinkedList in conjunction with a 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. }