在.NET中如何限制Queue<T>的大小？

Question

我有一个Queue<T>对象，它的初始容量为2，但很明显这只是一个容量限制，当我增加项目时它会不断地扩展。是否已经有一个可以在达到限制时自动出队的对象，或者创建自己的派生类是最好的解决方案？

- tags2k

Answer 1

我已经做出了一个基本版本，虽然并不完美，但在更好的东西出现之前可以胜任工作。

public class LimitedQueue<T> : Queue<T>
{
    public int Limit { get; set; }

    public LimitedQueue(int limit) : base(limit)
    {
        Limit = limit;
    }

    public new void Enqueue(T item)
    {
        while (Count >= Limit)
        {
            Dequeue();
        }
        base.Enqueue(item);
    }
}

- tags2k

---

我稍微修改了代码，通过在Limit属性的Set内部调用来确保队列大小没有超过限制 - 只需一个简单的While大于Limit，Dequeue即可。除此之外，这是一个非常好的解决方案，简单易懂，谢谢。 - Scott

很好的改动，针对“Limit”属性的“setter”代码。 - Pure.Krome

这个类存在一个非常严重的限制，就像Marcus Griep在他的答案中暗示的那样：由于你的 Enqueue 方法被声明为 new（因为 Queue<T>.Enqueue 不是虚拟的），如果有人将你的 LimitedQueue<T> 强制转换为 Queue<T>，他们将能够添加任意数量的项而不受你的限制影响。建议将 if (this.Count >= this.Limit) 更改为 while (this.Count >= this.Limit)，以便保险起见（例如针对刚才提到的情况）。 - Dan Tao

如果使用Queue<T>的其他调用Enqueue()方法，原始的Enqueue将会被调用，这可能会导致严重的问题。 - Louis Rhys

Answer 2

我建议您打开C5 Library。与SCG（System.Collections.Generic）不同，C5是为接口编程和设计的，可以被子类化。大多数公共方法都是虚拟的，而且没有一个类是密封的。这样，您就不必使用那个令人讨厌的"new"关键字了，如果将您的LimitedQueue<T>强制转换为SCG.Queue<T>，它也不会触发。使用C5并几乎相同的代码，您可以从CircularQueue<T>派生出来。CircularQueue<T>实际上实现了堆栈和队列，因此您可以获得两种选项，几乎是免费的限制。下面是一些3.5结构的重写：

using C5;

public class LimitedQueue<T> : CircularQueue<T>
{
    public int Limit { get; set; }

    public LimitedQueue(int limit) : base(limit)
    {
        this.Limit = limit;
    }

    public override void Push(T item)
    {
        CheckLimit(false);
        base.Push(item);
    }

    public override void Enqueue(T item)
    {
        CheckLimit(true);
        base.Enqueue(item);
    }

    protected virtual void CheckLimit(bool enqueue)
    {
        while (this.Count >= this.Limit)
        {
            if (enqueue)
            {
                this.Dequeue();
            }
            else
            {
                this.Pop();
            }
        }
    }
}

我认为这段代码应该完全符合你的要求。

- Marcus Griep

Answer 3

并发解决方案

public class LimitedConcurrentQueue<ELEMENT> : ConcurrentQueue<ELEMENT>
{
    public readonly int Limit;

    public LimitedConcurrentQueue(int limit)
    {
        Limit = limit;
    }

    public new void Enqueue(ELEMENT element)
    {
        base.Enqueue(element);
        if (Count > Limit)
        {
            TryDequeue(out ELEMENT discard);
        }
    }
}

注意：由于Enqueue控制元素的添加，并且一次只添加一个，因此不需要执行TryDequeue的while。

- SwiftArchitect

Answer 4

希望这个课程能帮到您：
循环FIFO缓冲区在内部使用指定大小的Queue<T>。一旦达到缓冲区的大小，它将用新项替换旧项。请注意：您不能随机删除项目。我设置了Remove（T item）方法返回false。如果您想要，可以修改以随机删除项目。

public class CircularFIFO<T> : ICollection<T> , IDisposable
{
    public Queue<T> CircularBuffer;

    /// <summary>
    /// The default initial capacity.
    /// </summary>
    private int capacity = 32;

