Дек
Дек (от англ. deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO, поэтому на ней можно реализовать как стек, так и очередь. В первом случае нужно использовать только методы головы или хвоста, во втором — методы push и pop двух разных концов. Дек можно воспринимать как двустороннюю очередь.
Дек поддерживает следующие операции:
● empty — проверка дека на наличие в нем элементов,
● push_back (запись в конец дека) — операция вставки нового элемента в конец,
● pop_back (снятие с конца дека) — операция удаления конечного элемента,
● push_front — (запись в начало дека) — операция вставки нового элемента в начало.
● pop_front (снятие с начала дека) — операция удаления начального элемента.
Реализация на массиве
В данной реализации изначально \(head = n - 1\) и \(tail = n - 1\). Ключевы поля:
● \(array[0 \ldots 2n-1]\) — массив, с помощью которого реализуется дек, способный вместить не более \(n\) элементов,
● \(head\) — индекс головы дека,
● \(tail\) — индекс хвоста.
Дек состоит из элементов \(array[0 \ldots 2n-1]\). Если происходит максимум \(n\) добавлений, то массив длины \(2 \times n\) может вместить в себя все добавленные элементы.
class Deque:
def __init__(self, n):
self.deque = [0] * (2 * n)
self.head = n - 1
self.tail = n - 1
def empty(self):
return self.head == self.tail
def push_back(self, x):
self.deque[self.tail] = x
self.tail += 1
def pop_back(self):
if self.empty():
return 'UnderflowError'
self.tail -= 1
x = self.deque[self.tail]
return x
def push_front(self, x):
self.head -= 1
self.deque[self.head] = x
def pop_front(self):
if self.empty():
return 'UnderflowError'
x = self.deque[self.head]
self.head += 1
return x
Реализация на двух стеках
Ключевы поля:
● \(left\_stack\) — ссылка на хвост,
● \(right\_stack\) — ссылка на голову.
Храним два стека — \(left\_stack\) и \(right\_stack\). Левый стек используем для операций \(push\_back\) и \(pop\_back\), правый — для \(push\_front\) и \(pop\_front\). Если мы хотим работать с левым стеком и при этом он оказывается пустым, то достаем нижнюю половину элементов из правого и кладем в левый, воспользовавшись при этом локальным стеком \(local\). Аналогично с правым стеком. Худшее время работы — \(O(n)\).
class Deque:
def __init__(self):
self.left_stack = Stack()
self.right_stack = Stack()
def empty(self):
return self.left_stack.empty() and self.right_stack.empty()
def push_back(self, x):
self.left_stack.push(x)
def pop_back(self):
if self.empty():
return 'UnderflowError'
if self.left_stack.empty():
size = len(self.right_stack.array)
local = Stack()
for _ in range(size // 2):
local.push(self.right_stack.pop())
while not self.right_stack.empty():
self.left_stack.push(self.right_stack.pop())
while not local.empty():
self.right_stack.push(local.pop())
return self.left_stack.pop()
def push_front(self, x):
self.right_stack.push(x)
def pop_front(self):
if self.empty():
return 'UnderflowError'
if self.right_stack.empty():
size = len(self.left_stack.array)
local = Stack()
for _ in range(size // 2):
local.push(self.left_stack.pop())
while not self.left_stack.empty():
self.right_stack.push(self.left_stack.pop())
while not local.empty():
self.left_stack.push(local.pop())
return self.right_stack.pop()