Data Structure for FIFO Implementation When Getting ith Element

Question

I want a data structure that will be fixed size and will work as FIFO. I mean if size exceeds the very first element will be removed. Also after each insertion I want to check the middle element at that structure (i.e. 10th element at size of 21)

I consider to use ArrayDeque but Deque interface does not consider the order. i.e. getting the ith element)

I will use it for a time consuming process and performance is important for me. What is the suggested data structure for my purpose?

Answer 1

Lets assume we are talking about a FIFO that will typically contain lots of elements.

• An ArrayList is not a good choice, because removing the element at start of the list is an O(N) operation. (For a list with N elements)

• An LinkedList may not be a good choice, because getting the Nth element is an O(N) operation.

I think you need a circular buffer backed by an array. This will give you O(1) FIFO insertion, O(1) FIFO removal, and O(1) indexed get of the element i from the FIFO start. The circular buffer behaviour is inplemented using two index, one for the position of the start of the queue, and one for the position of the end. Insertion and removal just involve moving one or other of the indexes, and get(i) boils down to a fetch of backingArray[(startPos + i) % backingArray.length] with some error checking.

If you need the FIFO to be expandable, you can implement this by doubling the size of the backing array ... and still get amortized O(1) for insertion, removal and indexing.

---

I think that the Apache Commons CircularFifoQueue class matches your requirements for the fixed sized FIFO case. It includes a get(i) method for getting the ith element.

Answer 2

You can use LinkedList. http://docs.oracle.com/javase/1.5.0/docs/api/java/util/LinkedList.html

LinkedList implements the queue interface (FIFO) but you can also get items at a specific position in the queue

For example:

LinkedList<Object> queue = new LinkedList<Object>();

public void insertObject(Object o)
{
   int middleElement = queue.size/2;
   if(queue.size > 20) //If full
   {
        queue.Poll(); //remove the first element
        queue.Offer(o); //Adds the element
        print(queue.Get(middleElement)); //Print the middle element

   }
   else //If not full
   {
      queue.Offer(o); //Adds the element
      print(queue.Get(middleElement)); //Print the middle element

   }
}