24
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
1/2
;
D
S N
⎡ ⎤
= ⎢ ⎥
/
;
V
D
S N S
= ⎡
⎤
⎢
⎥
1/2
D V
S S N
≅ ≅
.
Размер массива может изменяться по мере работы со структурой;
размер очередей не меняется никогда. После работы со структурой
можно выполнить полное перестроение для подгонки размера массива и
очередей до размера приблизительно
N
1/2
.
Рекомендуется знать прибли-
зительный размер будущей структуры во время ее создания, чтобы из-
начально рассчитать оптимальные размеры очереди. Иначе размер оче-
редей будет 1 и время вставки или удаления выродится в линейное.
Очередь с двумя концами может быть реализована с использова-
нием массива (набора массивов), либо списка. В первом случае обес-
печивается константный доступ, но линейные вставка или удаление,
во втором — линейный доступ, но константные вставка или удале-
ние. Очень важно, чтобы в структуре IgushArray очередь была реали-
зована с помощью именно первого способа. Поскольку размер очере-
дей известен во время создания структуры и никогда не изменяется,
то очередь можно создать из
одного массива
,
что улучшит и упро-
стит реализацию. Таким образом, массив и очереди, применяемые в
структуре IgushArray, являются структурами с произвольным досту-
пом (рис. 3).
Рис. 3. Струтура IgushArray
S
V