哪种数据结构允许从两侧添加，但强制执行容量？

Question

我需要一个具有 capacity，但也允许 adding an item from either the front or the back 的数据结构。每次添加一个项目时，必须从另一端删除一个项目。我的第一个想法是，这听起来与 Deque 非常相似。

是否有提供此功能的现有数据结构，还是我必须自己创建它？如果确实存在，does the .Net library have an implementation?

谢谢

Answer 1

我建议您使用 LinkedList，它可以提供您需要的所有功能。有 AddFirst 和 AddLast 方法可以让您在前面或后面添加项目，还有 RemoveFirst 和 RemoveLast 方法可以让您从前面和后面删除。

当然，还有一个 Count 属性告诉您列表中有多少项，因此您可以强制执行您的容量要求。

Answer 2

我认为最好的选择是使用 array of T for the backing structure，并使用 reference Front and a reference Back 来表示结构的虚拟开始和结束。我还将存储一个方向枚举，它将有效地指示结构面向哪个方向（最后一次添加操作是在前面还是后面，或者如果没有执行任何添加操作，则为默认值）。 This way, I can also implement an indexer with O(1) complexity，而不是迭代集合。

感谢您的所有回复。出于某种原因，我认为我需要在支持结构中移动数据。我没有意识到这个选项在 C# 中是可行的。

Answer 3

未测试，但我认为类似这样的方法可行

public class Stack<T>
{
    private T[] arr;
    readonly int m_Size;
    int m_StackPointer = 0;
    public T this[int i]
    {
        get
        {
            if (i >= m_Size)
                throw new IndexOutOfRangeException();
            int pointer = i + m_StackPointer;
            if (pointer >= (m_Size)) pointer -= m_Size;
            return arr[pointer];
        }
    }
    public void AddStart(T addItem)
    {
        m_StackPointer--;
        if (m_StackPointer < 0) m_StackPointer = m_Size - 1;
        arr[m_StackPointer] = addItem;
    }
    public void AddEnd(T addItem)
    {
        arr[m_StackPointer] = addItem;
        m_StackPointer++;
        if (m_StackPointer >= m_Size) m_StackPointer = 0;
    }
    public Stack()
        : this(100)
    { }
    public Stack(int size)
    {
        m_Size = size;
        arr = new T[size];
    }
}

哪种数据结构允许从两侧添加，但强制执行容量？

Which data structure allows adding from both sides, but enforces a capacity?

.net

c#

algorithm

data-structures