С# клонировать стек

У меня в моем коде несколько стеков, которые я использую для отслеживания моего логического местоположения. В определенные моменты мне нужно дублировать стеки, но я не могу клонировать их таким образом, чтобы сохранить порядок. Мне нужно только мелкое дублирование (ссылки, а не объект).

Каким будет правильный способ? Или я должен использовать несколько других стеков?

ПРИМЕЧАНИЕ. Я видел эту запись Проблема клонирования стека: ошибка .NET или ожидаемое поведение?, но не знаю, как настроить метод клонирования для класса Stack.

ПРИМЕЧАНИЕ # 2: Я использую System.Collection.Generic.Stack

Ответ 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) и, конечно, когда вы выполняете итерацию по реализации IEnumerable<T> для Stack<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());
}

Опять же, мы должны пройти стек в обратном порядке от выхода из итерации по стеку.

Я сомневаюсь, что существует разница в производительности между этими двумя методами.

Ответ 2

Здесь один простой способ, используя 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();

Ответ 3

Для тех, кто заботится о производительности. Есть несколько других способов, как итерации через исходные элементы стека без больших потерь в производительности:

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 ms
Clone3: 50,6025 мс
Clone4: 37,5233 мс - победитель

Как мы видим, подход с использованием метода CopyTo в 8 раз быстрее, и в то же время реализация довольно проста и понятна. Кроме того, я сделал быстрое исследование максимального значения размера стека: тесты Clone3 и Clone4 работали для большего размера стека до появления OutOfMemoryException:

Clone1: 67108765 элементы
Clone2: 67108765 элементы
Clone3: 134218140 элементов
Элементы Clone4: 134218140

Результаты выше для Clone1 и Clone2 меньше из-за дополнительных коллекций, которые были явно/неявно определены и, следовательно, повлияли на потребление памяти. Таким образом, подходы Clone3 и Clone4 позволяют клонировать экземпляр стека быстрее и с меньшим распределением памяти. Вы можете получить еще лучшие результаты, используя Reflection, но это другая история:)

Полный список программ можно найти здесь.

Ответ 4

Если вам не нужно фактическое Stack`1, а просто хотите быстро копию существующего Stack`1, что вы можете идти в том же порядке, что Pop возвращается, другой вариант, чтобы дублировать Stack`1 в Queue`1. Элементы будут тогда Dequeue в том же порядке, что они будут Pop от оригинала 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