What data structure will hold a bounded stack of items in LIFO ?

Question

I'm looking for a data structure that is basically a bounded stack.

If I declare that the stack can hold at most 3 items, and I push another item in, the oldest item is popped.

Answer 1

You need a queue. A singly linked list that records the first and last items. A doubly linked one if you would like to change from O(n) to O(1) traversal to update the last item.

You push objects at the front of the queue. And if the length is greater than 3, you pop the back.

Answer 2

You'll be able to implement this using a wrapper over a deque (http://en.wikipedia.org/wiki/Deque), or double-ended queue. Just make sure to call the pollLast method inside the offerFirst method if the stack size is reached.

Answer 3

Well a LIFO (Last In First Out) structure is known as a Stack which is what you need for the main part of your requirement

A FIFO (First In First Out) structure is known as a Queue which is what you need for the ability to pop the oldest Items off the back.

A combination of these is known as a Deque. Where you have to the ability to push or pop from either end.

I'm not sure if Java has a built-in Deque datastructure, but if it does (or you can find an implementation on google), You can just put some wrapping logic around to ensure that if you push to the front, and the deque.Count > 3, then also pop from the back.

Answer 4

This is in C# as I don't know Java I'm afraid but the idea should translate.

public class BoundedStack<T>
{
    private readonly int limit;
    private LinkedList<T> list;

    public BoundedStack(int limit)
    {
        this.limit = limit;
        list = new LinkedList<T>();
    }

    public void Push(T item)
    {
        if (list.Count == limit) list.RemoveFirst();
        list.AddLast(item);
    }

    public T Pop()
    {
        if (list.Count == 0) 
            throw new IndexOutOfRangeException("No items on the stack");

        var item = list.Last.Value;
        list.RemoveLast();

        return item;
    }

    public int Count()
    {
        return list.Count;
    }
}

Answer 5

Apache commons has something close to what you need except it is Fifo: CircularFifoBuffer. I think you will be stuck writing a custom wrapper to make a Lifo like implementation.

Answer 6

I'd write my own Deque implementation based on a ring buffer.