39
правок
Изменения
Дек
,→На двух стеках
* <tex>\mathtt{rightStack}</tex> {{---}} ссылка на голову.
Храним два стека - — <tex>\mathtt{leftStack}</tex> и <tex>\mathtt{rightStack}</tex>. Левый стек используем для операций <tex>\mathtt{popBack}</tex> и <tex>\mathtt{pushBack}</tex>, правый - — для <tex>\mathtt{popFront}</tex> и <tex>\mathtt{pushFront}</tex>. Если мы хотим работать с левым стеком и при этом он оказывается пустым, то по очереди достаем все элементы нижнюю половину элементов из правого и кладем в левый, воспользовавшись при этом локальным стеком. Аналогично с правым стеком. Худшее время работы каждой — <tex>O(n)</tex>, однако амортизационная стоимость операции - — <tex>O(n1)</tex>.
'''function''' pushBack(x : '''T'''):
'''return''' leftStack.pop()
'''else'''
'''int''' size = rightStack.size()
'''Stack<T>''' local
'''for''' i = 0 '''to''' size - 1
local.push(rightStack.pop())
'''while''' '''not''' rightStack.empty()
leftStack.push(rightStack.pop())
'''while''' '''not''' local.empty()
rightStack.push(local.pop())
'''return''' leftStack.pop()
rightStack.push(x)
'''T''' popFrontpopBack():
'''if''' '''not''' rightStack.empty()
'''return''' rightStack.pop()
'''else'''
'''int''' size = leftStack.size()
'''Stack<T>''' local
'''for''' i = 0 '''to''' size - 1
local.push(leftStack.pop())
'''while''' '''not''' leftStack.empty()
rightStack.push(leftStack.pop())
'''while''' '''not''' local.empty()
leftStack.push(local.pop())
'''return''' rightStack.pop()
