Is there a fixed sized queue which removes excessive elements?

java

queue

linkedhashmap

collections

byNikita Barsukov·Nov 11, 2024

A quick way to implement this is to use a LinkedBlockingDeque with a fixed capacity. Establish your capacity and it will auto-remove the oldest element when new ones exceed this limit. Here's a simple demonstration:

// Define capacity - not an invitation to a party, but a limit.
int capacity = 10;

// Construct your queue with the defined capacity
LinkedBlockingDeque<Integer> queue = new LinkedBlockingDeque<>(capacity);

// Our queue's guestlist is open
queue.addLast(element);

// Sorry buddy, this space is limited. We'll have to ask the first one in to leave!
if (queue.size() > capacity) {
    queue.removeFirst(); 
}

Here, the queue always operates within the specified capacity with automatic removal of the oldest element.

Implementing fixed-size queue with LinkedHashMap

A powerful component in Java is LinkedHashMap, which can be tuned to a self-maintaining fixed-size queue. Overriding removeEldestEntry allows you to auto-purge the stale entries.

// Guess the magic number!
int capacity = 10;

// The chosen one - LinkedHashMap!
LinkedHashMap<Integer, Boolean> map = new LinkedHashMap<Integer, Boolean>(capacity, 0.75F, true) {
    protected boolean removeEldestEntry(Map.Entry<Integer, Boolean> eldest) {
        // About to tip the scale? Remove oldest entry. 
        // It's like automatically cleaning your house. Isn't that cool?
        return size() > capacity;
    }
};

Library to the rescue: Guava and Apache Commons

Why reinvent the wheel when libraries exist? Meet Google Guava's EvictingQueue and Apache Commons' CircularFifoQueue - they are your ready-to-use solution for a fixed-size queue with oldest element auto-eviction.

// Guava's EvictingQueue, easy as apple pie
EvictingQueue<Integer> evictingQueue = EvictingQueue.create(capacity);

// Apache's CircularFifoQueue, it indeed goes round and round!
CircularFifoQueue<Integer> fifoQueue = new CircularFifoQueue<>(capacity);

Remember, both these libraries yell "no entry" to null elements.

Low-key solution with ArrayDeque

For non-concurrent tasks, and love for simplicity, ArrayDeque might be your perfect match. Wrap your methods to enforce size maintenance:

ArrayDeque<Integer> deque = new ArrayDeque<>(capacity);

// Add some spiciness by overriding the add() method
public boolean add(Integer e) {
    if (deque.size() == capacity) {
        // Eviction is the sad reality for oldest element. We hold a brief ceremony every time.
        deque.pollFirst(); 
    }
    return deque.offerLast(e); // Welcome aboard!
}

Pointers for choosing your implementation

Factor in thread-safety, performance and null support for choosing your queue.

LinkedBlockingDeque: Safety first! Thread-safe but with extra overhead.
Custom LinkedHashMap: Your rules, your game. Requires subclassing and overriding skills.
Third-party libraries: Ready-made solutions, just a dependency away.
ArrayDeque wrapping: Swift and easy for non-concurrent tasks, might lack some advanced features.

Taking control with AbstractQueue

When it's all about customization, extend AbstractQueue to forge a fixed-size queue.

public class FixedSizeQueue<E> extends AbstractQueue<E> {
    // Tailor your queue as per your own rules.
}

explain-codes / Java / Is there a fixed sized queue which removes excessive elements?

Linked

How to preserve insertion order in HashMap?



How to remove a key from HashMap while iterating over it?



Google Guava vs. Apache Commons



Java LinkedHashMap get first or last entry



Iterating over and removing from a map



What are the differences between a HashMap and a Hashtable in Java?



How do you create a dictionary in Java?



Implementing fixed-size queue with LinkedHashMap Library to the rescue: Guava and Apache Commons Low-key solution with ArrayDeque Pointers for choosing your implementation Taking control with AbstractQueue