Есть ли очередь фиксированного размера, которая удаляет лишние элементы?

Question

Мне нужна очередь с фиксированным размером. Когда я добавляю элемент и очередь заполнена, он должен автоматически удалить самый старый элемент.

Существует ли существующая реализация для этого в Java?

Answer 1

На самом деле LinkedHashMap делает именно то, что вы хотите. Вам необходимо переопределить метод removeEldestEntry.

Пример очереди с максимум 10 элементами:

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

Если «removeEldestEntry» возвращает true, самая старая запись удаляется с карты.

Answer 2

Да, Два

Из моего собственного дублирующего вопроса с этого правильного ответа , я узнал о двух:

• EvictingQueue в Google Guava
• CircularFifoQueue в Apache Commons

Я продуктивно использовал гуаву EvictingQueue, работал хорошо.

Answer 3

Нет существующей реализации в языке Java и среде исполнения. Все очереди расширяются AbstractQueue , и в его документе четко указано, что добавление элемента в полную очередь всегда заканчивается исключением. Было бы лучше (и довольно просто) превратить очередь в собственный класс, чтобы получить необходимую вам функциональность.

Еще раз, поскольку все очереди являются дочерними для AbstractQueue, просто используйте это как свой внутренний тип данных, и у вас должна быть гибкая реализация, работающая практически мгновенно:

UPDATE:

Как указано ниже, доступны две открытые реализации (этот ответ довольно старый, ребята!), Подробности смотрите в этом ответе .

Answer 4

Я только что реализовал очередь фиксированного размера следующим образом:

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 - 1);
        }
        return r;
    }

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

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

Answer 5

Это то, что я сделал с 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");
.....

Answer 6

Я думаю, что вы описываете круговую очередь. Вот пример , а вот лучше один

Answer 7

Этот класс выполняет работу, используя композицию вместо наследования (другие ответы здесь), которая устраняет возможность определенных побочных эффектов (как описано Джошом Блохом в Essential Java). Обрезка базового 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();
    }
}

Answer 8

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

Answer 9

Простое решение, ниже - «Строка»

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

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

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

Answer 10

Я думаю, что лучший ответ от этот другой вопрос .

Коллекции Apache commons 4 имеют CircularFifoQueue , который вы ищете. Цитируя Javadoc:

CircularFifoQueue - это очередь «первым пришел - первым вышел» с фиксированным размером, который заменяет самый старый элемент, если он заполнен.