120
правок
Изменения
→Реализация на шести стеках: оформление операций
Заметим, что вышеприведенный алгоритм гарантирует нам, что в обычном режиме в стеке <tex>L</tex> находится не больше элементов, чем в <tex>R</tex>, так что проверка на пустоту очереди при обычном режиме сводится к проверке на пустоту стека <tex>R</tex>.
Пусть наша очередь <tex>Q</tex> имеет стеки <tex>L1, L2, R, Rc1, Rc2, T</tex>, а также переменные <tex>recopy</tex> и <tex>toCopy</tex>, тогда вышеприведенный алгоритм реализует следующий псевдокод:выполняет требуемые операции.=== empty ===
<code>
empty()
return !recopy and R.size == 0 </code>=== push ===<code>
push(x)
if !recopy
L2.push(x)
checkNormal()
</code>=== pop ===<code>
pop()
if !recopy
checkNormal()
return tmp
</code>=== checkRecopy ===<code>
checkRecopy()
if Rc2.size > 0
toCopy = Rc1.size
additionalOperations()
</code>=== checkNormal ===<code>
checkNormal()
additionalOperations()
// Если мы не все перекопировали, то у нас не пуст стек T
recopy = T.size != 0
</code>=== additionalOperations ===<code>
additionalOperations()
// Нам достаточно 3 операций на вызов
