我需要什麼數據結構或如何實現「類LIFO」隊列？

Question

我在尋找一種數據結構，行爲方式是這樣的：

1. 後進先出
2. 迭代後的第一項是最後一次在該項目（LCFS - 最後先到先得）
3. 當達到最大容量，最古老的「項目（S）需要（S）被丟棄

這聽起來像一個Queue會做的伎倆，但結構是FIFO。聽起來像我需要一個類似LIFO的隊列。

任何想法我應該使用？

Answer 1

有Stack在基地.NET庫，但沒有最後的要求。我相信現在沒有這樣的結構，所以你必須自己實現它。

但這應該不成問題。只需創建一個鏈接列表，您可以在一側添加和刪除鏈接列表，並在項目數量超出給定大小時從其他鏈接列表中刪除。您可以通過使用帶有開始結束指針的數組來優化它，但是您必須定期重新排列數組，以免空間用完。循環版實際上可能比重新排列更好。

我做了一些循環版本的快速入侵。我相信你可以自己添加接口。

public class DroppingStack<T> : IEnumerable<T> 
{ 
    T[] array; 
    int cap; 
    int begin; 
    int end; 
    public DroppingStack (int capacity) 
    { 
     cap = capacity+1; 
     array = new T[cap]; 
     begin = 0; 
     end = 0; 
    } 

    public T pop() 
    { 
     if (begin == end) throw new Exception("No item"); 
     begin--; 
     if (begin < 0) 
      begin += cap; 
     return array[begin]; 
    } 

    public void push(T value) 
    { 
     array[begin] = value; 
     begin = (begin+1)%cap; 
     if (begin == end) 
      end = (end + 1) % cap; 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     int i = begin-1; 
     while (i != end-1) 
     { 
      yield return array[i]; 
      i--; 
      if (i < 0) 
       i += cap; 
     } 
    } 

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    { 
     return this.GetEnumerator(); 
    } 
} 

Answer 2

它就像一個具有定義容量的循環LIFO。

Answer 3

.Net有一個名爲Stack<T>的LIFO「隊列」結構，雖然這不符合您的第三個約束（例如大小限制）。通過遏制來實現這一點並不困難。

但是，如果你想扔掉堆棧中最古老的物品，最好使用循環緩衝區。這可能是實現如下：

class OverflowingStack<T> 
{ 
    private T[] items; 
    private int currentIndex; 
    private int count; 

    public OverflowingStack(int size) 
    { 
     this.items = new T[size]; 
     this.currentIndex = 0; 
     this.count = 0; 
    } 
    public void Push(T item) 
    { 
     items[currentIndex] = item; 
     currentIndex++; 
     currentIndex %= items.Length; 
     count++; 
     count = count > items.Length ? items.Length : count; 

    } 
    public T Pop() 
    { 
     if (count == 0) throw new Exception("stack is empty"); 
     currentIndex--; 
     while (currentIndex < 0) {currentIndex += items.Length;} 
     count--; 
     return items[currentIndex]; 
    } 
} 

我會留下額外的接口實現給你，但你的想法。

Answer 4

我會建議使用Stack類

MSDN Stack Class

Answer 5

嗯示例性後進先出的數據結構是Stack。這將滿足第一個和第二個要求。但是，這不符合第三個要求。對於這一要求，你可能最好使用Queue，儘管這是默認的FIFO數據類型。我不相信現有的數據結構符合您的要求，這意味着您必須自己構建它。

Answer 6

就像這樣，隨意使用它。 IEnumerable的實現是讀者的練習（如果他需要的話）：

class CyclicStack<T> 
    { 
     private T[] stack; 
     private int capacity; 
     private int curIndex = 0; 

     public int Count { get; private set; } 
     public CyclicStack(int capacity) 
     { 
      this.capacity = capacity; 
      stack = new T[capacity]; 
      this.Count = 0; 
     } 
     public T this[int index] 
     { 
      get 
      { 
       if (index >= capacity) 
        throw new Exception("Index is out of bounds"); 
       return this.stack[(curIndex + index) % capacity]; 
      } 
     } 
     public void Push(T item) 
     { 
      curIndex = (curIndex + capacity - 1) % capacity; 
      stack[curIndex] = item; 
      this.Count++; 
     } 
     public T Pop() 
     { 
      if (this.Count == 0) 
       throw new Exception("Collection is empty"); 
      int oldIndex = curIndex; 
      curIndex = (curIndex + capacity + 1) % capacity; 
      this.Count--; 
      return stack[oldIndex]; 
     } 
    }