Дек
Определение
Дек (от англ. deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Дек можно воспринимать как двустороннюю очередь или двусторонний стек. Он имеет следующие операции:
- — проверка на наличие элементов,
- (запись в конец) — операция вставки нового элемента в конец,
- (снятие с конца) — операция удаления конечного элемента,
- (запись в начало) — операция вставки нового элемента в начало,
- (снятие с начала) — операция удаления начального элемента.
Реализации
Дек расходует только памяти, на хранение самих элементов.
На массиве
Ключевые поля:
- — массив, с помощью которого реализуется дек, способный вместить не более элементов,
- — индекс головы дека,
- — индекс хвоста дека.
Дек состоит из элементов . Всего дек способен вместить не более элементов, поэтому при переполнении приходится перевыделять память и копировать все элементы.
boolean empty():
return d.head%n+1 == d.tail
function pushBack(x : T):
if (d.head == d.tail)
return error "overflow"
d[d.tail] = x
d.tail = (d.tail - 2 + n) % n + 1
T popBack():
if (empty())
return error "underflow"
d.tail = d.tail % n + 1
return d[d.tail]
function pushFront(x : T):
if (d.head == d.tail)
return error "overflow"
d[d.head] = x
d.head = d.head % n + 1
T popFront():
if (empty())
return error "underflow"
d.head = (d.head - 2 + n) % n + 1
return d[d.head]
Все операции выполняются за .
На саморасширяющемся массиве
---
На списке
Ключевые поля:
-
ListItem(data : T, next : ListItem, prev : ListItem)— конструктор, - — ссылка на хвост,
- — ссылка на голову.
Дек очень просто реализуется на списке. Элементы всегда добавляются либо в , либо в .
