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

128

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

Есть ли для этого реализация на Java?

c0d3x
источник
1
как насчет stackoverflow.com/a/6058025/1392882
Мигель

Ответы:

19

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

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

ОБНОВИТЬ:

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

Moritz
источник
4
Используйте Queue вместо AbstractQueue ... могут быть очереди, которые реализуют интерфейс, но не расширяют абстрактный класс.
TofuBeer,
1
В Python вы можете использовать a collection.dequeс указанным maxlen.
Йонас Грёгер
2
ОБНОВЛЕНИЕ Теперь доступно два таких класса. Нет необходимости писать свои собственные. Смотрите мой ответ на этой странице.
Basil Bourque
108

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

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

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

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

Маврик
источник
7
это фактически не делает того, что делает очередь, как я могу получить самое новое. объект?
Alex
69

Да, два

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


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

Чтобы создать экземпляр EvictingQueueвызова статического фабричного метода createи указать свой максимальный размер.

EvictingQueue< Person > people = com.google.common.collect.EvictingQueue.create( 100 ) ;  // Set maximum size to 100. 
Василий Бурк
источник
... и если вы не можете использовать Commons Collection 4.0, то CircularFifoBuffer кажется похожим на CircularFifoQueue в версии 3.0.
Шридхар Сарнобат
CircularFifoQueueссылка мертва, используйте вместо нее commons.apache.org/proper/commons-collections/apidocs/org/…
user7294900
@ user7294900 Спасибо, ссылка исправлена. К вашему сведению, Stack Overflow предлагает вам внести такие изменения непосредственно в ответ самостоятельно. Редактировать может кто угодно, а не только оригинальный автор. В этом отношении Stack Overflow больше похож на Википедию.
Basil Bourque
@BasilBourque да, но такие правки могут быть отклонены даже мной, при смене ссылок это серая зона
user7294900
18

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

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);
    }
}
Рев Скулестад
источник
1
Должно бытьremoveRange(0, size() - maxSize)
Ахмед Хегази
@AhmedHegazy removeRange (0, size () - maxSize - 1) верен
Ashish Doneriya
Я согласен с Амхедом выше. Удалите - 1. В противном случае при максимальной емкости вы получите массив с maxSize + 1, поскольку мы говорим о 0. Например. Если maxSize = 50, то при добавлении нового объекта формула removeRange в исходном сообщении будет 51 - 50 - 1 = 0 (т.е. ничего не удалено).
Etep 06
8

Это то, что я сделал с 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");
.....
Беркай Туранджы
источник
4

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

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

Если это слишком просто, вам, вероятно, нужно отредактировать описание проблемы.

Торбьёрн Равн Андерсен
источник
Фактически, ему нужно будет удалить первый элемент (т.е. самый ранний), усечение удалит последний элемент. Все еще практично с LinkedList.
MAK
0

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

Кроме того, если это приложение типа маршрутизатора, вы также можете поэкспериментировать с таким алгоритмом, как Random Early Dropping (RED), который случайным образом удаляет элементы из очереди еще до того, как она будет заполнена. В некоторых случаях было обнаружено, что RED имеет лучшую общую производительность, чем простой метод, позволяющий очереди заполняться перед отбрасыванием.

JaakkoK
источник
0

На самом деле вы можете написать свой собственный impl на основе LinkedList, это довольно просто, просто переопределите метод добавления и выполните команду.

Майк
источник
0

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

В коллекциях Apache Commons 4 есть CircularFifoQueue, которую вы ищете. Цитата из javadoc:

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

Диего
источник
0

Простое решение, ниже - очередь "String"

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

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

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

М. Усман Хан
источник
0

Как сказано в ООП, мы должны предпочесть композицию наследованию.

Вот мое решение с учетом этого.

package com.choiceview;

import java.util.ArrayDeque;

class Ideone {
    public static void main(String[] args) {
        LimitedArrayDeque<Integer> q = new LimitedArrayDeque<>(3);
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q);

        q.add(4);
        // First entry ie 1 got pushed out
        System.out.println(q);
    }
}

class LimitedArrayDeque<T> {

    private int maxSize;
    private ArrayDeque<T> queue;

    private LimitedArrayDeque() {

    }

    public LimitedArrayDeque(int maxSize) {
        this.maxSize = maxSize;
        queue = new ArrayDeque<T>(maxSize);
    }

    public void add(T t) {
        if (queue.size() == maxSize) {
            queue.removeFirst();
        }
        queue.add(t);
    }

    public boolean remove(T t) {
        return queue.remove(t);
    }

    public boolean contains(T t) {
        return queue.contains(t);
    }

    @Override
    public String toString() {
        return queue.toString();
    }
}
Абхишек
источник