Дек

Дек (от англ. 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()

Практические задания