How to clone a Stack<T>

I have few stacks in my code that I use to keep track of my logical location. At certain times I need to duplicate the stacks, but I can't seem to clone them in such way that it preserves the order. I only need shallow duplication (references, not object).

What would be the proper way to do it? Or should I use some oth开发者_如何学运维er sort of stacks?

I saw this post Stack Clone Problem: .NET Bug or Expected Behaviour?, but not sure how to setup clone method for the Stack<T> class.

I use System.Collection.Generic.Stack<T>.

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

You can write this as an extension method as

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

This is necessary because the Stack<T> constructor that we are using here is Stack<T>(IEnumerable<T> source) and of course when you iterate over the IEnumerable<T> implementation for a Stack<T> it is going to repeatedly pop items from the stack thus feeding them to you in reverse of the order that you want them to go onto the new stack. Therefore, doing this process twice will result in the stack being in the correct order.

Alternatively:

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());
}

Again, we have to walk the stack in the reverse order from the output from iterating over the stack.

I doubt there is a performance difference between these two methods.

For those who take care of performance.. There are a few other ways how to iterate through the original stack members without big losses in the performance:

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

I wrote a rough program (the link will be provided at the end of the post) to measure performance and added two tests for the already suggested implementations (see Clone1 and Clone2), and two tests for ToArray and CopyTo approaches (see Clone3 and Clone4, both of them use more efficient Array.Reverse method).

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);
    }
}

The results are:

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

As we can see, the approach using CopyTo method is 8 times faster and at the same time the implementation is pretty simple and straightforward. Moreover, I did a quick research on a maximum value of stack size: Clone3 and Clone4 tests worked for bigger stack sizes before OutOfMemoryException occurs:

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

The results above for Clone1 and Clone2 are smaller due to additional collections that were explicitly/implicitly defined and therefore affected memory consumption. Thus, Clone3 and Clone4 approaches allow to clone a stack instance faster and with less memory allocations. You can gain even better results using Reflection, but it's a different story :)

The full program listing can be found here.

Here's one easy way, using LINQ:

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

You could create an extension method to make this easier:

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

Usage:

var clone = originalStack.Clone();

If you don't need an actual Stack`1, but just want a quick copy of an existing Stack`1 that you can walk in the same order that Pop returns, another option is to duplicate the Stack`1 into a Queue`1. The elements will then Dequeue in the same order that they'll Pop from the 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());
  }
}

Output:

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

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