120
правок
Изменения
м
→Реализация на шести стеках
Инвариант очереди (обычный режим):
# Стек <tex>L</tex> содержит левую половину очереди, порядок при извлечении обратный.
# Стек <tex>R</tex> содержит правую половину очереди, порядок при извлечении прямой.
# <tex>L.size \leqslant R.size</tex>
# <tex>R.size = 0 \equiv Q.size = 0</tex>
# <tex>Rc'.size < R.size - L.size</tex>
# <tex>L'.size = 0, T.size = 0</tex>
Тогда к следующему перекопированию (<tex>L.size=R.size+1</tex>) мы гарантированно будем иметь пустые стеки <tex>L',T,Rc'</tex>, которые нам понадобятся.
