215
правок
Изменения
→Реализация на двух стеках
== Реализация на двух стеках ==
Очередь можно реализовать на двух [[Стек|стеках]] <tex>leftStack</tex> и <tex>rightStack</tex>. Один из стеков <tex>(leftStack)</tex> будем использовать для операции <texmath>\mathrm {push} </texmath>, другой для операции <texmath>\mathrm {pop} </texmath>. При этом, если при попытке извлечения элемента из <tex>rightStack</tex> он оказался пустым, просто перенесем все элементы из <tex>leftStack</tex> в него (при этом элементы в <tex>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>leftStack</tex> станет пустым).
* <texmath>\mathrm {pushLeft} </texmath> и <texmath>\mathrm {pushRight} </texmath> - функции, реализующие операцию <tex>push</tex> для соответствующего стека; * <texmath>\mathrm {popLeft} </texmath> и <texmath>\mathrm {popRight} </texmath> - аналогично операции <texmath>\mathrm {pop} </texmath>.
=== push ===
'''function''' push(x): pushLeft(x)
=== pop ===
'''if ''' !rigthStack.empty() '''return ''' popRight() '''else''' '''while ''' !leftStack.empty() pushRight(popLeft()) '''return ''' popRight()
При выполнении операции <tex>push</tex> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <tex>pop</tex> из первого стека, третью во второй стек на финальный <tex>pop</tex>. Тогда для операций <tex>pop</tex> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <tex>push</tex>.
