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