我需要什么数据结构或如何实现“类似LIFO的”队列？

Question

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

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

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

任何想法我应该使用什么？

Answer 1

基本.NET库中有Stack，但没有最后一个要求。而且我相信没有这样的现有结构，因此您必须自己实现。

但是那不应该是问题。只需创建一个链接列表，当项目数超过给定大小时，您可以从一侧添加和删除，从另一侧删除。您可以通过使用带有begin-end指针的数组来对其进行优化，但是随后您必须定期重新排列该数组，以免空间不足。循环版本实际上可能比重新排列更好。

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

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

示例性的后进先出数据结构是Stack。这将同时满足第一个和第二个要求。但是，这不能满足第三个要求。对于该要求，最好使用Stack，尽管默认情况下这是FIFO数据类型。我认为不存在符合您要求的现有数据结构，这意味着您必须自己构建它。

Answer 4

这样的事情，随时使用。 IEnumerable的实现是读者的一项练习（如果他需要的话）：

Queue

Answer 5

。Net具有一个称为

    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];
        }
    }

的LIFO“队列”结构，尽管这不能满足您的第三个约束（例如，尺寸受限制）。通过遏制实现这一目标并不难。

但是...如果要丢弃堆栈中最旧的项目，最好使用循环缓冲区。可以如下实现：

Stack<T>

我将其他接口实现留给您，但您明白了。

Answer 6

我建议使用Stack<T>类

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 7

使用Stack：

MSDN Stack Class