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

Question

Я ищу реализацию java.util.Queue или что-то в коллекции Google, которая ведет себя как очередь, но также гарантирует, что каждый элемент очереди уникален.(все дальнейшие вставки не будут иметь никакого эффекта)

Это возможно или мне придется делать это вручную?

На данный момент я использую очередь с реализацией LinkedList и проверяю уникальность перед вставкой.(Для этого я использую боковую карту, добавляю/удаляю элемент с боковой карты до/после очереди).Мне это не слишком нравится.

Любой вклад приветствуется.Если его нет в пакете java.util, то, возможно, это плохая идея?

Answer 1

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

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

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

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

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

Answer 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.
}

Answer 3

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

Answer 4

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

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

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

Answer 6

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

РЕДАКТИРОВАТЬ: Я вернулся.Действительно, если вам не нужен параллелизм, вам лучше поддерживать очередь и набор отдельно.Для того, что я делал, параллелизм был целью, но лучшее решение, которое я мог придумать, учитывая это ограничение, было проблематичным;по сути, поскольку он использовал ConcurrentHashMap, чем больше вы удаляли элемент «head» из очереди (основная вещь, которую нужно сделать с очередью), тем более несбалансированной хэш-таблица со временем становилась.Я все еще могу поделиться с вами этим кодом, но сомневаюсь, что вы действительно этого хотите.

РЕДАКТИРОВАТЬ: В случае, когда требуется параллелизм, я дал такой ответ:Параллельная установка очереди

Answer 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>

Answer 8

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

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