C#中的Stack <>实现

Question

我最近一直在实现递归目录搜索实现,我正在使用Stack来跟踪路径元素.当我使用string.Join()加入路径元素时,我发现它们被颠倒了.当我调试方法时,我查看了堆栈,发现元素本身在Stack的内部数组中是相反的,即最近的Push()ed元素位于内部数组的开头,而最近最近的Push() ed元素位于内部数组的末尾.这似乎是落后的,非常反直觉.有人可以告诉我为什么微软会以这种方式实现堆栈？

Answer 1

我觉得你错了.

它不是在Stack<T>.Push内部插入一个项目在其内部数组的开头(它没有).相反,它从顶部到底部进行枚举,因为这是一种直观地通过堆栈进行枚举的方式(想想一堆煎饼:你从顶部开始向下工作).

如果从Visual Studio的调试器中查看集合的内容,我认为它将按照它们枚举的顺序显示给您 - 而不是它们在内部存储的顺序*.

看看Reflector中的Stack<T>.Push方法,您会发现代码基本上与您期望的完全相同:

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

因此,堆栈在内部将新元素添加到其内部数组的末尾.这是Stack<T>.Enumerator那种有你困惑类,而不是Stack<T>类本身.

_{*我不知道这一般是否属实,但确实如此Stack<T>; 看看Hans Passant的优秀答案.}

Answer 2

你让我去了那里,确实看起来完全是低音的.然而,还有其他事情发生了.Stack <>类有一个名为System_StackDebugView <>的调试器可视化器.这是一个内部类,您必须使用Reflector查看它.

该可视化工具具有Items属性,这是您在调试器中展开节点时所看到的内容.Items属性使用Stack <>.ToArray().看起来像这样:

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

是的,向后.

Answer 3

您所描述的是正确的实现,因为堆栈是LIFO(后进先出)结构.想象它就像一堆盘子,最近放入堆叠的元素是第一个被移除的元素.你有没有遇到过FIFO的堆栈？

FIFO将是一个队列.