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!

Answer 2

A Queue is a First-In-First-Out (FIFO) collection (says so right in the documentation). That means the enumerator gives you the items in the order that they were added.

A Stack is a Last-In-First-Out (LIFO) collection. That means the enumerator gives you the items in reverse order of how they were added.

Stacks and Queues are very standard Computer Science constructs, so they really can't be re-purposed without serious backlash. When you look at the examples for the GetEnumerator() functions, it clearly documents the order of enumeration:

Stack Enumeration:

    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 Enumeration:

    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

    */

Again, with basic computer science definitions, An enumerator or iterator must present the elements in the natural order for a collection. Specific collection types have a defined order.

Caveat

Please note that while the enumeration process does reflect the natural order of the FIFO and LIFO collections (ref), this is not how Queues (ref) and Stacks (ref) are intended to be used. They are intended to be used with the Enqueue()/Dequeue()and Push()/Pop()/Peek() interactions. Microsoft includes the enumerator to keep everything consistent with the base ICollection<T> interface, and keeps the enumerator in the collection's natural order.

The purpose of a Queue is to provide a pipeline of work that can be processed in order. The purpose of a Stack is to provide a way of returning to a previous context when the local work is done. They are intended to work on one item at a time. Iterating over the collection with an enumerator kind of side steps that whole purpose and does not remove items from the queue/stack. It's essentially a peek at all the items that are there.

Answer 3

Yes. It doesn't seem to be explicitly documented, but elements are enumerated in the same order as if you popped/dequeued them.