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

What you described is the correct implementation, as a stack is a LIFO (Last in First out) structure. Imagine it like a stack of plates, the most recently element placed into the stack is the first one removed. Have you run into a stack elsewhere that is FIFO?

FIFO would be a Queue.

Answer 2

I don't see what it matters which end they consider the top of the stack, as long as you now know which end it is. It actually makes more sense that when you 'push' something on to the stack, you're pushing it on the top (beginning) and moving the other items down...

Answer 3

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 4

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.

Answer 5

Here is how the stack's push and pops methods are implemented. Notice that it is using the last index in the array, rather than the first. So there must be some other problem going on to get yours backwards.

   public virtual void Push(object obj)
    {
        if (this._size == this._array.Length)
        {
            object[] destinationArray = new object[2 * this._array.Length];
            Array.Copy(this._array, 0, destinationArray, 0, this._size);
            this._array = destinationArray;
        }
        this._array[this._size++] = obj;
        this._version++;
    }


 public virtual object Pop()
    {
        if (this._size == 0)
        {
            throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack"));
        }
        this._version++;
        object obj2 = this._array[--this._size];
        this._array[this._size] = null;
        return obj2;
    }

Answer 6

To add to the other answers, if in the debugger you scroll down to the bottom of your Stack<>'s elements and open up Raw View->Non-Public members->_array you can see the contents of the actual internal array used to hold the items and verify that they are in the expected order.