166

I need a queue with a fixed size. When I add an element and the queue is full, it should automatically remove the oldest element.

Is there an existing implementation for this in Java?

1

15 Answers 15

127

Actually the LinkedHashMap does exactly what you want. You need to override the removeEldestEntry method.

Example for a queue with max 10 elements:

  queue = new LinkedHashMap<Integer, String>()
  {
     @Override
     protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest)
     {
        return this.size() > 10;   
     }
  };

If the "removeEldestEntry" returns true, the eldest entry is removed from the map.

2
  • 10
    this actually doesn't do what a queue does, how can I retrieve the newest. object? Jan 15, 2018 at 15:19
  • 2
    Get the last item in values().
    – Mavrik
    Oct 13, 2020 at 11:35
92

Yes, Two

From my own duplicate question with this correct answer, I learned of two:

Neither is thread-safe. Neither accepts null elements.


I made productive use of the Guava EvictingQueue, worked well.

To instantiate an EvictingQueue call the static factory method create and specify your maximum size.

EvictingQueue< Person > people = com.google.common.collect.EvictingQueue.create( 100 ) ;  // Set maximum size to 100. 
6
  • ...and if you can't use Commons Collection 4.0 then CircularFifoBuffer seems to be similar to CircularFifoQueue in v 3.0. Mar 9, 2017 at 4:41
  • CircularFifoQueue link is dead, use instead commons.apache.org/proper/commons-collections/apidocs/org/…
    – Ori Marko
    Oct 22, 2018 at 12:47
  • @user7294900 Thanks, link fixed. FYI, Stack Overflow invites you to make such edits directly to an Answer yourself. Anyone can edit, not just the original author. Stack Overflow is intended to more like Wikipedia in that regard. Oct 22, 2018 at 16:38
  • @BasilBourque yes, but such edits can be rejected even by me when changing links it's a gray area
    – Ori Marko
    Oct 22, 2018 at 16:41
  • 1
    Note that both of the implementations are NOT thread-safe, if you plan on using them concurrently.
    – Jamby
    Jun 13, 2023 at 11:58
23

I just implemented a fixed size queue this way:

public class LimitedSizeQueue<K> extends ArrayList<K> {

    private int maxSize;

    public LimitedSizeQueue(int size){
        this.maxSize = size;
    }

    public boolean add(K k){
        boolean r = super.add(k);
        if (size() > maxSize){
            removeRange(0, size() - maxSize);
        }
        return r;
    }

    public K getYoungest() {
        return get(size() - 1);
    }

    public K getOldest() {
        return get(0);
    }
}
3
  • 1
    It should be removeRange(0, size() - maxSize) Feb 21, 2018 at 12:08
  • @AhmedHegazy removeRange(0, size() - maxSize - 1) is correct Mar 27, 2019 at 7:45
  • I agree with Amhed above. Remove the - 1. Otherwise at max capacity you will end up with an array that is maxSize + 1 since we are talking about 0 based. For instance. If maxSize = 50 then when adding a new object the removeRange formula in the original post will be 51 - 50 - 1 = 0 (ie. nothing removed).
    – Etep
    Jul 6, 2019 at 1:36
21

There is no existing implementation in the Java Language and Runtime. All Queues extend AbstractQueue, and its doc clearly states that adding an element to a full queue always ends with an exception. It would be best ( and quite simple ) to wrap a Queue into a class of your own for having the functionality you need.

Once again, because all queues are children of AbstractQueue, simply use that as your internal data type and you should have a flexible implementation running in virtually no time :-)

UPDATE:

As outlined below, there are two open implementations available (this answer is quite old, folks!), see this answer for details.

3
  • 4
    Use Queue instead of AbstractQueue... there may be queues that implement the interface but do not extend the abstract class.
    – TofuBeer
    Dec 26, 2009 at 17:40
  • 1
    In Python you can use a collection.deque with a specified maxlen. Feb 10, 2014 at 15:50
  • 3
    UPDATE There are now two such classes available. No need to write your own. See my answer on this page. Feb 11, 2014 at 10:22
10
public class CircularQueue<E> extends LinkedList<E> {
    private final int capacity;

    public CircularQueue(int capacity){
        this.capacity = capacity;
    }

    @Override
    public boolean add(E e) {
        if(size() >= capacity)
            removeFirst();
        return super.add(e);
    }
}

Usage and test result:

public static void main(String[] args) {
    CircularQueue<String> queue = new CircularQueue<>(3);
    queue.add("a");
    queue.add("b");
    queue.add("c");
    System.out.println(queue.toString());   //[a, b, c]

    String first = queue.pollFirst();       //a
    System.out.println(queue.toString());   //[b,c]

    queue.add("d");
    queue.add("e");
    queue.add("f");
    System.out.println(queue.toString());   //[d, e, f]
}
8

This is what I did with Queue wrapped with LinkedList, It is fixed sized which I give in here is 2;

