Alternative for the Stack

Question

I am working in .Net environment using C#. I need some alternative for the Stack data structure. Some kind of bound stack. The quantity of elements in the collection shouldn't exceed some fixed specified number. And, if that number achieved and new element is pushed, than most older element must be deleted. I need this for storing commands for Undo/Redo strategies.

Answer 1

A circular buffer should do the job; easy enough to wrap a list or array, but nothing built in AFAIK.

Answer 2

Johnny Coder has an implementation here: http://johnnycoder.com/blog/2008/01/07/undo-functionality-with-a-limited-stack/

Answer 3

This is an implementation of a stack with a constrained capacity. After reaching the given capacity, bottom items of the stack beyond the capacity are discarded. It is possible to iterate through the contained objects and set the index to a specifc position (like a rewind) for discarding multiple entries at once when pushing a new item to the stack.

This is an own implementation with some goodies that prevents you from handling more then one list if you need to go back in the history and forward again (is builtin).

public class DiscardingStack<TObject> : IEnumerable<TObject>
{
    private readonly int capacity;

    private readonly List<TObject> items;

    private int index = -1;

    public DiscardingStack(int capacity)
    {
        this.capacity = capacity;
        items = new List<TObject>(capacity);
    }

    public DiscardingStack(int capacity, IEnumerable<TObject> collection)
        : this(capacity)
    {
        foreach (var o in collection)
        {
            Push(o);
        }
    }

    public DiscardingStack(ICollection<TObject> collection)
        : this(collection.Count, collection)
    {
    }

    public void Clear()
    {
        if (items.Count >= 0)
        {
            items.Clear();
            index = items.Count - 1;
        }
    }

    public int Index
    {
        get { return index; }
        set
        {
            if (index >= 0 && index < items.Count)
            {
                index = value;
            }
            else throw new InvalidOperationException();
        }
    }

    public int Count
    {
        get { return items.Count; }
    }

    public TObject Current
    {
        get { return items[index]; }
        set { index = items.IndexOf(value); }
    }

    public int Capacity
    {
        get { return capacity; }
    }

    public TObject Pop()
    {
        if (items.Count <= 0)
            throw new InvalidOperationException();

        var i = items.Count - 1;
        var removed = items[i];
        items.RemoveAt(i);

        if (index > i)
            index = i;

        return removed;
    }

    public void Push(TObject item)
    {
        if (index == capacity - 1)
        {
            items.RemoveAt(0);
            index--;
        }
        else if (index < items.Count - 1)
        {
            var removeAt = index + 1;
            var removeCount = items.Count - removeAt;
            items.RemoveRange(removeAt, removeCount);
        }

        items.Add(item);

        index = items.Count - 1;
    }

    public TObject Peek()
    {
        return items[items.Count-1];
    }

    public TObject this[int i]
    {
        get { return items[i]; }
    }

    public IEnumerator<TObject> GetEnumerator()
    {
        return items.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Anyway, building a stack that discards elements when the maximum capacity is reached should be implemented using a LinkedList (as suggested above) if your list is huge (avoids copying). So the LinkedList idea might be better in such a case instead of wrapping a List if the buffer maximum is a high value.

I would also recommend to pack the Push(), Pop() etc. into an interface (e.g. IStack). Sadly, there is no IStack interface predefined in .Net (afaik).

Answer 4

.Net is rather deficient in type of collections. You'll find a collection library here. Use CircularQueue.

Answer 5

There's no builtin Class for this in Framework. (we dont expect to delete data automatically). But you can very well Extend the Stack class and Override Push/Pop and other Methods to suit your needs.