Which Queue implementation to use in Java?

Question

I need to use a FIFO structure in my application. It needs to have at most 5 elements. I'd like to have something easy to use (I don't care for concurrency) that implements the Collection interface.

I've tried the LinkedList, that seems to come from Queue, but it doesn't seem to allow me to set it's maximum capacity. It feels as if I just want at max 5 elements but try to add 20, it will just keep increasing in size to fit it. I'd like something that'd work the following way:

XQueue<Integer> queue = new XQueue<Integer>(5); //where 5 is the maximum number of elements I want in my queue.
for (int i = 0; i < 10; ++i) {
    queue.offer(i);
}

for (int i = 0; i < 5; ++i) {
    System.out.println(queue.poll());
}

That'd print:

5
6
7
8
9

Thanks

Answer 1

Create your own subclass of the one you want, and override the add method so that it

• checks if the new object will fit, and fails if not
• calls super.add()

(and the constructors).

If you want it to block when inserting if full, it is a different matter.

Answer 2

Looks like what you want is a limited size FIFO structure, that evicts oldest items when new ones are added. I recommend a solution based on a cyclic array implementation, where you should track the index of the queue tail and queue head, and increase them (in cyclic manner) as needed.

EDIT: Here is my implementation (note that it IS a Collection). It works fine with your test scenario.

public class XQueue <T> extends AbstractQueue<T>{
    private T[] arr;
    private int headPos;
    private int tailPos;
    private int size;

    @SuppressWarnings("unchecked")
    public XQueue(int n){
        arr = (T[]) new Object[n];
    }

    private int nextPos(int pos){
        return (pos + 1) % arr.length;
    }

    @Override
    public T peek() {
        if (size == 0)
            return null;
        return arr[headPos];
    }

    public T poll(){
        if (size == 0)
            return null;
        size--;
        T res = arr[headPos];
        headPos = nextPos(headPos);     
        return res;
    }

    @Override
    public boolean offer(T e) {
        if (size < arr.length)
            size++;
        else
            if (headPos == tailPos)
                headPos = nextPos(headPos);
        arr[tailPos] = e;
        tailPos = nextPos(tailPos);
        return true;
    }

    @Override
    public Iterator<T> iterator() {
        return null; //TODO: Implement
    }

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

Answer 3

I haven't seen any limitation like that in the API. You can use ArrayList by changing the behavior of the add method with anonymous class feature:

new ArrayList<Object>(){
    public boolean add(Object o){ /*...*/ }
}

Answer 4

Perhaps an ArrayBlockingQueue might do the trick. Look here. Try something like this:

BlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(5);

for (int i = 0; i < 10; i++) {
  while (!queue.offer(i)) {
    queue.poll();        
  }
}

for (int i = 0; i < 5; i++) {   
  System.out.println(queue.poll());
}

Answer 5

You have three choices

1) Subclass an Abstract Collection

2) Limit the size to five and do the logic around the code where you are doing the insert.

3) Use LinkedListHashMap The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map. (You would then use an Iterator to get the values - which will be returned in order of insertion)

Your best bet is #1 - It is real easy if you look at the link.

Answer 6

Did you have a look at the Apache Commons Collections library? The BoundedFifoBuffer should exactly meet your needs.