очередь реализованная с помощью массива

Для вставки нового элемента в IgushArray, необходимо вставить новый элемент в конкретной позицию в конкретной очереди ( O (N1/2) ) и “сдвинуть” элементы в этой и следующих очередях вниз. “Сдвиг” элемента вниз означает, что необходимо вынуть элемент с конца текущей очереди и вставить в начало следующей. Каждый такой сдвиг имеет сложность O (1). Необходимо “сдвинуть” вниз порядка N1/2 элементов ( O (N1/2) ). См. схему внизу. Как видно, полная операция имеет сложность O (N1/2).

Для доступа произвольного элемента по его индексу в IgushArray, необходимо рассчитать индекс в массиве с помощью K / deq_size операции ( O (1) ), затем получить указатель ( O (1) ), рассчитать индекс в очереди при помощи K % deq_size операции ( O (1) ) и получить элемент в очереди. См. схему внизу. Как видно, операция доступа имеет константную сложность.

Таким образом, массив и очереди, используемые при реализации IgushArray, сами по себе являются структурами с произвольным доступом.

Двусвязная очередь может быть реализована, используя массив (набор массивов) или лист. В первом случае обеспечивается константный доступ, но линейные вставка/удаление, во втором случае обеспечивается линейный доступ, но константные вставка/удаление. Очень важно, чтобы в IgushArray двусвязная очередь была реализована, используя именно первый способ. Также в IgushArray размер очередей известен во время создания и никогда не меняется, поэтому этот факт может быть использован и очередь может быть реализована, используя всего один массив, что улучшит и упросит реализацию

Размер массива может изменяться по мере работы со структурой; размер очередей не меняется никогда. Но после некоторой работы со структурой, может быть сделано полное перестроение для подгонки размера массива и очередей для размера приблизительно N1/2. Также очень рекомендуется знать приблизительный размер будущей структуры во время создания, чтобы изначально рассчитать оптимальные размеры. Иначе размер двусвязных очередей будет 1, и время вставки/удаления выродится в линейное.

IgushArray ЂЂЂ это массив указателей размера приблизительно N1/2. Каждый элемент указывает на двусвязную очередь размера приблизительно N1/2. Все очереди имеют одинаковый размер за исключением последней (последняя может иметь размер меньший, чем N1/2). См. схему внизу.

Существуют две базовые структуры данных: массив и лист. Массив это структура с произвольным доступом, но с дорогой линейной операцией вставки/удаления. Лист напротив структура с последовательным доступом, но имеет быструю константную операцию вставки/удаления. В этой статье я опишу структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”. Сравнение с другими структурами можно увидеть в таблице внизу.

IgushArray (быстрый массив) | Эдуард Игушев