Pila e coda ordine enumerazione

Question

So che List enumeratore garantisce l'ordine di enumerazione e rispetta l'ultima operazione di ordinamento, so che il Dictionary e HashSet quelli non cioè si può NON essere sicuri che

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

foreach(var pair in dictionary) 
{ 

} 

volontà elaborare le coppie nell'ordine in cui sono state aggiunte.

E lo Stack e lo Queue? I loro enumeratori garantiscono qualsiasi ordine?

Answer 1

Per Stack, l'enumerazione è attualmente fatto da una classe privata nidificato chiamato StackEnumerator (questo è dal 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; 
    } 
}  

Nota come enumera a partire dall'indice impostato _stack._size-1 e decrementa l'indice restituisce ogni elemento nell'ordine LIFO.

Tuttavia, poiché questo non è documentata non si può garantire che sarà sempre in questo modo (anche se sarebbe folle per Microsoft di cambiare il modo in cui l'enumeratore ora funziona!)

Puoi ispezionare l'implementazione della classe nidificata QueueEnumerator e determinare in modo simile che l'enumerazione venga eseguita nell'ordine in cui gli elementi verranno rimossi dalla coda.

Il Stack.GetEnumerator() implica fortemente che viene utilizzato l'ordine LIFO.

Se si guarda the example for Stack<T>.GetEnumerator() in Microsoft's documentation e si controlla l'output indicato, è possibile vedere che è in ordine LIFO.

Questo suggerisce fortemente che Microsoft intenda che uno stack sia elencato nell'ordine LIFO, ma si sono dimenticati (o non si sono preoccupati di farlo) di documentarlo esplicitamente!

Answer 2

Sì. Non sembra essere esplicitamente documentato, ma gli elementi sono enumerati nello stesso ordine come se li si fosse scansionati/cancellati.

Answer 3

A Queue è una raccolta FIFO (First-In-First-Out) (lo dice correttamente nella documentazione). Ciò significa che l'enumeratore ti fornisce gli articoli nell'ordine in cui sono stati aggiunti.

A Stack è una raccolta Last-In-First-Out (LIFO). Ciò significa che l'enumeratore ti fornisce gli articoli in ordine inverso rispetto a come sono stati aggiunti.

Stack e code sono costrutti di computer Science molto standard, quindi non possono essere ri-proposti senza un serio contraccolpo.Quando si guarda gli esempi per le GetEnumerator() funzioni, documenta in modo chiaro l'ordine di elencazione:

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 

    */ 

Anche in questo caso, con le definizioni di informatica di base, Enumeratore o l'iteratore deve presentare gli elementi nell'ordine naturale per una raccolta. I tipi di raccolta specifici hanno un ordine definito.

Caveat

Si prega di notare che mentre il processo di enumerazione fa riflettere l'ordine naturale delle collezioni FIFO e LIFO (ref), questo non è come Code (ref) e pile (ref) sono destinato da essere usato. Sono concepiti per essere utilizzati con le interazioni Enqueue()/Dequeue() e Push()/Pop()/Peek(). Microsoft include l'enumeratore per mantenere tutto coerente con l'interfaccia di base ICollection<T> e mantiene l'enumeratore nell'ordine naturale della raccolta.

Lo scopo di una coda è fornire una pipeline di lavoro che può essere elaborata in ordine. Lo scopo di una pila è di fornire un modo per tornare a un contesto precedente quando il lavoro locale è terminato. Sono destinati a lavorare su un oggetto alla volta. Iterazione sulla raccolta con un tipo di enumeratore di passaggi laterali che ha lo scopo completo e non rimuove gli elementi dalla coda/pila. È essenzialmente una sbirciatina in tutti gli oggetti che ci sono.