Stack<> implementation in C#

Question

I've recently been implementing a recursive directory search implementation and I'm using a Stack to track the path elements. When I used string.Join() to join the path elements, I found that they were reversed. When I debugged the method, I looked into the stack and found that the elements themselves were reversed in the Stack's internal array, ie the most recently Push()ed element was at the beginning of the internal array, and the least recently Push()ed element was at the end of the internal array. This seems ass-backward and very counter-intuitive. Can somebody please tell me why Microsoft would implement a stack in such a manner ?

Answer 1

I think you're mistaken.

It isn't that Stack<T>.Push internally inserts an item at the start of its internal array (it doesn't). Rather, it enumerates from the top to the bottom, as this is the manner in which one would intuitively enumerate through a stack (think of a stack of pancakes: you start at the top and work your way down).

If you look at the contents of a collection from within Visual Studio's debugger, I think it will display them to you in the order they're enumerated -- not the order they're stored internally*.

Take a look at the Stack<T>.Push method in Reflector and you'll see that the code is basically exactly what you'd expect:

// (code to check array size)
this._array[this._size++] = item;
// (code to update internal version number)

So the stack internally adds new elements onto the end of its internal array. It's the Stack<T>.Enumerator class that's got you confused, not the Stack<T> class itself.

_{*I don't know whether this is true in general, but it's true for Stack<T>; see Hans Passant's excellent answer for the reason why.}

Answer 2

You had me going there for a bit, that indeed looks completely bass-ackwards. There is however something else going on. The Stack<> class has a debugger visualizer, named System_StackDebugView<>. It is an internal class, you'd have to look with Reflector to see it.

That visualizer has an Items property, that's what you look at when you expand the node in the debugger. That Items property uses Stack<>.ToArray(). Which looks like this:

public T[] ToArray()
{
    T[] localArray = new T[this._size];
    for (int i = 0; i < this._size; i++)
    {
        localArray[i] = this._array[(this._size - i) - 1];
    }
    return localArray;
}

Yup, backwards.