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

Question

我正在寻找一个数据结构，其行为如下：

1. 后进先出
2. 在迭代时，第一个项目是最后进入的项目（LCFS-后来者优先）
3. 当达到最大容量时，需删除“最老”的项目

听起来像是Queue可以胜任，但该结构是FIFO。看起来我需要一个类似于LIFO的队列。

有什么建议？

- Kees C. Bakker

---

你描述的更像是一个栈而不是一个队列... - Thomas Levesque

你正在寻找一个堆栈吗？虽然标准的.NET堆栈不会丢弃旧的项目。 - Joe

你可以使用符合你要求的栈。 - Shyam sundar shah

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

- Euphoric

---

栈有迭代器吗？ - Kees C. Bakker

@KeesC.Bakker，是的，它会按照您指定的顺序（LCFS）枚举。 - Thomas Levesque

哇.. 神奇 :). 我唯一需要的是增加容量 :P - Kees C. Bakker

@KeesC.Bakker 容量增加？比如在创建堆栈后保留项目的情况下增加容量？是的，这可能会稍微困难一些。 - Euphoric

在你的GetEnumerator()中，如果begin == 0，那么i不会等于-1吗？这样在尝试以-1为索引访问“array”时就会出错了吧？ - h4le5torm

Answer 2

使用LinkedList<T>：

public class LifoBuffer<T> : LinkedList<T>
{
    private int capacity;

    public LifoBuffer(int capacity)
    {
        this.capacity = capacity;   
    }

    public void Add(T item)
    {
        if (Count == capacity) RemoveLast();
        AddFirst(item);
    }
}

void Main()
{
    var lifoBuffer = new LifoBuffer<int>(3);
    lifoBuffer.Add(1);
    lifoBuffer.Add(2);
    lifoBuffer.Add(3);
    lifoBuffer.Add(4);
    lifoBuffer.Add(5);
    foreach (var item in lifoBuffer) Console.WriteLine(item); // outputs: 5, 4, 3
}

- Brandon

Answer 3

.Net有一个后进先出的“队列”结构，称为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];
    }
}

我会把额外的接口实现留给你，但是你已经有了想法。

- spender

---

这是否满足第三个要求？在SO上，仅提供链接的答案是否可接受？ - Jon

好的，它没有满足第三点，但我相信对于提问者来说，这是一个有用的信息，即LIFO“队列”被称为堆栈。 - spender

@spender：还有其他人认为这是有用的信息。他们留下了评论。 - Jon

嗯...看起来不错...但是当堆栈“满”时，它停止推送其内容...应该在堆栈“满”时删除“底部”的项目。 - Kees C. Bakker

@KeesC.Bakker 嗯...我开始觉得循环缓冲区可能更适合你的情况。 - spender

Answer 4

可以使用类似这样的代码。如果读者需要，实现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];
        }
    }

- SergeyS

Answer 5

它就像是一个带有定义容量的循环后进先出。

- Mihai8

---

我们有现成的结构体可用吗，还是我需要自己创建？ - Kees C. Bakker

Answer 6

优秀的后进先出数据结构是栈（Stack）。这将满足第一和第二要求。然而，这并不满足第三个要求。为了满足第三个要求，最好使用队列（Queue），虽然它默认是一个FIFO数据类型。我认为没有现有的数据结构符合您的要求，这意味着您需要自己构建它。

- Erik Schierboom

Answer 7

我建议使用 Stack 类。

MSDN Stack Class

- csteinmueller