Есть ли очередь фиксированного размера, которая удаляет лишние элементы?
Мне нужна очередь фиксированного размера. Когда я добавляю элемент и очередь заполняется, он должен автоматически удалять самый старый элемент.
Есть ли существующая реализация для этого в Java?
6 ответов
В языке Java и среде выполнения нет реализации. Все очереди расширяют AbstractQueue , и в его документе четко указано, что добавление элемента в полную очередь всегда заканчивается исключением. Было бы лучше (и довольно просто) обернуть Queue в собственный класс для обеспечения необходимой вам функциональности.
Еще раз, поскольку все очереди являются дочерними по отношению к AbstractQueue, просто используйте это как свой внутренний тип данных, и у вас должна быть гибкая реализация, работающая практически мгновенно: -)
ОБНОВЛЕНИЕ:
Как описано ниже, там доступны две открытые реализации (этот ответ довольно старый, ребята!), подробнее см. этот ответ .
Похоже на обычный список, в котором метод добавления содержит дополнительный фрагмент, который обрезает список, если он становится слишком длинным.
Если это слишком просто, то вам, вероятно, нужно отредактировать вашу проблему описание.
На самом деле LinkedHashMap делает именно то, что вы хотите. Вам нужно переопределить метод removeEldestEntry.
Пример для очереди с максимум 10 элементами:
queue = new LinkedHashMap<Integer, String>()
{
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest)
{
return this.size() > 10;
}
};
Если "removeEldestEntry" возвращает true, то самая старшая запись удаляется с карты.
.См. также этот SO вопрос , или ArrayBlockingQueue (будьте осторожны с блокировкой, в вашем случае она может быть нежелательна)
.Не совсем понятно, какие требования у вас есть, что заставило вас задать этот вопрос. Если вам нужна структура данных фиксированного размера, вы также можете захотеть взглянуть на различные политики кэширования. Однако, так как у вас есть очередь, я думаю, что вы ищете какую-то функциональность маршрутизатора. В этом случае я бы выбрал кольцевой буфер: массив, имеющий первый и последний индекс. Всякий раз, когда добавляется элемент, вы просто увеличиваете индекс последнего элемента, а когда элемент удаляется, увеличиваете индекс первого элемента. В обоих случаях добавление выполняется по модулю размера массива, и обязательно увеличивайте другой индекс, когда это необходимо, то есть когда очередь полная или пустая.
Также, если это приложение маршрутизационного типа, вы можете поэкспериментировать с таким алгоритмом, как Random Early Droppping (RED), который выпадает элементы из очереди случайным образом еще до того, как она будет заполнена. В некоторых случаях было обнаружено, что RED имеет лучшую общую производительность, чем простой метод, позволяющий очереди заполняться до выпадения элементов из очереди
.