Дек

Определение

Дек

Дек (от англ. deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO, поэтому на ней можно реализовать как стек, так и очередь. В первом случае нужно использовать только методы головы или хвоста, во втором — методы push и pop двух разных концов. Дек можно воспринимать как двустороннюю очередь. Он имеет следующие операции:

• [math] \mathtt{empty} [/math] — проверка на наличие элементов,
• [math] \mathtt{pushBack} [/math] (запись в конец) — операция вставки нового элемента в конец,
• [math] \mathtt{popBack} [/math] (снятие с конца) — операция удаления конечного элемента,
• [math] \mathtt{pushFront} [/math] (запись в начало) — операция вставки нового элемента в начало,
• [math] \mathtt{popFront} [/math] (снятие с начала) — операция удаления начального элемента.

Реализации

Дек расходует только [math]O(n)[/math] памяти, на хранение самих элементов.

Простая реализация

В данной реализации изначально [math] \mathtt{head = n - 1} [/math] и [math] \mathtt{tail = n - 1} [/math]. Ключевые поля:

• [math]\mathtt{d[0\dots 2 \times n - 1]}[/math] — массив, с помощью которого реализуется дек, способный вместить не более [math]n[/math] элементов,
• [math]\mathtt{head}[/math] — индекс головы дека,
• [math]\mathtt{tail}[/math] — индекс хвоста.

Дек состоит из элементов [math]\mathtt {d[head\dots tail - 1]}[/math]. Если происходит максимум [math]\mathtt {n}[/math] добавлений, то массив длины [math]\mathtt {2 \times n}[/math] может вместить в себя все добавленные элементы.

boolean empty():
  return head == tail

function pushBack(x : T):
  d[tail++] = x

T popBack():
  if (empty()) 
    return error "underflow" 
  return d[--tail]

function pushFront(x : T):
  d[--head] = x

T popFront():
  if (empty()) 
    return error "underflow" 
  return d[head++]

Циклический дек на массиве константной длины

Во всех циклических реализациях изначально присвоены следующие значения [math] \mathtt{head = 0} [/math] и [math] \mathtt{tail = 0} [/math]. Ключевые поля:

• [math]\mathtt{d[0\dots n-1]}[/math] — массив, с помощью которого реализуется дек, способный вместить не более [math]n[/math] элементов,
• [math]\mathtt{head}[/math] — индекс головы дека,
• [math]\mathtt{tail}[/math] — индекс хвоста.

Дек состоит из элементов [math]\mathtt {d[head\dots tail-1]}[/math] или [math]\mathtt {d[0\dots tail-1]}[/math] и [math]\mathtt {d[head\dots n-1]}[/math]. Всего он способен вместить не более [math]n[/math] элементов. В данной реализации учитывается переполнение и правильно обрабатывается изъятие из пустого дека. Недостатком является константная длина массива, хранящего элементы. Все операции выполняются за [math]O(1)[/math].

function pushBack(x : T):
  if (head == (tail + 1) % n)
    return error "overflow"
  d[tail] = x
  tail = (tail + 1) % n

T popBack():
  if (empty()) 
    return error "underflow" 
  tail = (tail - 1 + n) % n
  return d[tail]

function pushFront(x : T):
  if (head == (tail + 1) % n)
    return error "overflow"
  head = (head - 1 + n) % n
  d[head] = x

T popFront():
  if (empty()) 
    return error "underflow" 
  T ret = d[head]
  head = (head + 1) % n
  return ret

Циклический дек на динамическом массиве

Ключевые поля:

• [math]\mathtt{n}[/math] — размер массива,
• [math]\mathtt{d[0\dots n-1]}[/math] — массив, в котором хранится дек,
• [math]\mathtt{newDeque[0\dots newSize]}[/math] — временный массив, где хранятся элементы после перекопирования,
• [math]\mathtt{head}[/math] — индекс головы дека,
• [math]\mathtt{tail}[/math] — индекс хвоста.

Дек состоит из элементов [math]\mathtt {d[head\dots tail-1]}[/math] или [math]\mathtt {d[0\dots tail-1]}[/math] и [math]\mathtt {d[head\dots n-1]}[/math]. Если реализовывать дек на динамическом массиве, то мы можем избежать ошибки переполнения. При выполнении операций [math]\mathtt{pushBack}[/math] и [math]\mathtt{pushFront}[/math] происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также происходит проверка на избыточность памяти, выделенной под дек при выполнении операций [math]\mathtt{popBack}[/math] и [math]\mathtt{popFront}[/math]. Если памяти под дек выделено в четыре раза больше размера дека, то массив сокращается в два раза. Для удобства выделим в отдельную функцию [math]\mathtt{size}[/math] получение текущего размера дека.

int size()
  if tail > head
    return n - head + tail
  else
    return tail - head

function pushBack(x : T):
  if (head == (tail + 1) % n)
    T newDeque[n * 2]
    for i = 0 to n - 2
      newDeque[i] = d[head]
      head = (head + 1) % n
    d = newDeque
    head = 0
    tail = n - 1
    n *= 2
  d[tail] = x
  tail = (tail + 1) % n

T popBack():
  if (empty()) 
    return error "underflow"
  if (size() < n / 4)
    T newDeque[n / 2]
    int dequeSize = size()
    for i = 0 to dequeSize - 1
      newDeque[i] = d[head]
      head = (head + 1) % n
    d = newDeque
    head = 0
    tail = dequeSize
    n /= 2
  tail = (tail - 1 + n) % n
  return d[tail]

function pushFront(x : T):
  if (head == (tail + 1) % n)
    T newDeque[n * 2]
    for i = 0 to n - 2
      newDeque[i] = d[head]
      head = (head + 1) % n
    d = newDeque
    head = 0
    tail = n - 1
    n *= 2
  head = (head - 1 + n) % n
  d[head] = x

T popFront():
  if (empty()) 
    return error "underflow" 
  if (size() < n / 4)
    T newDeque[n / 2]
    int dequeSize = size()
    for i = 0 to dequeSize - 1
      newDeque[i] = d[head]
      head = (head + 1) % n
    d = newDeque
    head = 0
    tail = dequeSize
    n /= 2
  T ret = d[head]
  head = (head + 1) % n
  return ret

На списке

Ключевые поля:

• ListItem(data : T, next : ListItem, prev : ListItem) — конструктор,
• [math]\mathtt{tail}[/math] — ссылка на хвост,
• [math]\mathtt{head}[/math] — ссылка на голову.

Дек очень просто реализуется на двусвязном списке. Он состоит из элементов [math]\mathtt {head\dots tail}[/math]. Элементы всегда добавляются либо в [math]\mathtt{tail.prev}[/math], либо в [math]\mathtt{head.next}[/math]. В данной реализации не учитывается изъятие из пустого дека.

function initialize():
  head = ListItem(null, null, null)
  tail = ListItem(null, null, head)
  head.next = tail

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

На двух стеках

Ключевые поля:

• [math]\mathtt{leftStack}[/math] — ссылка на хвост,
• [math]\mathtt{rightStack}[/math] — ссылка на голову.

Храним два стека — [math]\mathtt{leftStack}[/math] и [math]\mathtt{rightStack}[/math]. Левый стек используем для операций [math]\mathtt{popBack}[/math] и [math]\mathtt{pushBack}[/math], правый — для [math]\mathtt{popFront}[/math] и [math]\mathtt{pushFront}[/math]. Если мы хотим работать с левым стеком и при этом он оказывается пустым, то достаем нижнюю половину элементов из правого и кладем в левый, воспользовавшись при этом локальным стеком. Аналогично с правым стеком. Худшее время работы — [math]O(n)[/math].

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 / 2 
      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 popFront():
  if not rightStack.empty()
    return rightStack.pop() 
  else
    int size = leftStack.size()
    Stack<T> local
    for i = 0 to size / 2 
      local.push(leftStack.pop())
    while not leftStack.empty()
      rightStack.push(leftStack.pop())
    while not local.empty()
      leftStack.push(local.pop())
    return rightStack.pop()

Лемма:

Амортизированная стоимость операции в таком деке — [math]O(1)[/math].

Доказательство:

[math]\triangleright[/math]

Воспользуемся методом предоплаты для доказательства. Достаточно доказать, что между двумя балансировками происходит достаточно амортизирующих их операций. Вначале в обоих стеках пусто, поэтому они сбалансированы. Рассмотрим дек после очередной балансировки, будем использовать две монеты для операций [math]\mathtt{push}[/math] и [math]\mathtt{pop}[/math] — одну для самой операции, а другую — в качестве резерва. Разберем худший случай: после очередной балансировки происходит удаление всех элементов только из одного стека. В таком случае при удалении кладем одну резервную монету на элемент из другого стека. Тогда учетная стоимость следующей балансировки равна нулю, поскольку на всех элементах дека лежит по монете. Ч. т. д.

[math]\triangleleft[/math]

См. также

• Стек
• Очередь
• Персистентный дек

Источники информации

• Википедия — Дек
• Wikipedia — Deque
• Open Data Structures — Building a Deque from Two Stacks