Дек
Определение
Дек (от англ. deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO, поэтому на ней можно реализовать как стек, так и очередь. В первом случае нужно использовать только методы головы или хвоста, во втором — методы push и pop двух разных концов. Дек можно воспринимать как двустороннюю очередь. Он имеет следующие операции:
- — проверка на наличие элементов,
- (запись в конец) — операция вставки нового элемента в конец,
- (снятие с конца) — операция удаления конечного элемента,
- (запись в начало) — операция вставки нового элемента в начало,
- (снятие с начала) — операция удаления начального элемента.
Реализации
Дек расходует только памяти, на хранение самих элементов.
Простая реализация
В данной реализации изначально и . Ключевые поля:
- — массив, с помощью которого реализуется дек, способный вместить не более элементов,
- — индекс головы дека,
- — индекс хвоста.
Дек состоит из элементов . Если происходит максимум добавлений, то массив длины может вместить в себя все добавленные элементы.
boolean empty(): return head == tail
function pushBack(x : T): d[tail++] = x
T popBack():
if (empty())
return error "underflow"
return d[--tail]
function pushFront(x : T): d[--head] = x
T popFront():
if (empty())
return error "underflow"
return d[head++]
Циклический дек на массиве константной длины
Во всех циклических реализациях изначально присвоены следующие значения и . Ключевые поля:
- — массив, с помощью которого реализуется дек, способный вместить не более элементов,
- — индекс головы дека,
- — индекс хвоста.
Дек состоит из элементов или и . Всего он способен вместить не более элементов. В данной реализации учитывается переполнение и правильно обрабатывается изъятие из пустого дека. Недостатком является константная длина массива, хранящего элементы. Все операции выполняются за .
function pushBack(x : T):
if (head == (tail + 1) % n)
return error "overflow"
d[tail] = x
tail = (tail + 1) % n
T popBack():
if (empty())
return error "underflow"
tail = (tail - 1 + n) % n
return d[tail]
function pushFront(x : T):
if (head == (tail + 1) % n)
return error "overflow"
head = (head - 1 + n) % n
d[head] = x
T popFront():
if (empty())
return error "underflow"
T ret = d[head]
head = (head + 1) % n
return ret
Циклический дек на динамическом массиве
Ключевые поля:
- — размер массива,
- — массив, в котором хранится дек,
- — временный массив, где хранятся элементы после перекопирования,
- — индекс головы дека,
- — индекс хвоста.
Дек состоит из элементов или и . Если реализовывать дек на динамическом массиве, то мы можем избежать ошибки переполнения. При выполнении операций и происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также происходит проверка на избыточность памяти, выделенной под дек при выполнении операций и . Если памяти под дек выделено в четыре раза больше размера дека, то массив сокращается в два раза. Для удобства выделим в отдельную функцию получение текущего размера дека.
int size()
if tail > head
return n - head + tail
else
return tail - head
function pushBack(x : T):
if (head == (tail + 1) % n)
T newDeque[n * 2]
for i = 0 to n - 2
newDeque[i] = d[head]
head = (head + 1) % n
d = newDeque
head = 0
tail = n - 1
n *= 2
d[tail] = x
tail = (tail + 1) % n
T popBack():
if (empty())
return error "underflow"
if (size() < n / 4)
T newDeque[n / 2]
int dequeSize = size()
for i = 0 to dequeSize - 1
newDeque[i] = d[head]
head = (head + 1) % n
d = newDeque
head = 0
tail = dequeSize
n /= 2
tail = (tail - 1 + n) % n
return d[tail]
function pushFront(x : T):
if (head == (tail + 1) % n)
T newDeque[n * 2]
for i = 0 to n - 2
newDeque[i] = d[head]
head = (head + 1) % n
d = newDeque
head = 0
tail = n - 1
n *= 2
head = (head - 1 + n) % n
d[head] = x
T popFront():
if (empty())
return error "underflow"
if (size() < n / 4)
T newDeque[n / 2]
int dequeSize = size()
for i = 0 to dequeSize - 1
newDeque[i] = d[head]
head = (head + 1) % n
d = newDeque
head = 0
tail = dequeSize
n /= 2
T ret = d[head]
head = (head + 1) % n
return ret
На списке
Ключевые поля:
-
ListItem(data : T, next : ListItem, prev : ListItem)— конструктор, - — ссылка на хвост,
- — ссылка на голову.
Дек очень просто реализуется на двусвязном списке. Он состоит из элементов . Элементы всегда добавляются либо в , либо в . В данной реализации не учитывается изъятие из пустого дека.
function initialize(): head = ListItem(null, null, null) tail = ListItem(null, null, head) head.next = tail
function pushBack(x : T): head = ListItem(x, head, null) head.next.prev = head
T popBack(): data = head.data head = head.next return data
function pushFront(x : T): tail = ListItem(x, null, tail) tail.prev.next = tail
T popFront(): data = tail.data tail = tail.prev return data
На двух стеках
Ключевые поля:
- — ссылка на хвост,
- — ссылка на голову.
Храним два стека — и . Левый стек используем для операций и , правый — для и . Если мы хотим работать с левым стеком и при этом он оказывается пустым, то достаем нижнюю половину элементов из правого и кладем в левый, воспользовавшись при этом локальным стеком. Аналогично с правым стеком. Худшее время работы — .
function pushBack(x : T): leftStack.push(x)
T popBack():
if not leftStack.empty()
return leftStack.pop()
else
int size = rightStack.size()
Stack<T> local
for i = 0 to size / 2
local.push(rightStack.pop())
while not rightStack.empty()
leftStack.push(rightStack.pop())
while not local.empty()
rightStack.push(local.pop())
return leftStack.pop()
function pushFront(x : T): rightStack.push(x)
T popFront():
if not rightStack.empty()
return rightStack.pop()
else
int size = leftStack.size()
Stack<T> local
for i = 0 to size / 2
local.push(leftStack.pop())
while not leftStack.empty()
rightStack.push(leftStack.pop())
while not local.empty()
leftStack.push(local.pop())
return rightStack.pop()
| Лемма: |
Амортизированная стоимость операции в таком деке — . |
| Доказательство: |
|
Воспользуемся методом предоплаты для доказательства. Достаточно доказать, что между двумя балансировками происходит достаточно амортизирующих их операций. Вначале в обоих стеках пусто, поэтому они сбалансированы. Рассмотрим дек после очередной балансировки, будем использовать две монеты для операций и — одну для самой операции, а другую — в качестве резерва. Разберем худший случай: после очередной балансировки происходит удаление всех элементов только из одного стека. В таком случае при удалении кладем одну резервную монету на элемент из другого стека. Тогда учетная стоимость следующей балансировки равна нулю, поскольку на всех элементах дека лежит по монете. Ч. т. д. |
