Explain Codes LogoExplain Codes Logo

Is there a fixed sized queue which removes excessive elements?

java
queue
linkedhashmap
collections
Nikita BarsukovbyNikita Barsukov·Nov 11, 2024
TLDR

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