如何克隆一个 Stack<T>

Question

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

什么是正确的方法？还是应该使用其他类型的栈？

我看到了这篇文章Stack Clone Problem: .NET Bug or Expected Behaviour?，但不确定如何为Stack<T>类设置克隆方法。

我使用System.Collection.Generic.Stack<T>。

- SpaceBear

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<T> 构造函数是 Stack<T>(IEnumerable<T> source)。当您迭代 Stack<T> 的 IEnumerable<T> 实现时，它将重复从堆栈中弹出项目，因此反转了它们进入新堆栈所需的顺序。因此，执行两次此过程将使堆栈处于正确的顺序。

或者：

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

我们需要再次按照从堆栈迭代输出的反向顺序遍历堆栈。

我怀疑这两种方法之间没有性能差异。

- jason

---

遗憾的是，奇怪的是，这不能保持顺序 :( （我假设堆栈的双重初始化是打字错误还是一个技巧？） - SpaceBear

它确实保留了顺序。双重实例化是一种技巧，可以使顺序得以保留。 - jason

@Angrius：需要“双重初始化”，因为每个都会反转顺序。如果你反转两次，就会得到原始顺序。 - Gabe

@Angrius：此外，它不保留顺序并不奇怪。请查看我解释其原因的说明。对于Stack<T>的IEnumerable<T>实现是完全合理的；如果Stack<T>的IEnumerable<T>实现除了反复弹出和产生值以外做任何其他事情，我会感到困惑。对于Stack<T>(IEnumerable<T> source)的构造函数也是完全合理的；如果这个Stack<T>的构造函数除了从source中取值并推入栈中之外做任何其他事情，我会感到困惑。在我看来，这其中没有什么奇怪的地方。 - jason

尽管栈构造函数按顺序推入事物很合理，但在“现实生活”中，通过获取项目列表并将其最后一个项目作为第一个推入堆栈是非常普遍的。例如，在C和衍生语言中的可选参数通常从右到左推入，以便按顺序读取它们。 - supercat

我实际上需要反转项目，所以感谢您解释双重实例化背后的原因！ - lordcheeto

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毫秒
• Clone2: 269,2407毫秒
• Clone3: 50,6025毫秒
• Clone4：37,5233毫秒-获胜者

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

• Clone1：67108765个元素
• Clone2：67108765个元素
• Clone3：134218140个元素
• Clone4：134218140个元素

由于显式/隐式定义的额外集合影响了内存消耗，因此上述Clone1和Clone2的结果较小。因此，Clone3和Clone4的方法允许更快地克隆堆栈实例，并减少内存分配。您甚至可以使用Reflection获得更好的结果，但这是另一回事 :)

完整的程序清单可以在此处找到。

- AndreyCh

---

使用BenchmarkDotNet证明结果。从CPU和内存的角度来看，Clone4仍然是最有效的方法。

1. Clone1（703.87毫秒，128 MB）
2. Clone2（535.94毫秒，128 MB）
3. Clone3（71.60毫秒，64 MB）
4. Clone4（56.20毫秒，64 MB）

- AndreyCh

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

- Diego Mijelshon

---

对我有用。这也保留了原始堆栈。 - MStodd

@Diego Mijelshon: 不，它不会！它从顶部弹出并重复到堆栈的底部。 - jason

@Jason，你说得对，我误解了我的测试结果。这是Stack构造函数在克隆方面出了一些“问题”。 - Diego Mijelshon

Answer 4

如果您不需要实际的Stack`1，但只想快速复制现有的Stack`1，以便您可以按照Pop返回的顺序遍历它，另一个选项是将Stack`1复制到Queue`1中。元素将按照与原始Stack`1相同的顺序Dequeue，这些元素将按照它们从原始Stack`1中Pop的顺序Dequeue。

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

输出：

栈：
  最后压入，先弹出
  中间位置
  最先压入，最后弹出
队列：
  最后压入，先弹出
  中间位置
  最先压入，最后弹出

- Jonathan Gilbert