39
правок
Изменения
Дек
,Нет описания правки
== Определение ==
[[Файл:deque1.png|thumb|right|200px|Дек]]
'''Дек''' (от англ. ''deque'' {{---}} double ended queue) {{---}} структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO. Дек можно воспринимать как двустороннюю очередь или двусторонний стек. Он имеет следующие операции:
* <tex> \mathtt{empty} </tex> {{---}} проверка на наличие элементов,
* <tex> \mathtt{pushBack} </tex> (запись в конец) {{---}} операция вставки нового элемента в конец,
* <tex> \mathtt{popFront} </tex> (снятие с начала) {{---}} операция удаления начального элемента.
==Реализации==
Дек расходует только <tex>O(n)</tex> памяти, на хранение самих элементов.
=== На массиве ===
* <tex>\mathtt{d[1\dots n]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,
* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,
* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста дека.
Дек состоит из элементов <tex>\mathtt {d[d.tail\dots d.head]}</tex>. Всего дек он способен вместить не более <tex>n</tex> элементов. В данной реализации учитывается переполнение и правильно обрабатывается изъятие из пустого дека. Недостатком является константная длина массива, поэтому при переполнении приходится перевыделять память и копировать все хранящего элементы. Все операции выполняются за <tex>O(1)</tex>.
'''boolean''' empty():
'''return''' d[d.head]
=== На саморасширяющемся массиве ===
Ключевые поля:
* <tex>\mathtt{newDeque[1\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,
* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,
* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста дека,
* <tex>\mathtt{capacity}</tex> {{---}} размер массива.
Если реализовывать дек на динамическом массиве, то мы можем избежать ошибки переполнения. При выполнении операций <tex>\mathtt{pushBack}/tex> и <tex>\mathtt{pushFront}</tex> происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также проверяемпроисходит проверка на избыточность памяти, не нужно ли нам уменьшить размер массива выделенной под дек при выполнении операций <tex>\mathtt{popBack}</tex> и <tex>\mathtt{popFront}</tex>. Если памяти слишком много, то массив сокращается. Для удобства выделим в отдельную функцию <tex>\mathtt{size}</tex> получение текущего размера дека.
'''int''' size()
* <tex>\mathtt{head}</tex> {{---}} ссылка на голову.
Дек очень просто реализуется на двусвязном списке. Элементы всегда добавляются либо в <tex>\mathtt{tail.prev}</tex>, либо в <tex>\mathtt{head.next}</tex>. В данной реализации не учитывается пустой декизъятие из пустого дека.
'''function''' pushBack(x : '''T'''):
* <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>.
'''function''' pushBack(x : '''T'''):
* [[Персистентный дек]]
==Источники информации==* [[wikipedia:ru:Двусвязная_очередь|Википедия {{---}} Дек (программирование)]] [[Категория: Дискретная математика и алгоритмы]]
