StackList<T> implementation

Question

I needed a structure that works really similar to the predefined Stack<T> 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<T> : IEnumerable<T>
{
    private readonly List<T> _stackList = new List<T>();

    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<T> 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);
    }
}

Answer 1

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<T> 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<T> : IEnumerable<T>
{
    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<T>

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

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<T>(this Stack<T> 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<T>(this Stack<T> stack, T value)
    => stack.Select((x, i) => new { x, i }).FirstOrDefault(y => y.x.Equals(value))?.i ?? -1;

Example:

var s = new Stack<int>();
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.

Answer 2

I don't know why you are going through all this trouble to add an indexer. Stack<T> has an extension method called ElementAt(Int32) that will return what you need. At the most all you need to do is this:

using System.Linq;

public class StackList<T> : Stack<T>
{
    public T this[int index]
    {
        get { return this.ElementAt(index); }
    }

    //From t3chb0t's answer
    public int IndexOf(T value) 
    {
        var result = this.Select((x, i) => new { x, i })
                         .FirstOrDefault(y => y.x.Equals(value));
        return result == null ? -1 : result.i;
    }
}

And as far as the set, I would advise against implementing it at all since it breaks the functionality of your stack. You are overwriting elements at the specified index instead of rearranging the stack. You could implement a complicated method to push the stack onto a new stack, insert the element at the position, and push the remaining elements on, but then you are really circumventing the point of a stack.

The IndexOf was an adaptation borrowed from t3chb0t's answer and should provide everything that you need.

Answer 3

You're using the stack backwards. Not only that, but it's not a true stack. (Which is fine, we'll talk about that now.)

A true stack cannot have elements directly modified. In a stack there's no sense of an "index", elements go in the top and come out the top. With that said, the easiest way to fix that is to rename this from StackList to FiloList. (Now the name is more meaningful - first-in-last-out list.)

It's far more performant to insert items at the end and then remove them from the end.

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

public void Push(T item)
{
    _stackList.Add(item);
}

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

We also used RemoveAt as Remove may not guarantee what we want.

Now, I can see why you wrote it the way you did, but we'll fix that.

You can modify this[int index] and IndexOf(T item) to work relative to the end of the stack.

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

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

You should then write your own IEnumerator which enumerates it backwards.

In the end we'll have:

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

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

    public void Push(T item)
    {
        _stackList.Add(item);
    }

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

    public IEnumerator<T> GetEnumerator()
    {
        return _stackList.GetEnumerator();
    }

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

    public T this[int index]
    {
        get { return _stackList[_stackList.Count - 1 - index]; }
        set { _stackList[_stackList.Count - 1 - 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.Count - 1 - _stackList.IndexOf(item);
    }
}

And I've tested this with yours:

Pushing 10 items to top of stack.
Pushing another item on top of stack.
Modifying second to last item to new value.
Index of item just modified: 9
Popping 10 items from top of stack.
Index: 0, value: 10
Index: 1, value: 9
Index: 2, value: 8
Index: 3, value: 7
Index: 4, value: 6
Index: 5, value: 5
Index: 6, value: 4
Index: 7, value: 3
Index: 8, value: 2
Index: 9, value: 100
Printing items left in stack.
Value left in stack: 0

And mine:

Pushing 10 items to top of stack.
Pushing another item on top of stack.
Modifying second to last item to new value.
Index of item just modified: 9
Popping 10 items from top of stack.
Index: 0, value: 10
Index: 1, value: 9
Index: 2, value: 8
Index: 3, value: 7
Index: 4, value: 6
Index: 5, value: 5
Index: 6, value: 4
Index: 7, value: 3
Index: 8, value: 2
Index: 9, value: 100
Printing items left in stack.
Value left in stack: 0

The only thing left to do is rewrite it to use a custom IEnumerator, then you'll be all set.