Is there a fixed sized queue which removes excessive elements?

Question

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?

Solution 1

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.

Solution 2

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.

Solution 3

Yes, Two

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

• EvictingQueue in Google Guava
• CircularFifoQueue in Apache Commons

---

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. 

Solution 4

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);
    }
}

Solution 5

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");
.....

View more solutions

Comments

[Miguel]

how about stackoverflow.com/a/6058025/1392882

[TofuBeer]

Use Queue instead of AbstractQueue... there may be queues that implement the interface but do not extend the abstract class.

[MAK]

Actually, he would need to delete the first element (i.e. earliest), truncating would remove the last element. Still practical with a LinkedList.

[Jonas Gröger]

In Python you can use a collection.deque with a specified maxlen.

[Basil Bourque]

UPDATE There are now two such classes available. No need to write your own. See my answer on this page.

[Sridhar Sarnobat]

...and if you can't use Commons Collection 4.0 then CircularFifoBuffer seems to be similar to CircularFifoQueue in v 3.0.

[Alexander Oh]

this actually doesn't do what a queue does, how can I retrieve the newest. object?

[Ahmed Hegazy]

It should be removeRange(0, size() - maxSize)

[user7294900]

CircularFifoQueue link is dead, use instead commons.apache.org/proper/commons-collections/apidocs/org/…

[Basil Bourque]

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

[user7294900]

@BasilBourque yes, but such edits can be rejected even by me when changing links it's a gray area

[Ashish Doneriya]

@AhmedHegazy removeRange(0, size() - maxSize - 1) is correct

[Etep]

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

[Mavrik]

Get the last item in values().