c# - 堆栈的替代方案

Question

我正在使用 C# 在 .Net 环境中工作。我需要一些 Stack 数据结构的替代方案。某种绑定堆栈。集合中元素的数量不应超过某个固定的指定数量。并且，如果达到该数量并推送新元素，则必须删除大多数旧元素。我需要这个来存储撤消/重做策略的命令。

Answer 1

循环缓冲区应该可以完成这项工作；很容易包装一个列表或数组，但在 AFAIK 中没有内置任何东西。

Answer 2

Johnny Coder 在这里有一个实现：http: //johnnycoder.com/blog/2008/01/07/undo-functionality-with-a-limited-stack/

Answer 3

这是容量受限的堆栈的实现。达到给定容量后，超出容量的堆栈底部项目将被丢弃。可以遍历包含的对象并将索引设置为特定位置（如倒带），以便在将新项目推入堆栈时一次丢弃多个条目。

这是一个自己的实现，带有一些好东西，如果您需要返回历史并再次转发（内置），可以防止您处理多个列表。

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 接口。

Answer 4

.Net 在集合类型方面相当缺乏。你会在这里找到一个收藏库。使用循环队列。

Answer 5

在 Framework 中没有用于此的内置类。（我们不希望自动删除数据）。但是您可以很好地扩展Stack 类并覆盖 Push/Pop和其他方法以满足您的需求。