StackList<T> implementation

I needed a structure that works really similar to the predefined Stack but with a few extra functionalities. Examples include getting the index of value in the collection and being able to index the structure itself.

Any flaws or improvement notes are welcome!

public class StackList : IEnumerable
{
    private readonly List _stackList = new List();

    public T Pop()
    {
        if (_stackList.Count == 0)
        {
            throw new InvalidOperationException("The stack is empty");
        }
        T value = _stackList[0];
        _stackList.Remove(value);
        return value;
    }

    public void Push(T item)
    {
        _stackList.Insert(0, item);
    }

    public T Peek()
    {
        if (_stackList.Count == 0)
        {
            throw new InvalidOperationException("The stack is empty");
        }
        return _stackList[0];
    }

    public IEnumerator GetEnumerator()
    {
        return _stackList.GetEnumerator();
    }

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

    public T this[int index]
    {
        get { return _stackList[index]; }
        set { _stackList[index] = value; }
    }

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

    public void Clear()
    {
        _stackList.Clear();
    }

    public bool Contains(T item)
    {
        return _stackList.Contains(item);
    }

    public int IndexOf(T item)
    {
        return _stackList.IndexOf(item);
    }
}

Issues

public void Push(T item)
{
    _stackList.Insert(0, item);
}

The hurts the stack list.

It would be much easier if you just added new items at the end of the list. The Insert needs to rebuild the entire list:


This method is an O(n) operation, where n is Count.

For an addition this is a real bottleneck.

The same applies to the Pop method which internally uses List.Remove:


This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.

With these features the StackList is unusable - as far as performance is concerned.

I saw this comment of you:


I've made it the way it is because I wanted to be able visually see how the stack is sorted while debugging but I guess that will do.

There is a much simpler solution for debug helpers without sacrificing performance.

You can decorate your class with the DebuggerDisplay attribute and build what you need to see in debug.

Here's the pattern I use:

[DebuggerDisplay("{DebuggerDisplay,nq}")]
public class StackList : IEnumerable
{
    private string DebuggerDisplay => $"[{string.Join(", ", this)}]";
}

It's not a mistake that the property is private. The debugger will find it anyway and by being private it doesn't pollute the public API.

Challenging the purpose of the StackList

Finally I'd like to undermine the purpose of the StackList.

You write:


I needed a structure that works really similar to the predefined Stack but with a few extra functionalities for example getting the index of value in the collection and being able to index the structure itself.

I doubt you need a new type for this. With a few extensions you can achieve the same with less effort and based on the original Stack.

Let's try...


getting the index of value in the collection

We can build a new extension for this by utilizing two other extensions:

static class StackExtension
{
    public static int IndexOf(this Stack stack, T value)
    {
        var result = stack.Select((x, i) => new { x, i }).FirstOrDefault(y => y.x.Equals(value));
        return result == null ? -1 : result.i;
    }
}

or with C# 6

public static int IndexOf(this Stack stack, T value)
    => stack.Select((x, i) => new { x, i }).FirstOrDefault(y => y.x.Equals(value))?.i ?? -1;

Example:

var s = new Stack();
s.Push(1);
s.Push(2);
s.Push(3);
s.Push(4);

s.Dump();

s.IndexOf(2).Dump(); // 2
s.IndexOf(4).Dump(); // 0
s.IndexOf(5).Dump(); // -1

being able to index the structure itself

For this you don't even need to write an extension because there is already one: ElementAt and its safe equivalent ElementAtOrDefault.

StackExchange Code Review Q#147122, answer score: 13