39
правок
Изменения
Дек
,Нет описания правки
=== На саморасширяющемся массиве ===
Ключевые поля:
* <tex>\mathtt{sd[1\dots n]}</tex> {{---}} массив, в котором хранится дек,
* <tex>\mathtt{newDeque[1\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,
* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,
* <tex>\mathtt{head}</tex> {{---}} ссылка на голову.
Дек очень просто реализуется на двусвязном списке. Элементы всегда добавляются либо в <tex>\mathtt{tail.prev}</tex>, либо в <tex>\mathtt{head.next}</tex>. В данной реализации не учитывается пустой дек.
'''function''' pushBack(x : '''T'''):
=== На двух стеках ===
Ключевые поля:
* <tex>\mathtt{leftStack}</tex> {{---}} ссылка на хвост,
* <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>.
'''function''' pushBack(x : '''T'''):
leftStack.push(x)
'''T''' popBack():
'''if''' '''not''' leftStack.empty()
'''return''' leftStack.pop()
'''else'''
'''while''' '''not''' rightStack.empty()
leftStack.push(rightStack.pop())
'''return''' leftStack.pop()
'''function''' pushFront(x : '''T'''):
rightStack.push(x)
'''T''' popFront():
'''if''' '''not''' rightStack.empty()
'''return''' rightStack.pop()
'''else'''
'''while''' '''not''' leftStack.empty()
rightStack.push(leftStack.pop())
'''return''' rightStack.pop()
== См. также ==
* [[Стек]]
* [[Очередь]]
* [[Персистентный дек]]
==Источники информации==