    /// <summary>
    /// Gets the actual capacity of the FIFO.
    /// </summary>
    public int Capacity
    {
        get { return capacity; }          
    }

    /// <summary>
    ///  Initialize a new instance of FIFO class that is empty and has the default initial capacity.
    /// </summary>
    public CircularFIFO()
    {            
        CircularBuffer = new Queue<T>();
    }

    /// <summary>
    /// Initialize a new instance of FIFO class that is empty and has the specified initial capacity.
    /// </summary>
    /// <param name="size"> Initial capacity of the FIFO. </param>
    public CircularFIFO(int size)
    {
        capacity = size;
        CircularBuffer = new Queue<T>(capacity);
    }

    /// <summary>
    /// Adds an item to the end of the FIFO.
    /// </summary>
    /// <param name="item"> The item to add to the end of the FIFO. </param>
    public void Add(T item)
    {
        if (this.Count >= this.Capacity)
            Remove();

        CircularBuffer.Enqueue(item);
    }

    /// <summary>
    /// Adds array of items to the end of the FIFO.
    /// </summary>
    /// <param name="item"> The array of items to add to the end of the FIFO. </param>
     public void Add(T[] item)
    { 
        int enqueuedSize = 0;
        int remainEnqueueSize = this.Capacity - this.Count;

        for (; (enqueuedSize < item.Length && enqueuedSize < remainEnqueueSize); enqueuedSize++)
            CircularBuffer.Enqueue(item[enqueuedSize]);

        if ((item.Length - enqueuedSize) != 0)
        {
            Remove((item.Length - enqueuedSize));//remaining item size

            for (; enqueuedSize < item.Length; enqueuedSize++)
                CircularBuffer.Enqueue(item[enqueuedSize]);
        }           
    }

    /// <summary>
    /// Removes and Returns an item from the FIFO.
    /// </summary>
    /// <returns> Item removed. </returns>
    public T Remove()
    {
        T removedItem = CircularBuffer.Peek();
        CircularBuffer.Dequeue();

        return removedItem;
    }

    /// <summary>
    /// Removes and Returns the array of items form the FIFO.
    /// </summary>
    /// <param name="size"> The size of item to be removed from the FIFO. </param>
    /// <returns> Removed array of items </returns>
    public T[] Remove(int size)
    {
        if (size > CircularBuffer.Count)
            size = CircularBuffer.Count;

        T[] removedItems = new T[size];

        for (int i = 0; i < size; i++)
        {
            removedItems[i] = CircularBuffer.Peek();
            CircularBuffer.Dequeue();
        }

        return removedItems;
    }

    /// <summary>
    /// Returns the item at the beginning of the FIFO with out removing it.
    /// </summary>
    /// <returns> Item Peeked. </returns>
    public T Peek()
    {
        return CircularBuffer.Peek();
    }

    /// <summary>
    /// Returns the array of item at the beginning of the FIFO with out removing it.
    /// </summary>
    /// <param name="size"> The size of the array items. </param>
    /// <returns> Array of peeked items. </returns>
    public T[] Peek(int size)
    {
        T[] arrayItems = new T[CircularBuffer.Count];
        CircularBuffer.CopyTo(arrayItems, 0);

        if (size > CircularBuffer.Count)
            size = CircularBuffer.Count;

        T[] peekedItems = new T[size];

        Array.Copy(arrayItems, 0, peekedItems, 0, size);

        return peekedItems;
    }

    /// <summary>
    /// Gets the actual number of items presented in the FIFO.
    /// </summary>
    public int Count
    {
        get
        {
            return CircularBuffer.Count;
        }
    }

    /// <summary>
    /// Removes all the contents of the FIFO.
    /// </summary>
    public void Clear()
    {
        CircularBuffer.Clear();
    }

    /// <summary>
    /// Resets and Initialize the instance of FIFO class that is empty and has the default initial capacity.
    /// </summary>
    public void Reset()
    {
        Dispose();
        CircularBuffer = new Queue<T>(capacity);
    }

    #region ICollection<T> Members

    /// <summary>
    /// Determines whether an element is in the FIFO.
    /// </summary>
    /// <param name="item"> The item to locate in the FIFO. </param>
    /// <returns></returns>
    public bool Contains(T item)
    {
        return CircularBuffer.Contains(item);
    }

