39
правок
Изменения
Дек
,→Реализации
== Реализации ==
Дек расходует только <tex>O(n)</tex> памяти, на хранение самих элементов.
=== Простая реализация ===
В даннн <tex> \mathtt{d.head = n} </tex> и <tex> \mathtt{d.tail = n} </tex>.
Ключевые поля:
* <tex>\mathtt{d[0\dots 2 \times n - 1]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,
* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста.
Дек состоит из элементов <tex>\mathtt {d[d.head\dots d.tail- 1]}</tex>. Если происходит максимум <tex>\mathtt {n}</tex> добавлений, то массив длины <tex>\mathtt {2 \times n}</tex> может вместить в себя все добавленные элементы. При этом <tex> \mathtt{d.head = n} </tex> и <tex> \mathtt{d.tail = n} </tex>.
'''boolean''' empty():
=== Циклический дек на массиве константной длины ===
Во всех циклических реализациях <tex> \mathtt{head = 0} </tex> и <tex> \mathtt{tail = 0} </tex>.
Ключевые поля:
* <tex>\mathtt{d[0\dots n-1]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,
* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста.
Дек состоит из элементов <tex>\mathtt {d[d.head\dots d.tail-1]}</tex> или <tex>\mathtt {d[0\dots d.tail-1]}</tex> и <tex>\mathtt {d[d.head\dots n-1]}</tex>. Всего он способен вместить не более <tex>n</tex> элементов. В данной реализации учитывается переполнение и правильно обрабатывается изъятие из пустого дека. Недостатком является константная длина массива, хранящего элементы. Все операции выполняются за <tex>O(1)</tex>.
'''function''' pushBack(x : '''T'''):
* <tex>\mathtt{capacity}</tex> {{---}} размер массива.
Дек состоит из элементов <tex>\mathtt {d[d.head\dots d.tail-1]}</tex> или <tex>\mathtt {d[0\dots d.tail-1]}</tex> и <tex>\mathtt {d[d.head\dots n-1]}</tex>. Если реализовывать дек на [[Динамический_массив | динамическом массиве]], то мы можем избежать ошибки переполнения. При выполнении операций <tex>\mathtt{pushBack}</tex> и <tex>\mathtt{pushFront}</tex> происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также происходит проверка на избыточность памяти, выделенной под дек при выполнении операций <tex>\mathtt{popBack}</tex> и <tex>\mathtt{popFront}</tex>. Если памяти под дек выделено в четыре раза больше размера дека, то массив сокращается в два раза. Для удобства выделим в отдельную функцию <tex>\mathtt{size}</tex> получение текущего размера дека.
'''int''' size()
'''function''' pushBack(x : '''T'''):
'''if''' (d.head == (d.tail+ 1) % n)
'''T''' newDeque[capacity * 2]
'''for''' i = 0 '''to''' capacity - 1
'''function''' pushFront(x : '''T'''):
'''if''' (d.head == (d.tail+ 1) % n)
'''T''' newDeque[capacity * 2]
'''for''' i = 0 '''to''' capacity - 1
* <tex>\mathtt{head}</tex> {{---}} ссылка на голову.
Дек очень просто реализуется на [[Список | двусвязном списке]]. Он состоит из элементов <tex>\mathtt {head\dots tail}</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>, однако, амортизационная стоимость операции — <tex>O(1)</tex>.
'''function''' pushBack(x : '''T'''):
