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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Циклический дек на динамическом массиве)
(Реализации)
Строка 10: Строка 10:
 
== Реализации ==
 
== Реализации ==
 
Дек расходует только <tex>O(n)</tex> памяти, на хранение самих элементов.  
 
Дек расходует только <tex>O(n)</tex> памяти, на хранение самих элементов.  
Изначально переменные <tex> \mathtt{head} </tex> и <tex> \mathtt{tail} </tex> должны различаться на единицу, причем <tex> \mathtt{head = tail - 1} </tex>.
+
Изначально переменные <tex> \mathtt{head} </tex> и <tex> \mathtt{tail} </tex> не должны различаться, то есть <tex> \mathtt{head = tail} </tex>.
 
=== Простая реализация ===
 
=== Простая реализация ===
 
Ключевые поля:
 
Ключевые поля:
Строка 17: Строка 17:
 
* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста.
 
* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста.
  
Дек состоит из элементов <tex>\mathtt {d[d.head\dots d.tail]}</tex>. Если происходит максимум <tex>\mathtt {n}</tex> добавлений, то массив длины <tex>\mathtt {2 \times n}</tex> может вместить в себя все добавленные элементы. При этом <tex> \mathtt{d.head = n} </tex> и <tex> \mathtt{d.tail = n + 1} </tex>.
+
Дек состоит из элементов <tex>\mathtt {d[d.head\dots d.tail]}</tex>. Если происходит максимум <tex>\mathtt {n}</tex> добавлений, то массив длины <tex>\mathtt {2 \times n}</tex> может вместить в себя все добавленные элементы. При этом <tex> \mathtt{d.head = n} </tex> и <tex> \mathtt{d.tail = n} </tex>.
 
   
 
   
 
  '''boolean''' empty():
 
  '''boolean''' empty():
   '''return''' (d.head + 1) % n == d.tail
+
   '''return''' d.head == d.tail
  
 
  '''function''' pushBack(x : '''T'''):
 
  '''function''' pushBack(x : '''T'''):
Строка 33: Строка 33:
  
 
  '''function''' pushFront(x : '''T'''):
 
  '''function''' pushFront(x : '''T'''):
 +
  d.head = d.head - 1
 
   d[d.head] = x
 
   d[d.head] = x
  d.head = d.head - 1
 
  
 
  '''T''' popFront():
 
  '''T''' popFront():
 
   '''if''' (empty())  
 
   '''if''' (empty())  
 
     '''return''' <span style="color:red">error</span> "underflow"  
 
     '''return''' <span style="color:red">error</span> "underflow"  
 +
  '''T''' ret = d[d.head]
 
   d.head = d.head + 1
 
   d.head = d.head + 1
   '''return''' d[d.head]
+
   '''return''' ret
  
 
=== Циклический дек на массиве константной длины ===
 
=== Циклический дек на массиве константной длины ===
Строка 51: Строка 52:
  
 
  '''function''' pushBack(x : '''T'''):
 
  '''function''' pushBack(x : '''T'''):
   '''if''' (d.head == d.tail)
+
   '''if''' (d.head == (d.tail + 1) % n)
 
     '''return''' <span style="color:red">error</span> "overflow"
 
     '''return''' <span style="color:red">error</span> "overflow"
 
   d[d.tail] = x
 
   d[d.tail] = x
Строка 63: Строка 64:
  
 
  '''function''' pushFront(x : '''T'''):
 
  '''function''' pushFront(x : '''T'''):
   '''if''' (d.head == d.tail)
