9

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 ?

3
  • 6
    It sounds like you want a Queue and not a Stack. Jul 9, 2010 at 17:29
  • No, I'm iterating through the tree depth-first, it needs to be a stack, but that's not really relevant to the question. Jul 9, 2010 at 17:52
  • 1
    Real men use stacks that start at the highest address and grow down.
    – Ben Voigt
    Jul 9, 2010 at 23:15

6 Answers 6

35

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.

3
  • 1
    +1, in answer to the OP, it's very intuitive to me to see the top of the stack first.
    – jfsk3
    Jul 9, 2010 at 17:33
  • When I looked at the internal array of the stack in the debugger, I assumed that it would show me the actual order of the elements internally, rather than how they're enumerated through the IEnumerable interface. Thank you for clarifying that. Jul 9, 2010 at 17:53
  • You can also use the debugger to view the contents of the actual internal array storing the elements. See my answer for details: stackoverflow.com/questions/3215052/stack-implementation-in-c/…
    – Redwood
    Jul 9, 2010 at 23:07
17

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.

11

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.

7
  • The picture on the wiki page explains this very well, actually tinyurl.com/lwtr2 (sorry for the tinyURL, stackoverflow doesn't like the wiki URL for some reason) Jul 9, 2010 at 17:29
  • I don't know why someone voted you down on this. Your answer is text book correct.
    – Josh
    Jul 9, 2010 at 17:30
  • The bottom of a stack is usually in ar[0], and the top grows towards the end of the array. Sticking the most recent element at the front requires shifting every element when anything is pushed or popped. Remember, the original question was asking for implementation, not logical details. Jul 9, 2010 at 17:31
  • 3
    I could be wrong, but I think you've misinterpreted Alex's question. What I think he's asking is why a stack would be implemented with the most recent element inserted at the beginning of an internal array. That is to say, I think he's been "tricked" by Visual Studio's debugger into thinking this is how MS implemented Stack<T> (it isn't, of course, but you can see why he would be confused by this).
    – Dan Tao
    Jul 9, 2010 at 17:36
  • 1
    @ziplin OP was confused by the debugger which showed the top of the stack at ar[0]. It turns out it isn't, but that's not important. Based on the question as asked, it is an inefficient and stupid implementation, not the "correct implementation". Jul 9, 2010 at 17:41
2

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;
    }
2
  • And the solution to the problem is that Stack<>.toArray() is returning a reverse copy, rather than this._array Jul 9, 2010 at 18:04
  • Yeah you're correct it is the ToArray method, which is weird and backwards from what I would expect, but I don't see why you would be using the returned Array like a stack. But as to answer the question, I have no idea why Microsoft would have done that.
    – Pieces
    Jul 9, 2010 at 21:33
1

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.

0

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...

2
  • 1
    But moving things down takes O(n) time for push and pop. Just putting it on top takes O(1) (amortized if you need to copy the array into a larger one). So there are huge efficiencies to be gained from having the top of the stack at the end of the array. Jul 9, 2010 at 17:44
  • 1
    As answered by Dan Tao, it's not actually stored that way, just enumerated that way.
    – Fosco
    Jul 9, 2010 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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