요소의 고유성을 보장하는 대기열?

요소의 고유성을 보장하는 대기열?

---

java.util.Queue 구현 또는 큐처럼 작동하는 Google 컬렉션의 무언가를 찾고 있지만 큐의 각 요소가 고유한지 확인합니다. (모든 추가 삽입은 효과가 없습니다)

그게 가능합니까, 아니면 손으로해야합니까?

지금은 LinkedList 구현과 함께 Queue를 사용하고 있으며 삽입하기 전에 고유성을 확인합니다. (이 작업을 위해 사이드 맵을 사용하고 대기열 전후에 사이드 맵에서 요소를 추가 / 제거합니다). 나는 그것을 너무 좋아하지 않는다.

모든 입력을 환영합니다. java.util 패키지에 없으면 나쁜 생각일까요?

---

어때요 LinkedHashSet? 반복자는 삽입 순서를 유지하지만이므로 Set요소는 고유합니다.

문서에 따르면

요소가 세트에 다시 삽입 되는 경우 게재 순서는 영향을받지 않습니다 .

이 "대기열"의 헤드에서 요소를 효율적으로 제거하려면 반복자를 통해 이동합니다.

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

---

이것은 내가 아는 한 존재하지 않지만 a 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.
}

---

큐에있는 항목을 나란히 식별하는 키를 포함 하는 HashSet 을 유지하고 싶습니다 . 그런 다음 HashSet을 확인하여 항목을 추가하기 전에 대기열에 있는지 확인하십시오. 큐에서 항목을 제거 할 때 HashSet에서도 키를 제거하면됩니다.

---

물론 고유성을 확인하는 데는 비용이 발생합니다 (공간 또는 시간). 요소의 Comparator로 정렬 된 힙을 유지하는 PriorityQueue와 같은 작업을하는 것이 흥미로울 것 같습니다. 이를 활용하여 사이드 맵을 유지하지 않고도보다 효율적으로 (O (log n)) 존재를 확인할 수 있습니다.

고유성 검사기로 대기열을 래핑하려면 Google Collections ForwardingQueue 를 사용하여 이러한 작업을 수행하는 것이 좋습니다.

---

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

---

이것은 아주 좋은 질문입니다. 기존의 간단한 솔루션은 없습니다. 나는 이것을 시도하기 위해 얼마 전에 작성한 코드를 파헤쳐 돌아와서이 답변을 편집 할 것입니다.

EDIT: I'm back. Truly, if you don't need concurrency, you are better off maintaining a Queue and Set separately. For what I was doing, concurrency was a goal, but the best solution I could come up with given that constraint was problematic; basically, since it used a ConcurrentHashMap, the more you were removing the "head" element from the queue (a basic thing to do with a queue), the more unbalanced the hash table would become over time. I can still share this code with you, but I doubt you really want it.

EDIT: For the case where concurrency is required I gave this answer: Concurrent Set Queue

---

Unfortunately it doesn't exist. Since I needed such a Queue I have developed a Blocking Queue backed by a set, inspired by java.util.concurrent.LinkedBlockingQueue.

You can find it here :

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

Example :

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

You can use it with Maven :

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

---

I am a bit late to answer but I ended up solving a similar problem using an ArrayDeque and overriding the add method that I needed.

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

참고URL : https://stackoverflow.com/questions/2319086/a-queue-that-ensure-uniqueness-of-the-elements