我需要什么数据结构或者如何实现“后进先出式”队列？

Question

我正在寻找一种行为如下的数据结构：

1. 后进先出
2. 迭代时，第一个项目是最后出现的项目（LCFS - 后到先服务）
3. 当达到最大容量时，需要删除“最旧”的项目

听起来 aQueue可以解决问题，但该结构是 FIFO。听起来我需要一个类似 LIFO 的队列。

我应该使用什么想法？

Answer 1

基础 .NET 库中有Stack，但没有最后一个要求。我相信没有这样的现有结构，所以你必须自己实现它。

但这应该不是问题。只需创建一个链接列表，您可以在其中添加和删除一侧，并在项目数量超过给定大小时从另一侧删除。您可以通过使用带有开始结束指针的数组来优化它，但是您必须定期重新排列数组，以免空间不足。循环版本实际上比重新排列效果更好。

我用循环版本做了一些快速的修改。我确信您可以自己添加接口。

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