public static Queue<String> pageQueue;

pageQueue = new LinkedList<String>(){
            private static final long serialVersionUID = -6707803882461262867L;

            public boolean add(String object) {
                boolean result;
                if(this.size() < 2)
                    result = super.add(object);
                else
                {
                    super.removeFirst();
                    result = super.add(object);
                }
                return result;
            }
        };


....
TMarket.pageQueue.add("ScreenOne");
....
TMarket.pageQueue.add("ScreenTwo");
.....
0
4

I think what you're describing is a circular queue. Here is an example and here is a better one

1
  • no. He is describing a simple plain Queue according it's definition as a FIFO structure. Not having that in Collections is unexpected.
    – Rafael
    May 18, 2023 at 15:03
4

This class does the job using composition instead of inheritance (other answers here) which removes the possibility of certain side-effects (as covered by Josh Bloch in Essential Java). Trimming of the underlying LinkedList occurs on the methods add,addAll and offer.

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class LimitedQueue<T> implements Queue<T>, Iterable<T> {

    private final int limit;
    private final LinkedList<T> list = new LinkedList<T>();

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    private boolean trim() {
        boolean changed = list.size() > limit;
        while (list.size() > limit) {
            list.remove();
        }
        return changed;
    }

    @Override
    public boolean add(T o) {
        boolean changed = list.add(o);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return list.contains(o);
    }

    @Override
    public Iterator<T> iterator() {
        return list.iterator();
    }

    @Override
    public Object[] toArray() {
        return list.toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return list.toArray(a);
    }

    @Override
    public boolean remove(Object o) {
        return list.remove(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return list.containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean changed = list.addAll(c);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return list.removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return list.retainAll(c);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean offer(T e) {
        boolean changed = list.offer(e);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public T remove() {
        return list.remove();
    }

    @Override
    public T poll() {
        return list.poll();
    }

    @Override
    public T element() {
        return list.element();
    }

    @Override
    public T peek() {
        return list.peek();
    }
}
0

Also see this SO question, or ArrayBlockingQueue (be careful about blocking, this might be unwanted in your case).

0

It is not quite clear what requirements you have that led you to ask this question. If you need a fixed size data structure, you might also want to look at different caching policies. However, since you have a queue, my best guess is that you're looking for some type of router functionality. In that case, I would go with a ring buffer: an array that has a first and last index. Whenever an element is added, you just increment the last element index, and when an element is removed, increment the first element index. In both cases, addition is performed modulo the array size, and make sure to increment the other index when needed, that is, when the queue is full or empty.

Also, if it is a router-type application, you might also want to experiment with an algorithm such as Random Early Dropping (RED), which drops elements from the queue randomly even before it gets filled up. In some cases, RED has been found to have better overall performance than the simple method of allowing the queue to fill up before dropping.

0

Actually you can write your own impl based on LinkedList, it is quite straight forward, just override the add method and do the staff.

0

I think the best matching answer is from this other question.

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.

0

A Simple solution, below is a Queue of "String"

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

queue.put(queueKeysCounter++, "My String");
queueKeysCounter %= QUEUE_SIZE;

Note that this will not maintain the Order of the items in the Queue, but it will replace the oldest entry.

0

As it's advised in OOPs that we should prefer Composition over Inheritance

Here my solution keeping that in mind.

package com.choiceview;

import java.util.ArrayDeque;

class Ideone {
    public static void main(String[] args) {
        LimitedArrayDeque<Integer> q = new LimitedArrayDeque<>(3);
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q);

        q.add(4);
        // First entry ie 1 got pushed out
        System.out.println(q);
    }
}

class LimitedArrayDeque<T> {

    private int maxSize;
    private ArrayDeque<T> queue;

    private LimitedArrayDeque() {

    }

    public LimitedArrayDeque(int maxSize) {
        this.maxSize = maxSize;
        queue = new ArrayDeque<T>(maxSize);
    }

    public void add(T t) {
        if (queue.size() == maxSize) {
            queue.removeFirst();
        }
        queue.add(t);
    }

    public boolean remove(T t) {
        return queue.remove(t);
    }

    public boolean contains(T t) {
        return queue.contains(t);
    }

    @Override
    public String toString() {
        return queue.toString();
    }
}
1
0

Ok, I'll throw out my version too. :-) This is build to be very performant - for when that matters. It's not based on LinkedList - and is thread safe (should be at least). FIFO

static class FixedSizeCircularReference<T> {
    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 >= size) {
            cur = 0
        }
    }

    List<T> asList() {
        int c = cur
        int s = size
        T[] e = entries.collect() as T[]
        List<T> list = new ArrayList<>()
        int oldest = (c == s - 1) ? 0 : c
        for (int i = 0; i < e.length; i++) {
            def entry = e[oldest + i < s ? oldest + i : oldest + i - s]
            if (entry) list.add(entry)
        }
        return list
    }
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.