    /// <summary>
    /// Copies the FIFO elements to an existing one-dimensional array. 
    /// </summary>
    /// <param name="array"> The one-dimensional array that have at list a size of the FIFO </param>
    /// <param name="arrayIndex"></param>
    public void CopyTo(T[] array, int arrayIndex)
    {
        if (array.Length >= CircularBuffer.Count)
            CircularBuffer.CopyTo(array, 0);           
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public bool Remove(T item)
    {
        return false; 
    }

    #endregion

    #region IEnumerable<T> Members

    public IEnumerator<T> GetEnumerator()
    {
       return CircularBuffer.GetEnumerator();
    }

    #endregion

    #region IEnumerable Members

    IEnumerator IEnumerable.GetEnumerator()
    {
        return CircularBuffer.GetEnumerator();
    }

    #endregion

    #region IDisposable Members

    /// <summary>
    /// Releases all the resource used by the FIFO.
    /// </summary>
    public void Dispose()
    {          
        CircularBuffer.Clear();
        CircularBuffer = null;
        GC.Collect();
    }

    #endregion
}

- Robel.E

---

我认为通过使用这段代码，您可以拥有一个有限大小的队列..它也是循环缓冲区。 - Robel.E

Answer 5

你应该创建自己的类，一个环形缓冲区可能适合你的需求。

除了数组之外，.NET中允许你指定容量的数据结构用于构建用于保存内部数据的内部数据结构。

例如，对于列表，容量用于调整内部数组的大小。当你开始向列表中添加元素时，它将从索引0开始填充这个数组，并在达到容量时增加容量到一个新的更高容量，并继续填充它。

- Lasse V. Karlsen

Answer 6

为什么不直接使用大小为2的数组？队列应该能够动态增长和缩小。

或者创建一个包装类，将Queue<T>实例作为其实例，并在每次入队一个<T>对象时检查队列的大小。如果大于2，则出队第一个项目。

- CodingWithoutComments

Answer 7

如果对任何人有用的话，我制作了一个LimitedStack<T>。

public class LimitedStack<T>
{
    public readonly int Limit;
    private readonly List<T> _stack;

    public LimitedStack(int limit = 32)
    {
        Limit = limit;
        _stack = new List<T>(limit);
    }

    public void Push(T item)
    {
        if (_stack.Count == Limit) _stack.RemoveAt(0);
        _stack.Add(item);
    }

    public T Peek()
    {
        return _stack[_stack.Count - 1];
    }

    public void Pop()
    {
        _stack.RemoveAt(_stack.Count - 1);
    }

    public int Count
    {
        get { return _stack.Count; }
    }
}

当栈的大小超过限制时，它会移除最老的项目（栈底）。

（这个问题是“C# 限制栈大小”在谷歌搜索结果中排名第一）

- mpen

---

这段代码正确率达到99%。但是，如果我们在栈中没有放任何东西就调用Peek或Pop，程序将会崩溃，因为索引值为-1。通过添加索引边界检查，可以轻松解决这个问题。 - Contango

建议在 Peek 和 Pop() 中添加以下内容：如果((_stack.Count - 1) < 0)，则抛出新的异常("Cannot Peek or Pop without first doing a Push.")。这将提醒程序员注意这种情况，并在使用此类时记住它。我们还可以添加 TryPeek 或 TryPop，这是 Microsoft 在其 ConcurrentDictionary 实现中采用的方法。 - Contango

记录一下，这段代码没有额外的锁定是不安全的（这完全没问题，线程安全从未是该类设计规范的一部分）。 - Contango

Answer 8

你可以使用一个 LinkedList<T> 并添加线程安全性：

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

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

    public void Enqueue(T item)
    {
        // todo: add synchronization mechanism
        if (Count == capacity) RemoveLast();
        AddFirst(item);
    }

    public T Dequeue()
    {
        // todo: add synchronization mechanism
        var last = Last.Value;
        RemoveLast();
        return last;
    }
}

需要注意的是，在此示例中，默认枚举顺序将为LIFO。但如果必要，可以进行覆盖。

- Brandon