What data structure do I need or how to implement a "LIFO-like" queue?

.net, c#, data-structures, generics

Solution

There is Stack in base .NET library, but that doesn't have the last requirement. And I believe there is no existing structure like that, so you have to implement it yourself.

But that shouldn't be a problem. Just create a linked list where you add and remove from one side and remove from other when number of items exceeds given size. You could optimize it by using an array with begin-end pointers, but then you would have to periodically re-arrange the array so you don't run out of space. The cyclic version could actually work better than rearanging.

I did some quick hacking with the cyclic version. I'm sure you can add the interfaces yourself.

public class DroppingStack<T> : IEnumerable<T>
{
    T[] array;
    int cap;
    int begin;
    int end;
    public DroppingStack (int capacity)
    {
        cap = capacity+1;
        array = new T[cap];
        begin = 0;
        end = 0;
    }

    public T pop()
    {
        if (begin == end) throw new Exception("No item");
        begin--;
        if (begin < 0)
            begin += cap;
        return array[begin];
    }

    public void push(T value)
    {
        array[begin] = value;
        begin = (begin+1)%cap;
        if (begin == end)
            end = (end + 1) % cap;
    }

    public IEnumerator<T> GetEnumerator()
    {
        int i = begin-1;
        while (i != end-1)
        {
            yield return array[i];
            i--;
            if (i < 0)
                i += cap;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

Problem

I'm looking for a data structure that behaves like this: - Last in, first out - Upon iteration the first item is the item that was last in (LCFS - last come, first served) - When max capacity is reached, the 'oldest' item(s) need(s) to be dropped It sounds like a `Queue` would do the trick, but that structure is FIFO. Sounds like I need a LIFO-like queue. Any ideas what I should use?

Original source