如何克隆 Stack

Question

我的代码中有几个堆栈用于跟踪我的逻辑位置。在某些时候，我需要复制堆栈，但我似乎无法以保留顺序的方式克隆它们。我只需要浅层复制（引用，而不是对象）。

正确的方法是什么？或者我应该使用其他类型的堆栈？

我看到这篇文章 堆栈克隆问题：.NET Bug 或预期行为？< /a>，但不确定如何为 Stack 类设置克隆方法。

我使用 System.Collection.Generic .Stack。

Answer 1

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

您可以将其编写为扩展方法，因为

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

这是必要的，因为我们在这里使用的 Stack 构造函数是 Stack(IEnumerablesource)当然，当您迭代时Stack 的 IEnumerable实现，它将重复地从堆栈中弹出项目，从而以与您希望的顺序相反的顺序将它们提供给您进入新堆栈。因此，执行此过程两次将导致堆栈的顺序正确。

或者：

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

同样，我们必须按照与迭代堆栈的输出相反的顺序遍历堆栈。

我怀疑这两种方法之间是否存在性能差异。

Answer 2

对于那些关心性能的人来说..还有其他一些方法可以在不造成性能损失的情况下迭代原始堆栈成员：

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

我编写了一个粗略的程序（链接将在帖子末尾提供）来测量性能并为已建议的实现添加了两个测试（请参阅Clone1和Clone2），以及针对ToArray和CopyTo 方法（参见Clone3和Clone4，它们都使用更高效的Array.Reverse方法）。

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

结果是：

• Clone1：318,3766 ms
• Clone2：269,2407 ms
• Clone3：50,6025 ms
• Clone4：37,5233 ms - 获胜者

正如我们所看到的，使用 CopyTo 的方法 方法速度快了 8 倍，同时实现也非常简单明了。此外，我对堆栈大小的最大值进行了快速研究：在发生 OutOfMemoryException 之前，Clone3 和 Clone4 测试适用于更大的堆栈大小：

• Clone1 ：67108765个元素
• 克隆2：67108765个元素
• 克隆3：134218140个元素
• 克隆4： 134218140 个元素

上述 Clone1 和 Clone2 的结果较小，因为显式/隐式定义了额外的集合，因此影响了内存消耗。因此，Clone3 和 Clone4 方法允许更快地克隆堆栈实例并且占用更少的内存分配。使用反射可以获得更好的结果，但这是一个不同的故事:)

完整的程序列表可以在这里找到< /a>.

Answer 3

这是一种简单的方法，使用 LINQ：

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

您可以创建一个扩展方法来简化此操作：

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

用法：

var clone = originalStack.Clone();

Answer 4

如果您不需要实际的 Stack`1，而只是想要现有 Stack`1 的快速副本，您可以按照与 相同的顺序遍历Pop 返回，另一个选择是将 Stack`1 复制到 Queue`1 中。然后，这些元素将以与从原始 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());
  }
}

输出：

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

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