Дек
Содержание
Определение
Дек (от англ. 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()
| Лемма: |
Амортизированная стоимость операции в таком деке — . |
| Доказательство: |
|
Воспользуемся методом предоплаты для доказательства. Достаточно доказать, что между двумя балансировками происходит достаточно амортизирующих их операций. Вначале в обоих стеках пусто, поэтому они сбалансированы. Рассмотрим дек после очередной балансировки, будем использовать две монеты для операций и — одну для самой операции, а другую — в качестве резерва. Разберем худший случай: после очередной балансировки происходит удаление всех элементов только из одного стека. В таком случае при удалении кладем одну резервную монету на элемент из другого стека. Тогда учетная стоимость следующей балансировки равна нулю, поскольку на всех элементах дека лежит по монете. |