+
   '''if''' (d.head == (d.tail + 1) % n)
 
     '''return''' <span style="color:red">error</span> "overflow"
 
     '''return''' <span style="color:red">error</span> "overflow"
 +
  d.head = (d.head - 1 + n) % n
 
   d[d.head] = x
 
   d[d.head] = x
  d.head = (d.head - 1 + n) % n
 
  
 
  '''T''' popFront():
 
  '''T''' popFront():
 
   '''if''' (empty())  
 
   '''if''' (empty())  
 
     '''return''' <span style="color:red">error</span> "underflow"  
 
     '''return''' <span style="color:red">error</span> "underflow"  
 +
  '''T''' ret = d[d.head]
 
   d.head = (d.head + 1) % n
 
   d.head = (d.head + 1) % n
   '''return''' d[d.head]
+
   '''return''' ret
  
 
=== Циклический дек на динамическом массиве ===
 
=== Циклический дек на динамическом массиве ===
Строка 86: Строка 88:
 
  '''int''' size()
 
  '''int''' size()
 
   '''if''' d.tail > d.head
 
   '''if''' d.tail > d.head
     '''return''' n - d.head + d.tail - 1
+
     '''return''' n - d.head + d.tail
 
   '''else'''
 
   '''else'''
     '''return''' d.tail - d.head - 1
+
     '''return''' d.tail - d.head
  
 
  '''function''' pushBack(x : '''T'''):
 
  '''function''' pushBack(x : '''T'''):
Строка 94: Строка 96:
 
     '''T''' newDeque[capacity * 2]
 
     '''T''' newDeque[capacity * 2]
 
     '''for''' i = 0 '''to''' capacity - 1
 
     '''for''' i = 0 '''to''' capacity - 1
       newDeque[i] = d[d.head + 1]
+
       newDeque[i] = d[d.head]
 
       d.head = (d.head + 1) % n
 
       d.head = (d.head + 1) % n
 
     d = newDeque
 
     d = newDeque
 +
    d.head = 0
 
     d.tail = capacity - 1
 
     d.tail = capacity - 1
    d.head = capacity * 2
 
 
     capacity = capacity * 2
 
     capacity = capacity * 2
 
   d[d.tail] = x
 
   d[d.tail] = x
Строка 109: Строка 111:
 
     '''T''' newDeque[capacity / 2]
 
     '''T''' newDeque[capacity / 2]
 
     '''for''' i = 0 '''to''' size()
 
     '''for''' i = 0 '''to''' size()
       newDeque[i] = d[d.head + 1]
+
       newDeque[i] = d[d.head]
 
       d.head = (d.head + 1) % n
 
       d.head = (d.head + 1) % n
 
     d = newDeque
 
     d = newDeque
     d.head = capacity / 2 - 1
+
     d.head = 0
     d.tail = size() + 1
+
     d.tail = size()
 +
    capacity = capacity / 2
 
   d.tail = (d.tail - 1 + n) % n
 
   d.tail = (d.tail - 1 + n) % n
 
   '''return''' d[d.tail]
 
   '''return''' d[d.tail]
Строка 121: Строка 124:
 
     '''T''' newDeque[capacity * 2]
 
     '''T''' newDeque[capacity * 2]
 
     '''for''' i = 0 '''to''' capacity - 1
 
     '''for''' i = 0 '''to''' capacity - 1
       newDeque[i] = d[d.head + 1]
+
       newDeque[i] = d[d.head]
 
       d.head = (d.head + 1) % n
 
       d.head = (d.head + 1) % n
 
     d = newDeque
 
     d = newDeque
 +
    d.head = 0
 
     d.tail = capacity - 1
 
     d.tail = capacity - 1
     d.head = capacity * 2
+
     capacity = capacity * 2
 +
  d.head = (d.head - 1 + n) % n
 
   d[d.head] = x
 
   d[d.head] = x
  d.head = (d.head - 1 + n) % n
 
  
 
  '''T''' popFront():
 
  '''T''' popFront():
Строка 135: Строка 139:
 
     '''T''' newDeque[capacity / 2]
 
     '''T''' newDeque[capacity / 2]
 
     '''for''' i = 0 '''to''' size()
 
     '''for''' i = 0 '''to''' size()
       newDeque[i] = d[d.head + 1]
