Java: реализация очереди с фиксированным размером с помощью stdlib

Быстрый ответ

Для создания очереди, которая будет хранить последние N элементов, в Java можно использовать класс ArrayDeque. В случае переполнения этой очереди (N элементов) при добавлении нового элемента, достаточно удалить элемент из начала очереди:

import java.util.ArrayDeque;

public class FixedSizeQueue<E> {
    private final int capacity;
    private final ArrayDeque<E> deque;

    public FixedSizeQueue(int capacity) {
        this.capacity = capacity;
        this.deque = new ArrayDeque<>(capacity);
    }

    public boolean add(E e) {
        if (deque.size() == capacity) {
            deque.pollFirst();
        }
        return deque.add(e);
    }
}

// Пример использования
FixedSizeQueue<Integer> lastNElements = new FixedSizeQueue<>(N);

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

Планирование производительности

Использование ArrayDeque – это быстрое решение, но существуют также альтернативы и факторы, которые могут влиять на производительность и надежность ваших решений.

Готовые решения

Apache Commons Collections: Для удобства реализации очереди фиксированного размера можно использовать CircularFifoQueue, предоставляющую FIFO поведение.

import org.apache.commons.collections4.queue.CircularFifoQueue;

CircularFifoQueue<Integer> queue = new CircularFifoQueue<>(N);

Если вы работаете со старыми версиями Apache, вам может пригодиться CircularFifoBuffer.

Google Guava: EvictingQueue – это неблокирующая очередь, которая автоматически удаляет старые элементы.

import com.google.common.collect.EvictingQueue;

EvictingQueue<Integer> queue = EvictingQueue.create(N);

Подробнее об этом расскажет наш спикер на видео

Тщательно выбирайте реализацию

LinkedList: Кажется удобной, но увеличивает сложность и может снизить производительность.

Blocking Queues: Очереди, как, например, ArrayBlockingQueue, ожидают, пока очередь наполнится, тогда как нам нужно автоматическое удаление старых элементов.

Пользовательская очередь: основные принципы

Создание собственной реализации требует следования некоторым принципам:

• Безопасность максимального размера: Размер должен быть положительным и неизменным.
• Временная сложность: Операции должны быть быстрыми, без необходимости перепроверки всей коллекции.
• Соответствие интерфейсу: Реализация интерфейса Queue обеспечивает лучшую совместимость.

Визуализация

Можно представить очередь ограниченного размера как очередь на вход в концертный зал:

**Вход в зал**: 🚪
Вместимость: **5 зрителей** одновременно

Изменение состава очереди (🧍 – это посетитель):

До: [🧍, 🧍, 🧍, 🧍, 🧍]   После: [🧍, 🧍, 🧍, 🧍, 🧍🆕]
// Входит новый зритель: 🆕      // Уходит первый в очереди: 🚶‍♂️

Это похоже на отслеживание последних 5 зрителей, вошедших в помещение, что соответствует отслеживанию последних N элементов в нашей программной очереди.

Улучшение вашей реализации

Сосредоточившись на ключевых аспектах, вы сможете усовершенствовать вашу очередь ограниченного размера в Java:

Использование обобщений

Построение очередей с использованием обобщений обеспечивает типобезопасность и универсальность кода.

Продумайте стратегию

Рассмотрите композицию вместо наследования классов для изоляции логики и обеспечения гибкости.

Не забывайте о тестировании

Важно тестировать крайние случаи, такие как переполнение или многопоточность, и разрабатывать соответствующие модульные тесты.

Бережное отношение к сборке мусора

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

Полезные материалы

1. ArrayDeque (Java Platform SE 8 )
2. EvictingQueue (Guava: Google Core Libraries for Java 19.0 API)
3. Круговая структура данных очереди
4. BlockingQueue (Java Platform SE 8 )
5. CircularFifoQueue (Apache Commons Collections 4.4 API)
6. Подробное изучение Java LinkedList с примерами | CalliCoder
7. PriorityQueue (Java Platform SE 8 )