215
правок
Изменения
Очередь
,→Реализация на двух стеках
== Реализация на двух стеках ==
Эта реализация пригодится, например, для нахождения наименьшего элемента за <tex>O(1)</tex>.
Очередь можно реализовать на двух [[Стек|стеках]] <tex>leftStack</tex> и <tex>rightStack</tex>. Один из стеков <tex>(leftStack)</tex> будем использовать для операции <math> \mathrm {push} </math>, другой для операции <math> \mathrm {pop} </math>. При этом, если при попытке извлечения элемента из <tex>rightStack</tex> он оказался пустым, просто перенесем все элементы из <tex>leftStack</tex> в него (при этом элементы в <tex>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>leftStack</tex> станет пустым).