28
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
% _
j k deq size
=
//
удаление в очереди
(
)
,
i
erase D j
//
сдвиг элементов
(
1)
V
пока i S
< −
1
_ (
)
i
temp pop front D
+
=
_ ( ,
)
i
push back D temp
i
+ +
end
//
если последняя пуста
1
(
(
))
V
S
если empty D
−
_ ( )
last
D pop back V
=
(
)
last
destroy D
end
Здесь
(
)
,
erase D pos
—
удаление элемента в очереди
D
в позиции
pos
;
_ ( )
pop front D
—
вынимание элемента с начала очереди
D
;
_ ( ,
)
push back D val
—
вставка элемента
val
в конец очереди
D
;
( )
empty D
—
узнать, пуста ли очередь
D
;
_ ( )
pop back V
—
вынуть
указатель на очередь с конца массива
V
;
( )
destroy D
—
уничтожить
очередь
D
.
Операция удаления одного элемента (рис. 6) состоит из доступа,
удаления из очереди и «сдвига» вверх, сложность:
(1) ( )
D
O O S
+
+
1/2
1/2
1/2
( )
(1) (
) (
)
(
).
V
O S O О N О N O N
+
≅ +
+
=
Рис. 6. Операция удаления в IgushArray