Voir des problèmes avec cette implémentation C# d'une pile?

Question

Je l'ai écrit rapidement dans des conditions d'entrevue, je voulais l'afficher dans la communauté pour éventuellement voir s'il y avait une façon meilleure/plus rapide/plus propre de s'y prendre. Comment cela pourrait-il être optimisé?

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

Vous pouvez simplement utiliser un tableau. Les méthodes de tableau .NET sont vraiment rapides.

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

Je pense que la méthode Clear() pourrait être accéléré de manière significative en changeant à top = null;. La pile entière sera collectée et aucune boucle requise entre-temps.

Answer 3

est peut-être préférable d'utiliser un tableau dynamique que la structure de données au lieu d'une liste chaînée. Le tableau aura une meilleure localisation de référence car les éléments sont côte à côte. Une pile n'a pas besoin d'une capacité pour supprimer des éléments au milieu, épissage, etc, donc un tableau suffit.