26
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
3.1)
вынуть элемент с конца текущей очереди
i
D
,
сложность
О
(1);
3.2)
вставить элемент в начало следующей очереди
1
i
D
+
,
слож-
ность
О
(1).
Каждый сдвиг имеет сложность
О
(1).
Необходимо «сдвинуть»
вниз порядка
V
S
элементов. Таким образом, вся сложность «сдвига»
составляет
2 (1)
( ).
V
V
S O O S
=
Примечание
.
Операция может потребовать вставку нового указателя в
конец массива указателей и создание новой очереди (если последняя оче-
редь до операции полная, после операции переполнена). Операция может
потребовать ( )
V
O S
времени и не испортить общую производительность.
Псевдокод операции вставки:
//
доступ к позиции
/
_
i
k deq size
= ⎢
⎥
⎣
⎦
[ ]
i
D V i
=
% _
j k deq size
=
//
вставка в очереди
(
)
, ,
i
insert D j val
//
сдвиг элементов
(
1)
V
пока i S
< −
_ ( )
i
temp pop back D
=
1
_ (
,
)
i
push front D temp
+
i
+ +
end
//
если последняя очередь переполнена
1
( (
)
)
V
S
D
если size D S
−
>
1
_ (
)
V
S
temp pop back D
−
=
_ (
,
)
new
push front D temp
_ ( ,
)
new
push back V D
end
Здесь
(
)
,
,
insert D pos val
—
вставка элемента
val
в очередь
D
в пози-
цию
pos
;
_ ( )
pop back D
—
вынимание элемента с конца очереди
D
;
_ ( ,
)
push front D val
–
вставка элемента
val
в начало очереди
D
;
( )
size D
—
текущий размер очереди
D
;
_ ( , )
push back V D
—
вставка в
конец массива
V
указателя на очередь
D
.
Операция вставки одного элемента (рис. 5) состоит из доступа,
вставки в очередь и «сдвига» вниз, операция в целом имеет слож-
ность
1/2
1/2
1/2
(1) ( ) ( )
(1) (
) (
)
(
).
D
V
O O S O S O О N О N O N
+
+
≅ +
+
=