c# - Stack and Queue enumeration order

Question

I know that List enumerator guarantees the enumeration order and respects last sort operation, I know that the Dictionary and HashSet ones do not i.e. you can NOT be sure that

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

foreach(var pair in dictionary)
{

}

will process pairs in the order they were appended.

What about the Stack and the Queue? Do their enumerators guarantee any order?

Answer 1

For Stack, the enumeration is currently done by a nested private class called StackEnumerator (this is from the Reference Source):

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

Note how it enumerates starting with the index set to _stack._size-1 and decrements the index to return each element in LIFO order.

However, because this is not documented you can't guarantee that it will always be this way (although it would be insane for Microsoft to change the way that the enumerator works now!)

You can inspect the implementation of the nested QueueEnumerator class and similarly determine that the enumeration is done in the order in which items would be dequeued.

The Stack.GetEnumerator() strongly implies that LIFO order is used.

If you look at the example for Stack<T>.GetEnumerator() in Microsoft's documentation and inspect the stated output, you can see that it is in LIFO order.

This strongly suggests that Microsoft fully intend a Stack to be enumerated in LIFO order - but they forgot (or didn't bother to) to explicitly document this!