C# sao chép ngăn xếp

Question

Tôi có vài ngăn xếp trong mã của tôi mà tôi sử dụng để theo dõi vị trí hợp lý của mình. Vào những thời điểm nhất định, tôi cần phải sao chép các ngăn xếp, nhưng tôi dường như không thể sao chép chúng theo cách như vậy mà nó giữ nguyên thứ tự. Tôi chỉ cần nhân đôi nông (tài liệu tham khảo, không phải đối tượng).

Cách thích hợp để làm điều đó là gì? Hoặc tôi nên sử dụng một số loại ngăn xếp khác?

LƯU Ý: Tôi thấy bài đăng này Stack Clone Problem: .NET Bug or Expected Behaviour?, nhưng không chắc chắn cách thiết lập phương pháp sao chép cho lớp Ngăn xếp.

Chú ý # 2: Tôi sử dụng System.Collection.Generic.Stack

Answer 1

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

Bạn có thể viết này như là một phương pháp khuyến nông như

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

này là cần thiết vì các nhà xây dựng Stack<T> rằng chúng ta là sử dụng ở đây là Stack<T>(IEnumerable<T> source) và tất nhiên khi bạn lặp qua triển khai IEnumerable<T> cho một Stack<T> nó sẽ liên tục bật các mục từ ngăn xếp, do đó cho chúng ăn theo thứ tự mà bạn kiến chúng để đi vào ngăn xếp mới. Do đó, thực hiện quá trình này hai lần sẽ dẫn đến việc ngăn xếp nằm đúng thứ tự.

Hoặc:

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

Một lần nữa, chúng tôi phải đi bộ ngăn xếp theo thứ tự ngược lại từ đầu ra từ iterating trên stack.

Tôi nghi ngờ có sự khác biệt về hiệu suất giữa hai phương pháp này.

Answer 2

Dưới đây là một cách dễ dàng, sử dụng LINQ:

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

Bạn có thể tạo ra một phương pháp khuyến nông để làm điều này dễ dàng hơn:

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

Cách sử dụng:

var clone = originalStack.Clone(); 

Answer 3

Nếu bạn don' t cần một số thực tế Stack`1, nhưng chỉ muốn một bản sao nhanh của số hiện có Stack`1 mà y Bạn có thể đi theo thứ tự mà trả về Pop, một tùy chọn khác là sao chép số Stack`1 vào một số Queue`1. Sau đó, các phần tử sẽ là Dequeue theo cùng thứ tự mà chúng sẽ là Pop từ gốc 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 

Answer 4

Đối với những người chăm sóc hiệu suất ..Có một vài cách khác làm thế nào để lặp qua các đống thành viên ban đầu mà không tổn thất lớn trong việc thực hiện:

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

Tôi đã viết một chương trình thô (liên kết sẽ được cung cấp vào cuối bài viết) để đo hiệu suất và bổ sung thêm hai thử nghiệm cho việc triển khai đã đề nghị (xem Clone1 và Clone2), và hai bài kiểm tra cho ToArray và CopyTo cách tiếp cận (xem Clone3 và Clone4, cả trong số họ sử dụng hiệu quả hơn Array.Reverse phương pháp).

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

Kết quả là:

• Clone1: 318,3766 ms
• Clone2: 269,2407 ms
• Clone3: 50,6025 ms
• Clone4: 37,5233 ms - người chiến thắng

Như chúng tôi có thể thấy, cách tiếp cận sử dụng phương pháp CopyTo nhanh hơn 8 lần và đồng thời việc triển khai khá đơn giản và dễ hiểu. Hơn nữa, tôi đã làm một nghiên cứu nhanh chóng trên một giá trị tối đa của stack kích thước: Clone3 và Clone4 xét nghiệm làm việc cho các kích cỡ chồng lớn hơn trước OutOfMemoryException xảy ra:

• Clone1: 67.108.765 yếu tố
• Clone2: 67.108.765 yếu tố
• Clone3: 134.218.140 yếu tố
• Clone4: 134.218.140 yếu tố

Kết quả trên cho Clone1 và Clone2 nhỏ do các bộ sưu tập bổ sung mà là rõ ràng/ngầm được xác định và do đó ảnh hưởng tiêu thụ bộ nhớ. Do đó, Clone3 và Clone4 phương pháp tiếp cận cho phép sao chép một thể hiện ngăn xếp nhanh hơn và với ít phân bổ bộ nhớ hơn. Bạn có thể đạt được kết quả tốt hơn bằng cách sử dụng Reflection, nhưng đó là một câu chuyện khác nhau :)

Danh sách đầy đủ chương trình có thể được tìm thấy here.