Implementación de Stack <> en C#

Question

Recientemente he estado implementando una implementación de búsqueda de directorio recursiva y estoy usando una Pila para seguir los elementos de ruta. Cuando utilicé string.Join() para unirme a los elementos de la ruta, descubrí que estaban invertidos. Cuando depuré el método, busqué en la pila y encontré que los elementos se invirtieron en la matriz interna de la Pila, es decir, el elemento Push() ed más reciente estaba al principio de la matriz interna, y el menos recientemente Push() El elemento ed estaba al final de la matriz interna. Esto parece ir hacia atrás y muy contrario a la intuición. ¿Alguien puede decirme por qué Microsoft implementaría una pila de esa manera?

Answer 1

Creo que estás equivocado.

No es que Stack<T>.Push internamente inserta un elemento al comienzo de su matriz interna (no es así). Más bien, enumera de arriba a abajo, ya que esta es la manera en que uno enumeraría intuitivamente a través de una pila (piense en una pila de panqueques: comienza en la parte superior y avanza hacia abajo).

Si observa los contenidos de una colección desde el depurador de Visual Studio, creo que los mostrará en el orden en que están enumerados, no el orden en que están almacenados internamente *.

Tome una mirada en el método Stack<T>.Push en Reflector y verá que el código es básicamente exactamente lo que se espera:

// (code to check array size) 
this._array[this._size++] = item; 
// (code to update internal version number) 

Así que la pila se suma internamente nuevos elementos al final de su interior formación. Es la clase Stack<T>.Enumerator la que te confunde, no la clase Stack<T>.

_{* No sé si esto es cierto en general, pero es cierto para Stack<T>; ver Hans Passant's excellent answer por la razón por la cual.}

Answer 2

Lo que describió es la implementación correcta, ya que una pila es una estructura LIFO (último en entrar, primero en salir). Imagínelo como una pila de placas, el último elemento colocado en la pila es el primero eliminado. ¿Has encontrado una pila en otro lugar que sea FIFO?

FIFO sería una cola.

Answer 3

No veo qué importa qué final consideren la parte superior de la pila, siempre y cuando sepa de qué lado se trata. En realidad, tiene más sentido que cuando "empujas" algo hacia la pila, lo estés empujando hacia arriba (comenzando) y moviendo los otros elementos hacia abajo ...

Answer 4

Me tenías yendo allí un poco, que de hecho se ve completamente a favor de los bajos. Sin embargo, está sucediendo algo más. La clase Stack <> tiene un visualizador de depuración, llamado System_StackDebugView <>. Es una clase interna, tendrías que mirar con Reflector para verla.

Ese visualizador tiene una propiedad Items, eso es lo que se ve al expandir el nodo en el depurador. Esa propiedad Items usa Stack <> .ToArray(). Que se ve así:

public T[] ToArray() 
{ 
    T[] localArray = new T[this._size]; 
    for (int i = 0; i < this._size; i++) 
    { 
     localArray[i] = this._array[(this._size - i) - 1]; 
    } 
    return localArray; 
} 

Yup, al revés.

Answer 5

Así es como se implementan los métodos push y pops de la pila. Tenga en cuenta que está utilizando el último índice en la matriz, en lugar del primero. Por lo tanto, debe haber algún otro problema para que el suyo retroceda.

public virtual void Push(object obj) 
    { 
     if (this._size == this._array.Length) 
     { 
      object[] destinationArray = new object[2 * this._array.Length]; 
      Array.Copy(this._array, 0, destinationArray, 0, this._size); 
      this._array = destinationArray; 
     } 
     this._array[this._size++] = obj; 
     this._version++; 
    } 


public virtual object Pop() 
    { 
     if (this._size == 0) 
     { 
      throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack")); 
     } 
     this._version++; 
     object obj2 = this._array[--this._size]; 
     this._array[this._size] = null; 
     return obj2; 
    } 

Answer 6

Para añadir a las otras respuestas, si en el depurador se desplaza hacia abajo a la parte inferior de la pila <> 's elementos y abrir Raw Ver-> miembros que no son públicas -> _ matriz se puede ver la contenido de la matriz interna real utilizada para contener los elementos y verificar que estén en el orden esperado.