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

Версия 14:25, 10 января 2016

Содержание

1 Определение
2 Реализации
3 См. также
4 Источники информации

Определение

Дек

Дек (от англ. 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{d.head = n} [/math] и [math] \mathtt{d.tail = n} [/math]. Ключевые поля:

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

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

boolean empty():
  return head == tail

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

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

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

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

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

Во всех циклических реализациях изначально присвоены следующие значения [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[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{head}[/math] — индекс головы дека,
[math]\mathtt{tail}[/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 = 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 size = size()
    for i = 0 to size - 1
      newDeque[i] = d[head]
      head = (head + 1) % n
    d = newDeque
    head = 0
    tail = size
    n = 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 = 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 size = size()
    for i = 0 to size - 1
      newDeque[i] = d[head]
      head = (head + 1) % n
    d = newDeque
    head = 0
    tail = size
    n = 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()

См. также

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

@@ Строка 14: / Строка 14: @@
 Ключевые поля:
 * <tex>\mathtt{d[0\dots 2 \times n - 1]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,
-* <tex>\mathtt{d.head}</tex> {{---}} индекс головы дека,
+* <tex>\mathtt{head}</tex> {{---}} индекс головы дека,
-* <tex>\mathtt{d.tail}</tex> {{---}} индекс хвоста.
+* <tex>\mathtt{tail}</tex> {{---}} индекс хвоста.
-Дек состоит из элементов <tex>\mathtt {d[d.head\dots d.tail - 1]}</tex>. Если происходит максимум <tex>\mathtt {n}</tex> добавлений, то массив длины <tex>\mathtt {2 \times n}</tex> может вместить в себя все добавленные элементы.
+Дек состоит из элементов <tex>\mathtt {d[head\dots tail - 1]}</tex>. Если происходит максимум <tex>\mathtt {n}</tex> добавлений, то массив длины <tex>\mathtt {2 \times n}</tex> может вместить в себя все добавленные элементы.
   '''boolean''' empty():
-    '''return''' d.head == d.tail
+    '''return''' head == tail
   '''function''' pushBack(x : '''T'''):
-    d[d.tail] = x
+    d[tail] = x
-    d.tail = d.tail + 1
+    tail++
   '''T''' popBack():
     '''if''' (empty())
       '''return''' <span style="color:red">error</span> "underflow"
-    d.tail = d.tail - 1
+    tail--
-    '''return''' d[d.tail]
+    '''return''' d[tail]
   '''function''' pushFront(x : '''T'''):
-    d.head = d.head - 1
+    head--
     d[d.head] = x
@@ Строка 39: / Строка 39: @@
     '''if''' (empty())
       '''return''' <span style="color:red">error</span> "underflow"
-    '''T''' ret = d[d.head]
+    '''T''' ret = d[head]
-    d.head = d.head + 1
+    head++
     '''return''' ret

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

Версия 14:25, 10 января 2016

Содержание

Определение

Реализации

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

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

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

На списке

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

См. также

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты