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> элементов,
