替代堆棧

Question

我正在使用C＃在.Net環境中工作。我需要一些替代Stack數據結構。某種綁定的堆棧。集合中的元素數量不應超過某個固定的指定數量。而且，如果達到了這個數字並推出新元素，則必須刪除大多數舊元素。我需要這個用於存儲撤消/重做策略的命令。

Answer 1

約翰尼編碼器在這裏有一個實現：http://johnnycoder.com/blog/2008/01/07/undo-functionality-with-a-limited-stack/

Answer 2

A circular buffer應該做的工作;很容易包裝一個列表或數組，但沒有內置AFAIK。

Answer 3

有一個在框架對此沒有內置類。 （我們不希望自動刪除數據）。但你可以很好地延伸堆棧類和覆蓋推/流行和其他方法，以滿足您的需求。

Answer 4

.net在收集類型上相當不足。你會找到一個收藏庫here。使用 CircularQueue。

Answer 5

這是一個具有受限容量的堆棧的實現。 達到給定容量後，超出容量的堆棧底部項目將被丟棄。將新項目推送到堆棧時，可以遍歷包含的對象並將索引設置爲特定的位置（如倒回）以一次丟棄多個條目。

這是一個自己的實現，有些好東西可以防止您處理多個列表，如果您需要返回歷史記錄並再次向前（正在建立）。

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

總之，建設一個堆棧丟棄時達到最大容量應在LinkedList實現的元素（如上面所建議的），如果你的名單是巨大的（避免複製）。所以在這種情況下LinkedList的想法可能會更好，而不是包裝一個List，如果緩衝區最大值是一個高值。

我也建議將Push（），Pop（）等打包到一個接口（例如IStack）中。可悲的是，在.Net（afaik）中沒有預定義的IStack接口。