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

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

---

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

---

Use composition not extends (yes I mean extends, as in a reference to the extends keyword in java and yes this is inheritance). Composition is superier because it completely shields your implementation, allowing you to change the implementation without impacting the users of your class.

I recommend trying something like this (I'm typing directly into this window, so buyer beware of syntax errors):

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

A better option (based on the answer by Asaf) might be to wrap the Apache Collections CircularFifoBuffer with a generic class. For example:

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
}

---

The only thing I know that has limited space is the BlockingQueue interface (which is e.g. implemented by the ArrayBlockingQueue class) - but they do not remove the first element if filled, but instead block the put operation until space is free (removed by other thread).

To my knowledge your trivial implementation is the easiest way to get such an behaviour.

---

An LRUMap is another possibility, also from Apache Commons.

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

---

You can use a MinMaxPriorityQueue from Google Guava, from the javadoc:

A min-max priority queue can be configured with a maximum size. If so, each time the size of the queue exceeds that value, the queue automatically removes its greatest element according to its comparator (which might be the element that was just added). This is different from conventional bounded queues, which either block or reject new elements when full.

---

    public class ArrayLimitedQueue<E> extends ArrayDeque<E> {

    private int limit;

    public ArrayLimitedQueue(int limit) {
        super(limit + 1);
        this.limit = limit;
    }

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

    @Override
    public void addLast(E e) {
        super.addLast(e);
        while (size() > limit) {
            super.removeLast();
        }
    }

    @Override
    public boolean offerLast(E e) {
        boolean added = super.offerLast(e);
        while (added && size() > limit) {
            super.pollLast();
        }
        return added;
    }
}

참고URL : https://stackoverflow.com/questions/5498865/size-limited-queue-that-holds-last-n-elements-in-java