과도한 요소를 제거하는 고정 크기의 큐가 있습니까?

과도한 요소를 제거하는 고정 크기의 큐가 있습니까?

---

고정 크기의 대기열이 필요합니다. 요소를 추가하고 대기열이 가득 차면 가장 오래된 요소가 자동으로 제거됩니다.

Java로 기존 구현이 있습니까?

---

Java 언어 및 런타임에는 기존 구현이 없습니다. 모든 큐는 AbstractQueue를 확장 하고 문서는 전체 큐에 요소를 추가하면 항상 예외로 끝나는 것으로 명확하게 설명합니다. 필요한 기능을 갖추기 위해 대기열을 자신의 클래스로 포장하는 것이 가장 쉽고 간단합니다.

다시 한 번, 모든 큐는 AbstractQueue의 자식이므로 간단히이를 내부 데이터 유형으로 사용하면 사실상 짧은 시간 내에 유연한 구현을 수행해야합니다. :-)

최신 정보:

아래에 설명 된 것처럼 두 가지 공개 구현이 가능합니다 (이 답변은 상당히 오래되었습니다!) . 자세한 내용 은 이 답변 을 참조하십시오.

---

실제로 LinkedHashMap 은 원하는 것을 정확하게 수행합니다. removeEldestEntry메소드 를 대체해야합니다 .

요소가 최대 10 개인 큐의 예 :

  queue = new LinkedHashMap<Integer, String>()
  {
     @Override
     protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest)
     {
        return this.size() > 10;   
     }
  };

"removeEldestEntry"가 true를 리턴하면 가장 큰 항목이 맵에서 제거됩니다.

---

네, 둘

에서 내 자신의 중복 된 질문 에 이 정답 , 나는이 알게 :

• EvictingQueue에서 구글 구아바
• CircularFifoQueue에서 아파치 코 몬즈

나는 구아바를 생산적으로 사용하고 EvictingQueue잘 작동했습니다.

---

방금 고정 크기 대기열을 다음과 같이 구현했습니다.

public class LimitedSizeQueue<K> extends ArrayList<K> {

    private int maxSize;

    public LimitedSizeQueue(int size){
        this.maxSize = size;
    }

    public boolean add(K k){
        boolean r = super.add(k);
        if (size() > maxSize){
            removeRange(0, size() - maxSize);
        }
        return r;
    }

    public K getYoungest() {
        return get(size() - 1);
    }

    public K getOldest() {
        return get(0);
    }
}

---

이것은 내가 Queue래핑 LinkedList한 것입니다. 여기서 고정 된 크기는 2입니다.

public static Queue<String> pageQueue;

pageQueue = new LinkedList<String>(){
            private static final long serialVersionUID = -6707803882461262867L;

            public boolean add(String object) {
                boolean result;
                if(this.size() < 2)
                    result = super.add(object);
                else
                {
                    super.removeFirst();
                    result = super.add(object);
                }
                return result;
            }
        };


....
TMarket.pageQueue.add("ScreenOne");
....
TMarket.pageQueue.add("ScreenTwo");
.....

---

나는 당신이 묘사하는 것이 원형 큐라고 생각합니다. 여기입니다 예 와 여기에있다 더 나은 하나

---

이 클래스는 상속 대신 컴포지션을 사용하여 작업을 수행합니다 (여기의 답변은 여기에 있습니다). 이는 Java의 Josh Bloch가 다루는 특정 부작용의 가능성을 제거합니다. 기본 LinkedList의 트리밍은 add, addAll 및 offer 메소드에서 발생합니다.

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class LimitedQueue<T> implements Queue<T>, Iterable<T> {

    private final int limit;
    private final LinkedList<T> list = new LinkedList<T>();

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

    private boolean trim() {
        boolean changed = list.size() > limit;
        while (list.size() > limit) {
            list.remove();
        }
        return changed;
    }

    @Override
    public boolean add(T o) {
        boolean changed = list.add(o);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return list.contains(o);
    }

    @Override
    public Iterator<T> iterator() {
        return list.iterator();
    }

    @Override
    public Object[] toArray() {
        return list.toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return list.toArray(a);
    }

    @Override
    public boolean remove(Object o) {
        return list.remove(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return list.containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean changed = list.addAll(c);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return list.removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return list.retainAll(c);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean offer(T e) {
        boolean changed = list.offer(e);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public T remove() {
        return list.remove();
    }

    @Override
    public T poll() {
        return list.poll();
    }

    @Override
    public T element() {
        return list.element();
    }

    @Override
    public T peek() {
        return list.peek();
    }
}

---

public class CircularQueue<E> extends LinkedList<E> {
    private int capacity = 10;

    public CircularQueue(int capacity){
        this.capacity = capacity;
    }

    @Override
    public boolean add(E e) {
        if(size() >= capacity)
            removeFirst();
        return super.add(e);
    }
}

사용 및 테스트 결과 :

public static void main(String[] args) {
    CircularQueue<String> queue = new CircularQueue<>(3);
    queue.add("a");
    queue.add("b");
    queue.add("c");
    System.out.println(queue.toString());   //[a, b, c]

    String first = queue.pollFirst();       //a
    System.out.println(queue.toString());   //[b,c]

    queue.add("d");
    queue.add("e");
    queue.add("f");
    System.out.println(queue.toString());   //[d, e, f]
}

---

add 메소드에 목록이 너무 길면 잘리는 추가 스 니펫이 포함 된 일반 목록처럼 들립니다.

그것이 너무 단순하다면, 아마도 문제 설명을 편집해야 할 것입니다.

---

Also see this SO question, or ArrayBlockingQueue (be careful about blocking, this might be unwanted in your case).

---

It is not quite clear what requirements you have that led you to ask this question. If you need a fixed size data structure, you might also want to look at different caching policies. However, since you have a queue, my best guess is that you're looking for some type of router functionality. In that case, I would go with a ring buffer: an array that has a first and last index. Whenever an element is added, you just increment the last element index, and when an element is removed, increment the first element index. In both cases, addition is performed modulo the array size, and make sure to increment the other index when needed, that is, when the queue is full or empty.

Also, if it is a router-type application, you might also want to experiment with an algorithm such as Random Early Dropping (RED), which drops elements from the queue randomly even before it gets filled up. In some cases, RED has been found to have better overall performance than the simple method of allowing the queue to fill up before dropping.

---

Actually you can write your own impl based on LinkedList, it is quite straight forward, just override the add method and do the staff.

---

I think the best matching answer is from this other question.

Apache commons collections 4 has a CircularFifoQueue which is what you are looking for. Quoting the javadoc:

CircularFifoQueue is a first-in first-out queue with a fixed size that replaces its oldest element if full.

---

A Simple solution, below is a Queue of "String"

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

queue.put(queueKeysCounter++, "My String");
queueKeysCounter %= QUEUE_SIZE;

Note that this will not maintain the Order of the items in the Queue, but it will replace the oldest entry.

참고URL : https://stackoverflow.com/questions/1963806/is-there-a-fixed-sized-queue-which-removes-excessive-elements