+
       newDeque[i] = d[d.head]
 
       d.head = (d.head + 1) % n
 
       d.head = (d.head + 1) % n
 
     d = newDeque
 
     d = newDeque
     d.head = capacity / 2 - 1
+
     d.head = 0
     d.tail = size() + 1
+
     d.tail = size()
 +
    capacity = capacity / 2
 +
  '''T''' ret = d[d.head]
 
   d.head = (d.head + 1) % n
 
   d.head = (d.head + 1) % n
   '''return''' d[d.head]
+
   '''return''' ret
  
 
=== На списке ===
 
=== На списке ===

Версия 00:42, 8 января 2016

Определение

Дек

Дек (от англ. 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} [/math] и [math] \mathtt{tail} [/math] не должны различаться, то есть [math] \mathtt{head = tail} [/math].

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

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

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

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

boolean empty():
  return d.head == d.tail
function pushBack(x : T):
  d[d.tail] = x
  d.tail = d.tail + 1
T popBack():
  if (empty()) 
    return error "underflow" 
  d.tail = d.tail - 1
  return d[d.tail]
function pushFront(x : T):
  d.head = d.head - 1
  d[d.head] = x
T popFront():
  if (empty()) 
    return error "underflow" 
  T ret = d[d.head]
  d.head = d.head + 1
  return ret

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

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

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

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

function pushBack(x : T):
  if (d.head == (d.tail + 1) % n)
    return error "overflow"
  d[d.tail] = x
  d.tail = (d.tail + 1) % n
T popBack():
  if (empty()) 
    return error "underflow" 
  d.tail = (d.tail - 1 + n) % n
  return d[d.tail]
function pushFront(x : T):
  if (d.head == (d.tail + 1) % n)
    return error "overflow"
  d.head = (d.head - 1 + n) % n
  d[d.head] = x
T popFront():
  if (empty()) 
    return error "underflow" 
  T ret = d[d.head]
  d.head = (d.head + 1) % n
  return ret

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

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

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

Дек состоит из элементов [math]\mathtt {d[d.head\dots d.tail]}[/math] или [math]\mathtt {d[0\dots d.tail]}[/math] и [math]\mathtt {d[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 d.tail > d.head
    return n - d.head + d.tail
  else
    return d.tail - d.head
function pushBack(x : T):
  if (d.head == d.tail)
    T newDeque[capacity * 2]
    for i = 0 to capacity - 1
      newDeque[i] = d[d.head]
      d.head = (d.head + 1) % n
    d = newDeque
    d.head = 0
    d.tail = capacity - 1
    capacity = capacity * 2
  d[d.tail] = x
  d.tail = (d.tail + 1) % n
T popBack():
  if (empty()) 
    return error "underflow"
  if (size() < capacity / 4)
    T newDeque[capacity / 2]
    for i = 0 to size()
      newDeque[i] = d[d.head]
      d.head = (d.head + 1) % n
    d = newDeque
    d.head = 0
    d.tail = size()
    capacity = capacity / 2
  d.tail = (d.tail - 1 + n) % n
  return d[d.tail]
function pushFront(x : T):
  if (d.head == d.tail)
    T newDeque[capacity * 2]
    for i = 0 to capacity - 1
      newDeque[i] = d[d.head]
      d.head = (d.head + 1) % n
    d = newDeque
    d.head = 0
    d.tail = capacity - 1
    capacity = capacity * 2
  d.head = (d.head - 1 + n) % n
  d[d.head] = x
T popFront():
  if (empty()) 
    return error "underflow" 
  if (size() < capacity / 4)
    T newDeque[capacity / 2]
    for i = 0 to size()
      newDeque[i] = d[d.head]
      d.head = (d.head + 1) % n
    d = newDeque
    d.head = 0
    d.tail = size()
    capacity = capacity / 2
  T ret = d[d.head]
  d.head = (d.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 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], однако, амортизационная стоимость операции — [math]O(1)[/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()

См. также

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