堆栈和队列枚举顺序

Question

我知道List枚举器保证枚举顺序并尊重最后的排序操作,我知道那些Dictionary和HashSet那些不是,你不能确定

Dictionary<string, string> dictionary = ...;

foreach(var pair in dictionary)
{

}

将按照附加顺序处理对.

怎么样Stack和Queue？他们的调查员是否保证任何订单？

Answer 1

因为Stack,枚举当前由一个名为的嵌套私有类完成StackEnumerator(这来自参考源):

private class StackEnumerator : IEnumerator, ICloneable
{
    private Stack _stack;
    private int _index;
    private int _version;
    private Object currentElement;

    internal StackEnumerator(Stack stack) {
        _stack = stack;
        _version = _stack._version;
        _index = -2;
        currentElement = null;
    }

    public Object Clone()
    {
        return MemberwiseClone();
    }

    public virtual bool MoveNext() {
        bool retval;
        if (_version != _stack._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
        if (_index == -2) {  // First call to enumerator.
            _index = _stack._size-1;
            retval = ( _index >= 0);
            if (retval)
                currentElement = _stack._array[_index];
            return retval;
        }
        if (_index == -1) {  // End of enumeration.
            return false;
        }

        retval = (--_index >= 0);
        if (retval)
            currentElement = _stack._array[_index];
        else
            currentElement = null;
        return retval;
    }

    public virtual Object Current {
        get {
            if (_index == -2) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
            if (_index == -1) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
            return currentElement;
        }
    }

    public virtual void Reset() {
        if (_version != _stack._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
        _index = -2;
        currentElement = null;
    }
}    

请注意它如何枚举从索引设置开始_stack._size-1并递减索引以返回LIFO顺序中的每个元素.

但是,因为没有记录,你无法保证它总是这样(尽管微软改变枚举器现在工作的方式是疯狂的!)

您可以检查嵌套QueueEnumerator类的实现,并类似地确定枚举是按照项目出列的顺序完成的.

Stack.GetEnumerator()强烈暗示使用LIFO顺序.

如果您查看Microsoft文档中的示例Stack<T>.GetEnumerator()并检查所声明的输出,您可以看到它是LIFO顺序.

这强烈暗示微软完全打算以LIFO顺序枚举一个堆栈 - 但是他们忘记了(或者没有费心)明确记录这个!

Answer 2

一个队列是一个先入先出(FIFO)集合(说的文档中这样的权利).这意味着枚举器按照添加顺序为您提供项目.

一个堆栈是一个后进先出(LIFO)集合.这意味着枚举器以与添加方式相反的顺序为您提供项目.

堆栈和队列是非常标准的计算机科学构造,因此如果没有严重的反弹,它们真的无法重新定位.当您查看GetEnumerator()函数的示例时,它会清楚地记录枚举的顺序:

堆栈枚举:

    Stack<string> numbers = new Stack<string>();
    numbers.Push("one");
    numbers.Push("two");
    numbers.Push("three");
    numbers.Push("four");
    numbers.Push("five");

    // A stack can be enumerated without disturbing its contents.
    foreach( string number in numbers )
    {
        Console.WriteLine(number);
    }

    /* This code example produces the following output:

     five
     four
     three
     two
     one

    */

队列枚举:

    Queue<string> numbers = new Queue<string>();
    numbers.Enqueue("one");
    numbers.Enqueue("two");
    numbers.Enqueue("three");
    numbers.Enqueue("four");
    numbers.Enqueue("five");

    // A queue can be enumerated without disturbing its contents.
    foreach( string number in numbers )
    {
        Console.WriteLine(number);
    }

    /* This code example produces the following output:

     one
     two
     three
     four
     five

    */

同样,对于基本的计算机科学定义,枚举器或迭代器必须以集合的自然顺序呈现元素.特定的集合类型具有已定义的顺序.

警告

请注意,虽然枚举过程确实反映了FIFO和LIFO集合(的自然顺序REF),这不是多么队列(REF)和堆栈(REF)的意图使用.它们旨在与Enqueue()/ Dequeue()和Push()/ Pop()/ Peek()交互一起使用.Microsoft包含枚举器以使所有内容与基本ICollection<T>接口保持一致,并使枚举器保持在集合的自然顺序中.

队列的目的是提供可以按顺序处理的工作流程.Stack的目的是提供一种在本地工作完成时返回到先前上下文的方法.它们旨在一次处理一个项目.使用枚举器类型的迭代迭代集合,完整的目的并不会从队列/堆栈中删除项目.它基本上是对所有物品的窥视.