Xem bất kỳ vấn đề nào với việc triển khai C# này của ngăn xếp?

Question

Tôi đã viết điều này một cách nhanh chóng trong các điều kiện phỏng vấn, tôi muốn đăng nó lên cộng đồng để có thể xem liệu có cách nào tốt hơn/nhanh hơn/sạch hơn để thực hiện điều đó hay không. Làm thế nào điều này có thể được tối ưu hóa?

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Stack 
{ 
    class StackElement<T> 
    { 
     public T Data { get; set; } 
     public StackElement<T> Below { get; set; } 
     public StackElement(T data) 
     { 
      Data = data; 
     } 
    } 

    public class Stack<T> 
    { 
     private StackElement<T> top; 

     public void Push(T item)    
     { 
      StackElement<T> temp; 
      if (top == null) 
      { 
       top = new StackElement<T>(item); 
      } 
      else 
      { 
       temp = top; 
       top = new StackElement<T>(item); 
       top.Below = temp;     
      } 
     } 

     public T Pop() 
     { 
      if (top == null) 
      { 
       throw new Exception("Sorry, nothing on the stack"); 
      } 
      else 
      { 
       T temp = top.Data;     
       top = top.Below; 
       return temp; 
      }   
     } 

     public void Clear() 
     { 
      while (top != null) 
       Pop(); 
     } 

    } 


    class TestProgram 
    { 
     static void Main(string[] args) 
     { 
      Test1(); 
      Test2(); 
      Test3(); 
     } 

     private static void Test1() 
     { 
      Stack<string> myStack = new Stack<string>(); 
      myStack.Push("joe"); 
      myStack.Push("mike"); 
      myStack.Push("adam"); 

      if (myStack.Pop() != "adam") { throw new Exception("fail"); } 
      if (myStack.Pop() != "mike") { throw new Exception("fail"); } 
      if (myStack.Pop() != "joe") { throw new Exception("fail"); } 

     } 

     private static void Test3() 
     { 

      Stack<string> myStack = new Stack<string>(); 
      myStack.Push("joe"); 
      myStack.Push("mike"); 
      myStack.Push("adam"); 
      myStack.Clear(); 
      try 
      { 
       myStack.Pop(); 

      } 
      catch (Exception ex) 
      { 
       return; 
      } 

      throw new Exception("fail"); 
     } 

     private static void Test2() 
     { 
      Stack<string> myStack = new Stack<string>(); 
      myStack.Push("joe"); 
      myStack.Push("mike"); 
      myStack.Push("adam"); 

      if (myStack.Pop() != "adam") { throw new Exception("fail"); } 
      myStack.Push("alien"); 
      myStack.Push("nation"); 
      if (myStack.Pop() != "nation") { throw new Exception("fail"); } 
      if (myStack.Pop() != "alien") { throw new Exception("fail"); } 

     } 

    } 
} 

Answer 1

Bạn chỉ cần sử dụng một mảng. Các phương thức mảng .NET thực sự nhanh.

public class Stack<T> 
{ 
    private const int _defaultSize = 4; 
    private const int _growthMultiplier = 2; 

    private T[] _elements; 
    private int _index; 
    private int _limit; 


    public Stack() 
    { 
     _elements = new T[_defaultSize]; 
     _index = -1; 
     _limit = _elements.Length - 1; 
    } 


    public void Push(T item) 
    { 
     if (_index == _limit) 
     { 
      var temp = _elements; 
      _elements = new T[_elements.Length * _growthMultiplier]; 
      _limit = _elements.Length - 1; 
      Array.Copy(temp, _elements, temp.Length); 
     } 
     _elements[++_index] = item; 
    } 

    public T Pop() 
    { 
     if (_index < 0) 
      throw new InvalidOperationException(); 

     var item = _elements[_index]; 
     _elements[_index--] = default(T); 
     return item; 
    } 

    public void Clear() 
    { 
     _index = -1; 
     Array.Clear(_elements, 0, _elements.Length); 
    } 
} 

Answer 2

Tôi nghĩ phương thức Clear() có thể tăng tốc đáng kể bằng cách thay đổi thành top = null;. Toàn bộ ngăn xếp sẽ được thu thập rác và không yêu cầu vòng lặp trong thời gian đó.

Answer 3

Có thể thích hợp hơn khi sử dụng mảng động làm cấu trúc dữ liệu thay vì danh sách được liên kết. Mảng sẽ có vị trí tham chiếu tốt hơn vì các phần tử nằm cạnh nhau. Một ngăn xếp không cần khả năng xóa các phần tử ở giữa, nối vv sao cho một mảng đủ.