Order of stack and queue enumeration

Question

I know that List enumeration guarantees the order of enumeration and respects the last sorting operation, I know that Dictionary and HashSet tags can not be sure that

 Dictionary<string, string> dictionary = ...; foreach(var pair in dictionary) { } 

will process pairs in the order in which they were added.

What about Stack and Queue ? Do their transfers carry out any orders?

Answer 1

For Stack enumeration is currently performed 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; } } 

Notice how it lists, starting with the index set to _stack._size-1 , and decreasing the index to return each item in LIFO order.

However, since this is not documented, you cannot guarantee that it will always be that way (although it would be abnormal for Microsoft to change the way the counter works!) P>

You can check the implementation of the nested QueueEnumerator class and similarly determine that the enumeration is performed in the order in which the elements are deleted.

Stack.GetEnumerator () strongly means that the LIFO order is used.

If you look at the example for Stack<T>.GetEnumerator() in the Microsoft documentation and check the result, you will see that it is in LIFO order.

This suggests that Microsoft is fully committed to listing Stack in LIFO order, but they forgot (or didn't bother) to explicitly document this!

Answer 2

A Queue is a collection of First-In-First-Out (FIFO) (this is explicitly stated in the documentation). This means that the enumeration provides you with the elements in the order in which they were added.

A Stack is the Last-In-First-Out (LIFO) collection. This means that the enumerator provides you with the elements in the reverse order of how they were added.

Stacks and queues are a very standard Computer Science construct, so they really cannot be reconfigured without a serious reaction. When you look at the GetEnumerator() function examples, 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 */ 

Queuing 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 the basic definitions of computer science, an enumerator or iterator should present elements in a natural way for a collection. Specific collection types have a specific order.

Caveat

Note that although the listing process reflects the natural order of the FIFO and LIFO ( ref ) collections, it is not the way Queues ( ref ) and Stacks ( ref ) are intended to be used, They are intended to be used with the Enqueue() / Dequeue() and Push() / Pop() / Peek() . Microsoft includes an enumeration so that everything is consistent with the ICollection<T> base interface and maintains the numbering in the natural order of the collection.

The purpose of the queue is to create a work pipeline that can be processed in order. The purpose of the stack is to provide a way to return to the previous context when local work is performed. They are designed to work on one subject at a time. Iterating over a collection using an enumerating view of side steps that do not completely remove elements from the queue / stack. This is essentially a look at all the objects that are.

Answer 3

Yes. This doesn't seem to be clearly documented, but the items are listed in the same order that you popped / deleted them.