Эффективный способ реализовать индексированную очередь (где элементы могут быть получены по индексу за O (1) времени)?

Question

Доступ к элементам по индексу с использованием ElementAt, очевидно, не является разумным выбором с точки зрения производительности .NET ElementAt .

Существует ли альтернативная общая структура данных, которая бы соответствовала этому требованию?

Моя очередь имеет фиксированную емкость.

В соответствии с MSDN-записью в классе очереди , " Этот класс реализует очередь в виде циклического массива ", но, похоже, он не предоставляет никаких свойств индексирования.

Обновление : Я обнаружил реализацию C5 CircularQueue . Кажется, это соответствует всем требованиям, но я бы предпочел не импортировать другую внешнюю библиотеку, если это возможно.

Answer 1

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

Answer 2

Вы можете использовать циклический массив .Т.е. реализовать очередь в массиве.

Реализация довольно тривиальна, вам не нужно использовать внешнюю библиотеку, просто реализуйте ее самостоятельно.Подсказка: проще использовать m_beginIndex, m_nElements членов, чем m_beginIndex, m_endIndex.