[java] Java에서 마지막 N 개 요소를 보유하는 크기 제한 큐

JAVA / 글쓴이

Java 라이브러리에 대한 매우 간단하고 빠른 질문 : Queue고정 된 최대 크기로 를 구현하는 기성품 클래스가 있습니까 ? 즉, 항상 요소를 추가 할 수 있지만 새로 추가 된 요소의 공간을 수용하기 위해 헤드 요소를 자동으로 제거합니다.

물론 수동으로 구현하는 것은 쉽지 않습니다.

import java.util.LinkedList;

public class LimitedQueue<E> extends LinkedList<E> {
    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > limit) { super.remove(); }
        return true;
    }
}

내가 아는 한, Java stdlib에는 표준 구현이 없지만 Apache Commons 또는 이와 유사한 것이 있습니까?

답변

Apache Commons Collections 4에는 찾고 있는 CircularFifoQueue <> 가 있습니다. javadoc 인용 :

CircularFifoQueue는 고정 된 크기의 선입 선출 대기열로, 가장 오래된 요소가 가득 찬 경우이를 대체합니다.

    import java.util.Queue;
    import org.apache.commons.collections4.queue.CircularFifoQueue;

    Queue<Integer> fifo = new CircularFifoQueue<Integer>(2);
    fifo.add(1);
    fifo.add(2);
    fifo.add(3);
    System.out.println(fifo);

    // Observe the result: 
    // [2, 3]

이전 버전의 Apache Commons Collections (3.x)를 사용 하는 경우 기본적으로 제네릭없이 동일한 CircularFifoBuffer 를 사용할 수 있습니다 .

업데이트 : 일반을 지원하는 Commons Collections 버전 4 릴리스 이후의 답변이 업데이트되었습니다.

답변

구아바 이제 갖는다 EvictingQueue , 큐에 새로운 요소를 추가 할 때 자동 큐의 선두의 요소를 축출 비 블로킹 큐 그리고 가득.

import java.util.Queue;
import com.google.common.collect.EvictingQueue;

Queue<Integer> fifo = EvictingQueue.create(2);
fifo.add(1);
fifo.add(2);
fifo.add(3);
System.out.println(fifo);

// Observe the result: 
// [2, 3]

답변

나는 @FractalizeR 솔루션을 좋아합니다. 그러나 또한 super.add (o)에서 값을 유지하고 반환합니다!

public class LimitedQueue<E> extends LinkedList<E> {

    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
           super.remove();
        }
        return added;
    }
}

답변

composition not extends를 사용하십시오 (예, java의 extends 키워드에 대한 참조에서와 같이 extends를 의미하며 이것이 상속입니다). 컴포지션은 구현을 완전히 차단하여 클래스 사용자에게 영향을주지 않고 구현을 변경할 수 있기 때문에 더욱 우수합니다.

나는 이런 식으로 시도하는 것이 좋습니다 (이 창에 직접 입력하고 있으므로 구매자는 구문 오류에주의하십시오) :

public LimitedSizeQueue implements Queue
{
  private int maxSize;
  private LinkedList storageArea;

  public LimitedSizeQueue(final int maxSize)
  {
    this.maxSize = maxSize;
    storageArea = new LinkedList();
  }

  public boolean offer(ElementType element)
  {
    if (storageArea.size() < maxSize)
    {
      storageArea.addFirst(element);
    }
    else
    {
      ... remove last element;
      storageArea.addFirst(element);
    }
  }

  ... the rest of this class

Asaf의 답변을 기반으로하는 더 좋은 옵션은 Apache Collections CircularFifoBuffer 를 일반 클래스 로 래핑하는 것 입니다. 예를 들면 다음과 같습니다.

public LimitedSizeQueue<ElementType> implements Queue<ElementType>
{
    private int maxSize;
    private CircularFifoBuffer storageArea;

    public LimitedSizeQueue(final int maxSize)
    {
        if (maxSize > 0)
        {
            this.maxSize = maxSize;
            storateArea = new CircularFifoBuffer(maxSize);
        }
        else
        {
            throw new IllegalArgumentException("blah blah blah");
        }
    }

    ... implement the Queue interface using the CircularFifoBuffer class
}

답변

제한된 공간을 가지고 있다는 것을 알고있는 유일한 것은 BlockingQueue 인터페이스 (예 : ArrayBlockingQueue 클래스에 의해 구현 됨)입니다. 그러나 채워지면 첫 번째 요소를 제거하지 않고 대신 공간이 비워 질 때까지 put 작업을 차단합니다 (다른 스레드에 의해 제거됨) ).

내 지식으로는 사소한 구현이 그러한 행동을 얻는 가장 쉬운 방법입니다.

답변

javadoc 에서 Google Guava 의 MinMaxPriorityQueue 를 사용할 수 있습니다 .

최소-최대 우선 순위 큐는 최대 크기로 구성 할 수 있습니다. 그렇다면 대기열의 크기가 해당 값을 초과 할 때마다 대기열은 비교기 (방금 추가 된 요소 일 수 있음)에 따라 가장 큰 요소를 자동으로 제거합니다. 이는 새 요소가 가득 차면 차단하거나 거부하는 기존의 제한 대기열과 다릅니다.

답변

LRUMap은 Apache Commons의 또 다른 가능성입니다.

http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/LRUMap.html