Size-limited queue that holds last N elements in Java

Question

A very simple  amp  quick question on Java libraries  is there a ready-made class that implements a Queue with a fixed maximum size - i e  it always allows addition of elements  but it will silently remove head elements to accomodate space for newly added elements   Of course  it s trivial to implement it manually   import java util LinkedList   public class LimitedQueue lt E gt  extends LinkedList lt E gt        private int limit       public LimitedQueue int limit            this limit   limit              Override     public boolean add E o            super add o           while  size    gt  limit    super remove              return true            As far as I see  there s no standard implementation in Java stdlibs  but may be there s one in Apache Commons or something like that

User · Accepted Answer

Apache commons collections 4 has a CircularFifoQueue<> which is what you are looking for. Quoting the javadoc:

CircularFifoQueue is a first-in first-out queue with a fixed size that replaces its oldest element if full.

    import java.util.Queue;
    import org.apache.commons.collections4.queue.CircularFifoQueue;

    Queue<Integer> fifo = new CircularFifoQueue<Integer>(2);
    fifo.add(1);
    fifo.add(2);
    fifo.add(3);
    System.out.println(fifo);

    // Observe the result: 
    // [2, 3]

If you are using an older version of the Apache commons collections (3.x), you can use the CircularFifoBuffer which is basically the same thing without generics.

Update: updated answer following release of commons collections version 4 that supports generics.

User · Answer

You can use a MinMaxPriorityQueue from Google Guava  from the javadoc      A min-max priority queue can be configured with a maximum size  If so  each time the size of the queue exceeds that value  the queue automatically removes its greatest element according to its comparator  which might be the element that was just added   This is different from conventional bounded queues  which either block or reject new elements when full

User · Answer

public class ArrayLimitedQueue lt E gt  extends ArrayDeque lt E gt         private int limit       public ArrayLimitedQueue int limit            super limit   1           this limit   limit              Override     public boolean add E o            boolean added   super add o           while  added  amp  amp  size    gt  limit                super remove                      return added              Override     public void addLast E e            super addLast e           while  size    gt  limit                super removeLast                          Override     public boolean offerLast E e            boolean added   super offerLast e           while  added  amp  amp  size    gt  limit                super pollLast                      return added

User · Answer

I like  FractalizeR solution  But I would in addition keep and return the value from super add o    public class LimitedQueue lt E gt  extends LinkedList lt E gt         private int limit       public LimitedQueue int limit            this limit   limit              Override     public boolean add E o            boolean added   super add o           while  added  amp  amp  size    gt  limit               super remove                      return added

User · Answer

The only thing I know that has limited space is the BlockingQueue interface  which is e g  implemented by the ArrayBlockingQueue class  - but they do not remove the first element if filled  but instead block the put operation until space is free  removed by other thread    To my knowledge your trivial implementation is the easiest way to get such an behaviour

User · Answer

Use composition not extends  yes I mean extends  as in a reference to the extends keyword in java and yes this is inheritance    Composition is superier because it completely shields your implementation  allowing you to change the implementation without impacting the users of your class   I recommend trying something like this  I m typing directly into this window  so buyer beware of syntax errors    public LimitedSizeQueue implements Queue     private int maxSize    private LinkedList storageArea     public LimitedSizeQueue final int maxSize          this maxSize   maxSize      storageArea   new LinkedList           public boolean offer ElementType element          if  storageArea size    lt  maxSize              storageArea addFirst element             else                 remove last element        storageArea addFirst element                    the rest of this class   A better option  based on the answer by Asaf  might be to wrap the Apache Collections CircularFifoBuffer with a generic class   For example   public LimitedSizeQueue lt ElementType gt  implements Queue lt ElementType gt        private int maxSize      private CircularFifoBuffer storageArea       public LimitedSizeQueue final int maxSize                if  maxSize  gt  0                        this maxSize   maxSize              storateArea   new CircularFifoBuffer maxSize                     else                       throw new IllegalArgumentException  blah blah blah                             implement the Queue interface using the CircularFifoBuffer class

User · Answer

Ok I ll share this option  This is a pretty performant option - it uses an array internally - and reuses entries  It s thread safe - and you can retrieve the contents as a List  static class FixedSizeCircularReference lt T gt        T   entries      FixedSizeCircularReference int size            this entries   new Object size  as T           this size   size           int cur   0     int size      synchronized void add T entry            entries cur      entry         if  cur  gt   size                cur   0                      List lt T gt  asList             int c   cur         int s   size         T   e   entries collect   as T           List lt T gt  list   new ArrayList lt  gt            int oldest    c    s - 1    0   c         for  int i   0  i  lt  e length  i                  def entry   e oldest   i  lt  s   oldest   i   oldest   i - s              if  entry  list add entry                    return list

User · Answer

An LRUMap is another possibility  also from Apache Commons   http   commons apache org collections apidocs org apache commons collections map LRUMap html

User · Answer

Guava now has an EvictingQueue  a non-blocking queue which automatically evicts elements from the head of the queue when attempting to add new elements onto the queue and it is full   import java util Queue  import com google common collect EvictingQueue   Queue lt Integer gt  fifo   EvictingQueue create 2    fifo add 1    fifo add 2    fifo add 3    System out println fifo        Observe the result       2  3

[collections] Size-limited queue that holds last N elements in Java

Examples related to collections

Examples related to queue

Examples related to java