Alternativa para la pila

Question

Estoy trabajando en el entorno .Net usando C#. Necesito alguna alternativa para la estructura de datos Stack. Algún tipo de pila atada. La cantidad de elementos en la colección no debe exceder un número fijo determinado. Y, si se logra ese número y se empuja un nuevo elemento, debe eliminarse el elemento más antiguo. Necesito esto para almacenar comandos para las estrategias Deshacer/Rehacer.

Answer 1

Johnny Coder tiene una aplicación aquí: http://johnnycoder.com/blog/2008/01/07/undo-functionality-with-a-limited-stack/

Answer 2

A circular buffer debería hacer el trabajo; lo suficientemente fácil como para envolver una lista o matriz, pero nada incorporado en AFAIK.

Answer 3

No hay ninguna clase de orden interna para esto en marco. (no esperamos eliminar datos automáticamente). Pero puede muy bien Extender la clase Stack y Anular push/pop y otros métodos para satisfacer sus necesidades.

Answer 4

.Net es bastante deficiente en el tipo de colecciones. Encontrará una biblioteca de colecciones here. Use CircularQueue.

Answer 5

Esta es una implementación de una pila con una capacidad restringida. Después de alcanzar la capacidad dada, los artículos del fondo de la pila más allá de la capacidad se descartan. Es posible iterar a través de los objetos contenidos y establecer el índice en una posición específica (como un rebobinado) para descartar múltiples entradas a la vez cuando se empuja un nuevo elemento a la pila.

Esta es una implementación propia con algunos extras que le impide manejar más de una lista si necesita volver al historial y reenviarla (está incorporada).

public class DiscardingStack<TObject> : IEnumerable<TObject> 
{ 
    private readonly int capacity; 

    private readonly List<TObject> items; 

    private int index = -1; 

    public DiscardingStack(int capacity) 
    { 
     this.capacity = capacity; 
     items = new List<TObject>(capacity); 
    } 

    public DiscardingStack(int capacity, IEnumerable<TObject> collection) 
     : this(capacity) 
    { 
     foreach (var o in collection) 
     { 
      Push(o); 
     } 
    } 

    public DiscardingStack(ICollection<TObject> collection) 
     : this(collection.Count, collection) 
    { 
    } 

    public void Clear() 
    { 
     if (items.Count >= 0) 
     { 
      items.Clear(); 
      index = items.Count - 1; 
     } 
    } 

    public int Index 
    { 
     get { return index; } 
     set 
     { 
      if (index >= 0 && index < items.Count) 
      { 
       index = value; 
      } 
      else throw new InvalidOperationException(); 
     } 
    } 

    public int Count 
    { 
     get { return items.Count; } 
    } 

    public TObject Current 
    { 
     get { return items[index]; } 
     set { index = items.IndexOf(value); } 
    } 

    public int Capacity 
    { 
     get { return capacity; } 
    } 

    public TObject Pop() 
    { 
     if (items.Count <= 0) 
      throw new InvalidOperationException(); 

     var i = items.Count - 1; 
     var removed = items[i]; 
     items.RemoveAt(i); 

     if (index > i) 
      index = i; 

     return removed; 
    } 

    public void Push(TObject item) 
    { 
     if (index == capacity - 1) 
     { 
      items.RemoveAt(0); 
      index--; 
     } 
     else if (index < items.Count - 1) 
     { 
      var removeAt = index + 1; 
      var removeCount = items.Count - removeAt; 
      items.RemoveRange(removeAt, removeCount); 
     } 

     items.Add(item); 

     index = items.Count - 1; 
    } 

    public TObject Peek() 
    { 
     return items[items.Count-1]; 
    } 

    public TObject this[int i] 
    { 
     get { return items[i]; } 
    } 

    public IEnumerator<TObject> GetEnumerator() 
    { 
     return items.GetEnumerator(); 
    } 

    IEnumerator IEnumerable.GetEnumerator() 
    { 
     return GetEnumerator(); 
    } 
} 

De todos modos, la construcción de una pila que descarta los elementos cuando se alcanza debe ser implementado usando un LinkedList la capacidad máxima (como se sugirió anteriormente) si la lista es enorme (evita la copia). Entonces, la idea LinkedList podría ser mejor en ese caso en lugar de envolver una lista si el máximo del buffer es de alto valor.

También recomendaría empaquetar Push(), Pop(), etc. en una interfaz (por ejemplo, IStack). Lamentablemente, no hay una interfaz IStack predefinida en .Net (afaik).