338
правок
Изменения
м
leftStack.pushLeft(x)
rightPushpushRight(popLeft(leftStack[leftSize]) leftSize--) return rightStack.popStackpopRight()
→Реализация на двух стеках
== Реализация на двух стеках ==
Очередь можно реализовать на двух [[Стек|стеках]] <tex>leftStack</tex> и <tex>rightStack</tex>. Один из стеков <tex>(leftStack)</tex> будем использовать для операции <tex>push</tex>, другой для операции <tex>pop</tex>. При этом, если при попытке извлечения элемента из <tex>rightStack</tex> он оказался пустым, просто перенесем все элементы из <tex>leftStack</tex> в него (при этом элементы в <tex>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>leftStack</tex> станет пустым).
* <tex>pushLeft</tex> и <tex>pushRight</tex> - функции, реализующие операцию <tex>push</tex> для соответствующего стека; * <tex>popStackpopLeft</tex> - операция и <tex>poppopRight</tex> для - аналогично операции <tex>rightStackpop</tex>.
=== push ===
push(x)
=== pop ===
if !rigthStack.empty()
return rightStack.popStackpopRight()
else
if !leftStack.empty()
while !leftStack.empty()
Каждая операция выполняется за амортизированную <tex>O(1)</tex>.
