¿Ves algún problema con esta implementación C# de una pila?

Question

Escribí esto rápidamente en las condiciones de la entrevista, quería publicarlo en la comunidad para ver si había una manera mejor/más rápida/más limpia de hacerlo. ¿Cómo podría esto optimizarse?

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

Simplemente puede usar una matriz. Los métodos de matriz .NET son realmente rápidos.

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

creo que el método Clear() podría ser acelerado significativamente cambiándola a top = null;. Toda la pila será recogida de basura, y no se requiere bucle mientras tanto.

Answer 3

Puede ser preferible utilizar la matriz dinámica como la estructura de datos en lugar de una lista vinculada. La matriz tendrá una mejor localidad de referencia porque los elementos están uno al lado del otro. Una pila no necesita capacidad para eliminar elementos en el medio, empalmes, etc. por lo que una matriz es suficiente.