Очередь, обеспечивающая уникальность элементов?

Ответ 1

Как насчет LinkedHashSet? Его итератор сохраняет порядок вставки, но поскольку он a Set, его элементы уникальны.

Как говорится в документации,

Обратите внимание, что порядок вставки не изменяется, если элемент повторно вставлен в набор.

Чтобы эффективно удалить элементы из заголовка этой "очереди", пройдите через его итератор:

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

Ответ 2

Это не существует, насколько я знаю, но было бы довольно просто реализовать с помощью LinkedList в сочетании с 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.
}

Ответ 3

У меня возникнет соблазн поддерживать HashSet, содержащий ключ, который однозначно идентифицирует элементы в очереди бок о бок с этим. Затем просто проверьте HashSet, чтобы увидеть, находится ли элемент в очереди, прежде чем добавлять его. Когда вы удаляете элемент из очереди, просто удалите его из HashSet.

Ответ 4

Проверка уникальности курса имеет стоимость (либо в пространстве, либо во времени). Похоже, что было бы интересно работать с чем-то вроде PriorityQueue, который будет поддерживать кучу, отсортированную по компаратору элементов. Возможно, вы сможете более эффективно использовать это (O (log n)) для проверки существования без сохранения боковой карты.

Если вы хотите обернуть очередь с помощью проверки уникальности, я настоятельно рекомендую использовать коллекцию Google ForwardingQueue для создания таких вещь.

Ответ 5

Просто чтобы ответить Адамски:

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

Ответ 6

Это очень хороший вопрос. Нет прямого решения. Я выкопаю код, который я написал некоторое время назад, который пытался это сделать, и вернусь и отредактируйте этот ответ.

EDIT: Я вернулся. Поистине, если вам не нужен concurrency, вам лучше поддерживать очередь и устанавливать отдельно. Для того, что я делал, concurrency была целью, но лучшим решением я мог бы придумать, учитывая, что ограничение было проблематичным; в основном, поскольку он использовал ConcurrentHashMap, тем больше вы удаляли элемент "head" из очереди (основная задача, связанная с очередью), тем более неуравновешенная хэш-таблица со временем становилась. Я все еще могу поделиться этим кодом с вами, но я сомневаюсь, что вы действительно этого хотите.

EDIT: Для случая, когда требуется concurrency, я дал следующий ответ: Параллельная установка очереди

Ответ 7

К сожалению, этого не существует. Поскольку мне нужна такая очередь, я разработал блокирующую очередь, поддерживаемую набором, созданным с помощью java.util.concurrent.LinkedBlockingQueue.

Вы можете найти его здесь:

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

Пример:

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

Вы можете использовать его с Maven:

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

Ответ 8

Я немного опоздал с ответом, но в итоге решил аналогичную проблему с помощью ArrayDeque и переопределил нужный мне метод add.

    Deque<Long> myQueue = new ArrayDeque<Long>() {
        @Override
        public boolean add(Long e) { return !this.contains(e) && super.add(e);}
    };

Ответ 9

TreeSet. Это отсортированный набор, а Set означает "нет повторяющихся элементов".