Дек — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 55: Строка 55:
 
* <tex>\mathtt{capacity}</tex> {{---}} размер массива.
 
* <tex>\mathtt{capacity}</tex> {{---}} размер массива.
  
Если реализовывать дек на динамическом массиве, то мы можем избежать ошибки переполнения. При выполнении операций <tex>pushBack</tex> и <tex>pushFront</tex> происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также проверяем, не нужно ли нам уменьшить размер массива при выполнении операций <tex>popBack</tex> и <tex>popFront</tex>. Для удобства выделим в отдельную функцию <tex>size</tex> получение размера дека.
+
Если реализовывать дек на динамическом массиве, то мы можем избежать ошибки переполнения. При выполнении операций <tex>\mathtt{pushBack}/tex> и <tex>\mathtt{pushFront}</tex> происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также проверяем, не нужно ли нам уменьшить размер массива при выполнении операций <tex>\mathtt{popBack}</tex> и <tex>\mathtt{popFront}</tex>. Для удобства выделим в отдельную функцию <tex>\mathtt{size}</tex> получение размера дека.
 
   
 
   
 
  '''int''' size()
 
  '''int''' size()
Строка 122: Строка 122:
 
* <tex>\mathtt{head}</tex> {{---}} ссылка на голову.
 
* <tex>\mathtt{head}</tex> {{---}} ссылка на голову.
  
Дек очень просто реализуется на списке. Элементы всегда добавляются либо в <tex>\mathtt{tail.prev}</tex>, либо в <tex>\mathtt{head.next}</tex>.
+
Дек очень просто реализуется на двусвязном списке. Элементы всегда добавляются либо в <tex>\mathtt{tail.prev}</tex>, либо в <tex>\mathtt{head.next}</tex>. В данной реализации не учитывается пустой дек. 
 +
 
 +
'''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
 +
 
 
=== На двух стеках ===
 
=== На двух стеках ===

Версия 02:02, 6 января 2016

Определение

Дек

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

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

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

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]

Все операции выполняются за [math]O(1)[/math].

На саморасширяющемся массиве

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

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

Если реализовывать дек на динамическом массиве, то мы можем избежать ошибки переполнения. При выполнении операций [math]\mathtt{pushBack}/tex\gt и \lt tex\gt \mathtt{pushFront}[/math] происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также проверяем, не нужно ли нам уменьшить размер массива при выполнении операций [math]\mathtt{popBack}[/math] и [math]\mathtt{popFront}[/math]. Для удобства выделим в отдельную функцию [math]\mathtt{size}[/math] получение размера дека.

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) — конструктор,
  • [math]\mathtt{tail}[/math] — ссылка на хвост,
  • [math]\mathtt{head}[/math] — ссылка на голову.

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

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

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