Stack и Queue перечисления заказ

Question

Я знаю, что List Перечислителя гарантирует порядок перечисления и уважает последнюю операцию сортировки, я знаю, что Dictionary и HashSet из них не есть вы можете НЕ быть уверен, что

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

foreach(var pair in dictionary) 
{ 

} 

будет обрабатывать пары в том порядке, в котором они были добавлены.

Как насчет Stack и Queue? Выполняют ли их перечисления какие-либо заказы?

Answer 1

Для Stack, перечисление в настоящее время осуществляется с помощью вложенного частного класса под названием StackEnumerator (это из 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; 
    } 
}  

Обратите внимание, как она перебирает, начиная с индексом, установленным в _stack._size-1 и вычитает индекс возвращает каждый элемент в порядке LIFO.

Однако, поскольку это не документировано, вы не можете гарантировать, что это всегда будет так (хотя это было бы безумием для Microsoft, чтобы изменить способ, что переписчик работает сейчас)

Вы можете проверьте реализацию вложенного класса QueueEnumerator и аналогичным образом определите, что перечисление выполняется в том порядке, в котором элементы будут удалены.

The Stack.GetEnumerator() настоятельно указывает, что используется заказ LIFO.

Если вы посмотрите на the example for Stack<T>.GetEnumerator() in Microsoft's documentation и проверите указанный результат, вы увидите, что он находится в порядке LIFO.

Это настоятельно указывает на то, что Microsoft полностью намерена перечислить Stack в порядке LIFO, но они забыли (или не потрудились) явно документировать это!

Answer 2

Да. Кажется, что это явно не документировано, но элементы перечислены в том же порядке, что и вы выскочили/выгрузили их.

Answer 3

A Queue представляет собой коллекцию First-In-First-Out (FIFO) (это прямо сказано в документации). Это означает, что перечисление предоставляет вам элементы в том порядке, в котором они были добавлены.

A Stack - коллекция Last-In-First-Out (LIFO). Это означает, что перечислитель предоставляет вам элементы в обратном порядке того, как они были добавлены.

Стеки и очереди представляют собой очень стандартную конструкцию компьютерных наук, поэтому они действительно не могут быть переназначены без серьезной реакции.Когда вы смотрите на примеры для GetEnumerator() функций, это ясно указывает порядок перечисления:

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 

    */ 

Опять же, с основными определениями информатики, счетчику или итератор должен представить элементы в естественном порядке для коллекции. Конкретные типы сбора имеют определенный порядок.

Caveat

Пожалуйста, обратите внимание, что в то время как процесс перечисления действительно отражает естественный порядок коллекций ФИФО и ЛИФО (ref), это не так, как Очереди (ref) и стеки (ref) являются предназначены быть использованным. Они предназначены для использования с взаимодействиями Enqueue()/Dequeue() и Push()/Pop()/Peek(). Microsoft включает в себя перечислитель, чтобы все было согласовано с базовым интерфейсом ICollection<T> и сохраняло нумерацию в естественном порядке коллекции.

Целью очереди является создание конвейера работы, который может быть обработан в порядке. Целью стека является предоставление способа возврата к предыдущему контексту, когда выполняется локальная работа. Они предназначены для работы по одному предмету одновременно. Итерирование по коллекции с помощью перечисляющего вида боковых шагов, целиком и не удаляющих элементы из очереди/стека. Это, по сути, взгляд на все предметы, которые есть.