C# clonar una pila

Question

Tengo pocas pilas en mi código que utilizo para hacer un seguimiento de mi ubicación lógica. En ciertos momentos necesito duplicar las pilas, pero parece que no puedo clonarlas de manera que conserve el orden. Solo necesito una duplicación superficial (referencias, no objeto).

¿Cuál sería la forma correcta de hacerlo? ¿O debería usar algún otro tipo de pilas?

NOTA: Vi esta publicación Stack Clone Problem: .NET Bug or Expected Behaviour?, pero no estoy seguro de cómo configurar el método de clonación para la clase Stack.

NOTA # 2: Consumo System.Collection.Generic.Stack

Answer 1

var clonedStack = new Stack<T>(new Stack<T>(oldStack)); 

Usted puede escribir esto como un método de extensión como

public static Stack<T> Clone<T>(this Stack<T> stack) { 
    Contract.Requires(stack != null); 
    return new Stack<T>(new Stack<T>(stack)); 
} 

Esto es necesario debido a que el Stack<T> constructor que estamos usando aquí es Stack<T>(IEnumerable<T> source) y, por supuesto, cuando itere sobre la implementación IEnumerable<T> para un Stack<T>, va a sacar elementos repetidamente de la pila, de modo que se los alimentará en el orden inverso al que usted y ellos para ir a la nueva pila. Por lo tanto, hacer este proceso dos veces dará como resultado que la pila esté en el orden correcto.

alternativa:

var clonedStack = new Stack<T>(oldStack.Reverse()); 


public static Stack<T> Clone<T>(this Stack<T> stack) { 
    Contract.Requires(stack != null); 
    return new Stack<T>(stack.Reverse()); 
} 

Una vez más, tenemos que caminar la pila en el orden inverso a la salida de la iteración en la pila.

Dudo que haya una diferencia de rendimiento entre estos dos métodos.

Answer 2

Ésta es una forma fácil, usando LINQ:

var clone = new Stack<ElementType>(originalStack.Reverse()); 

Se puede crear un método de extensión para hacer esto más fácil:

public static class StackExtensions 
{ 
    public static Stack<T> Clone<T>(this Stack<T> source) 
    { 
     return new Stack<T>(originalStack.Reverse()); 
    } 
} 

Uso:

var clone = originalStack.Clone(); 

Answer 3

Si no' Necesito un Stack`1 real, pero solo quiero una copia rápida de un Stack`1 existente que y Puede caminar en el mismo orden en que regresa Pop, otra opción es duplicar el Stack`1 en un Queue`1. Los elementos serán Dequeue en el mismo orden en que van a Pop desde el original Stack`1.

using System; 
using System.Collections.Generic; 

class Test 
{ 
    static void Main() 
    { 
    var stack = new Stack<string>(); 

    stack.Push("pushed first, pop last"); 
    stack.Push("in the middle"); 
    stack.Push("pushed last, pop first"); 

    var quickCopy = new Queue<string>(stack); 

    Console.WriteLine("Stack:"); 
    while (stack.Count > 0) 
     Console.WriteLine(" " + stack.Pop()); 
    Console.WriteLine(); 
    Console.WriteLine("Queue:"); 
    while (quickCopy.Count > 0) 
     Console.WriteLine(" " + quickCopy.Dequeue()); 
    } 
} 

Salida:

 
Stack: 
    pushed last, pop first 
    in the middle 
    pushed first, pop last 

Queue: 
    pushed last, pop first 
    in the middle 
    pushed first, pop last 

Answer 4

Para aquellos que cuidan de rendimiento ..Hay algunas otras formas forma de repetición de los miembros de la pila originales, sin grandes pérdidas en el rendimiento:

public T[] Stack<T>.ToArray(); 
public void Stack<T>.CopyTo(T[] array, int arrayIndex); 

me escribió un programa en bruto (el enlace se proporciona al final del post) para medir el desempeño y añadido dos pruebas para las implementaciones que han sido sugeridas (ver Clone1 y Clone2), y dos pruebas para ToArray y CopyTo enfoques (ver Clone3 y Clone4, tanto de ellos un uso más eficiente Array.Reverse método).

public static class StackExtensions 
{ 
    public static Stack<T> Clone1<T>(this Stack<T> original) 
    { 
     return new Stack<T>(new Stack<T>(original)); 
    } 

    public static Stack<T> Clone2<T>(this Stack<T> original) 
    { 
     return new Stack<T>(original.Reverse()); 
    } 

    public static Stack<T> Clone3<T>(this Stack<T> original) 
    { 
     var arr = original.ToArray(); 
     Array.Reverse(arr); 
     return new Stack<T>(arr); 
    } 

    public static Stack<T> Clone4<T>(this Stack<T> original) 
    { 
     var arr = new T[original.Count]; 
     original.CopyTo(arr, 0); 
     Array.Reverse(arr); 
     return new Stack<T>(arr); 
    } 
} 

Los resultados son:

• Clone1: 318,3766 ms
• Clone2: 269,2407 ms
• Clone3: 50,6025 ms
• Clone4: 37,5233 ms - el ganador

Como nosotros puede ver, el enfoque que usa El método CopyTo es 8 veces más rápido y, al mismo tiempo, la implementación es bastante simple y directa. Por otra parte, hice una búsqueda rápida en un valor máximo de tamaño de la pila: Clone3 y Clone4 pruebas trabajaron para grandes tamaños de pila antes de OutOfMemoryException ocurre:

• Clone1: 67108765 elementos
• Clone2: 67108765 elementos
• Clone3: 134218140 elementos
• Clone4: 134218140 elementos

Los resultados anteriores para Clone1 y Clone2 son más pequeños debido a las colecciones adicionales que eran explícitamente/consumo de memoria definido implícitamente y por lo tanto afectada. Por lo tanto, Clone3 y Clone4 enfoques permiten clonar una instancia de pila más rápido y con menos asignaciones de memoria. Puede obtener resultados aún mejores utilizando Reflection, pero es una historia diferente :)

El listado completo del programa se puede encontrar here.