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