实现索引队列的有效方法(在O(1)时间内可以通过索引检索元素)？

Question

根据.NET队列ElementAt性能,使用ElementAt按索引访问项目显然不是一个合理的选择.

是否有适合此要求的替代通用数据结构？

我的队列有固定的容量.

根据Queue类上的MSDN条目," 此类将队列实现为循环数组 ",但它似乎没有公开任何类型的索引属性.

更新:我找到了C5的CircularQueue实现.这似乎符合要求,但如果可能,我宁愿不必导入另一个外部库.

Answer 1

您可以使用循环数组.即在数组中实现队列.

实现非常简单,您不需要使用外部库,只需自己实现.提示:使用m_beginIndex, m_nElements成员比使用成员更容易m_beginIndex, m_endIndex.

Answer 2

public class IndexedQueue<T>
{
    T[] array;
    int start;
    int len;

    public IndexedQueue(int initialBufferSize)
    {
        array = new T[initialBufferSize];
        start = 0;
        len = 0;
    }

    public void Enqueue(T t)
    {
        if (len == array.Length)
        {
            //increase the size of the cicularBuffer, and copy everything
            T[] bigger = new T[array.Length * 2];
            for (int i = 0; i < len; i++)
            {
                bigger[i] = array[(start + i) % len];
            }
            start = 0;
            array = bigger;
        }            
        array[(start + len) % array.Length] = t;
        ++len;
    }

    public T Dequeue()
    {
        var result = array[start];
        start = (start + 1) % array.Length;
        --len;
        return result;
    }

    public int Count { get { return len; } }

    public T this[int index]
    {
        get 
        { 
            return array[(start + index) % array.Length]; 
        }
    }        
}