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();