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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 19: Строка 19:
 
перевыделять память и копировать все элементы.
 
перевыделять память и копировать все элементы.
  
'''boolean''' empty():
+
'''boolean''' empty():
 
   '''return''' d.head%n+1 == d.tail
 
   '''return''' d.head%n+1 == d.tail
  
'''function''' pushBack(x : '''T'''):
+
'''function''' pushBack(x : '''T'''):
 
   '''if''' (d.head == d.tail)
 
   '''if''' (d.head == d.tail)
 
     '''return''' error "overflow"
 
     '''return''' error "overflow"
Строка 28: Строка 28:
 
     d.tail = (d.tail - 2 + n) % n + 1
 
     d.tail = (d.tail - 2 + n) % n + 1
  
'''T''' popBack():
+
'''T''' popBack():
 
   '''if''' (empty())  
 
   '''if''' (empty())  
 
     '''return''' error "underflow"  
 
     '''return''' error "underflow"  
Строка 34: Строка 34:
 
   '''return''' d[d.tail]
 
   '''return''' d[d.tail]
  
'''function''' pushFront(x : '''T'''):
+
'''function''' pushFront(x : '''T'''):
 
   '''if''' (d.head == d.tail)
 
   '''if''' (d.head == d.tail)
 
     '''return''' error "overflow"
 
     '''return''' error "overflow"
Строка 40: Строка 40:
 
     d.head = d.head % n + 1
 
     d.head = d.head % n + 1
  
'''T''' popFront():
+
'''T''' popFront():
 
   '''if''' (empty())  
 
   '''if''' (empty())  
 
     '''return''' error "underflow"  
 
     '''return''' error "underflow"  

Версия 15:54, 4 января 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].

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

---

На списке

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

  • 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].

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