10
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ This one is working ! @t3chb0t \$\endgroup\$ – Denis Nov 15 '16 at 16:56
  • \$\begingroup\$ (Re?)Defining basic data structures in C# is rarely necessary, or even desirable, in practice. \$\endgroup\$ – Mark Rogers Nov 15 '16 at 17:50
  • 3
    \$\begingroup\$ @MarkRogers I redefined a Queue in C# that is 2x the speed of the Microsoft supplied version just this morning. \$\endgroup\$ – 410_Gone Nov 16 '16 at 1:39
  • \$\begingroup\$ Sure, but its rare that one actually needs that level of optimization in a basic data structure when using C#. \$\endgroup\$ – Mark Rogers Nov 16 '16 at 2:37
  • 1
    \$\begingroup\$ @mbomb007 All of them. \$\endgroup\$ – 410_Gone Nov 16 '16 at 15:49
13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ in which case the Remove must be replaced by RemoveAt (it would have been a good idea anyway for perf, now it is mandatory to fit the requirements) \$\endgroup\$ – njzk2 Nov 15 '16 at 20:22
  • 1
    \$\begingroup\$ Thank you a lot for the nice answer t3chb0t i really think you are doing great job here at CodeReview always providing a comprehensive and competent opinion keep up the good work ! \$\endgroup\$ – Denis Nov 16 '16 at 6:13
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ index of value is different than value at index \$\endgroup\$ – Denis Nov 15 '16 at 17:22
  • \$\begingroup\$ @denis Missed that one, I borrowed the method from t3chb0t's answer to get the IndexOf method. I think that is what you meant anyway... \$\endgroup\$ – Ron Beyer Nov 15 '16 at 17:30
  • 1
    \$\begingroup\$ I agree, either derived or with extensions, either way it will work without a complete new implemention. \$\endgroup\$ – t3chb0t Nov 15 '16 at 17:33
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Denis Nov 15 '16 at 17:03
  • \$\begingroup\$ @denis Added information on fixing those. \$\endgroup\$ – 410_Gone Nov 15 '16 at 17:09
  • \$\begingroup\$ "A true stack cannot have elements directly modified." Do you have a reference for this? In the physical world, if I have a stack of microwaves, I can easily change the contents of any single microwave by opening its door. I'm not doubting you; just would like the reference. \$\endgroup\$ – Kenneth K. Nov 16 '16 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.