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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 43 промежуточные версии 6 участников)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
 
[[Файл:deque1.png|thumb|right|200px|Дек]]
 
[[Файл:deque1.png|thumb|right|200px|Дек]]
'''Дек''' (от англ. ''deque'' {{---}} double ended queue) {{---}} структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Дек можно воспринимать как двустороннюю очередь или двусторонний стек. Он имеет следующие операции:
+
'''Дек''' (от англ. ''deque'' {{---}} double ended queue) {{---}} структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO, поэтому на ней можно реализовать как [[Стек | стек]], так и [[Очередь | очередь]]. В первом случае нужно использовать только методы головы или хвоста, во втором {{---}} методы push и pop двух разных концов. Дек можно воспринимать как двустороннюю очередь. Он имеет следующие операции:
 
* <tex> \mathtt{empty} </tex> {{---}} проверка на наличие элементов,
 
* <tex> \mathtt{empty} </tex> {{---}} проверка на наличие элементов,
 
* <tex> \mathtt{pushBack} </tex> (запись в конец) {{---}} операция вставки нового элемента в конец,
 
* <tex> \mathtt{pushBack} </tex> (запись в конец) {{---}} операция вставки нового элемента в конец,
Строка 8: Строка 8:
 
* <tex> \mathtt{popFront} </tex> (снятие с начала) {{---}} операция удаления начального элемента.
 
* <tex> \mathtt{popFront} </tex> (снятие с начала) {{---}} операция удаления начального элемента.
  
==Реализации==
+
== Реализации ==
Дек расходует только <tex>O(n)</tex> памяти, на хранение самих элементов.
+
Дек расходует только <tex>O(n)</tex> памяти, на хранение самих элементов.  
=== На массиве ===
+
=== Простая реализация ===
 +
В данной реализации изначально <tex> \mathtt{head = n - 1} </tex> и <tex> \mathtt{tail = n - 1} </tex>.
 
Ключевые поля:
 
Ключевые поля:
* <tex>\mathtt{d[1\dots n]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,
+
* <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.tail\dots d.head]}</tex>. Если очень много раз добавлять в начало и столько же раз удалять конечные элементы, то скоро мы дойдем до границы, имея немного элементов, при этом добавление в начало вызовет переполнение (в данной реализации во внимание не берется). Если в деке верно равенство <tex>\mathtt{d.tail = d.head}</tex>, то такой дек пуст и изъятие из него может привести к ошибке.
+
Дек состоит из элементов <tex>\mathtt {d[head\dots tail - 1]}</tex>. Если происходит максимум <tex>\mathtt {n}</tex> добавлений, то массив длины <tex>\mathtt {2 \times n}</tex> может вместить в себя все добавленные элементы.
 +
 +
'''boolean''' empty():
 +
  '''return''' head == tail
  
 +
'''function''' pushBack(x : '''T'''):
 +
  d[tail++] = x
  
 +
'''T''' popBack():
 +
  '''if''' (empty())
 +
    '''return''' <span style="color:red">error</span> "underflow"
 +
  '''return''' d[--tail]
 +
 +
'''function''' pushFront(x : '''T'''):
 +
  d[--head] = x
 +
 +
'''T''' popFront():
 +
  '''if''' (empty())
 +
    '''return''' <span style="color:red">error</span> "underflow"
 +
  '''return''' d[head++]
 +
 +
=== Циклический дек на массиве константной длины ===
 +
Во всех циклических реализациях изначально присвоены следующие значения <tex> \mathtt{head = 0} </tex> и <tex> \mathtt{tail = 0} </tex>.
 +
Ключевые поля:
 +
* <tex>\mathtt{d[0\dots n-1]}</tex> {{---}} массив, с помощью которого реализуется дек, способный вместить не более <tex>n</tex> элементов,
 +
* <tex>\mathtt{head}</tex> {{---}} индекс головы дека,
 +
* <tex>\mathtt{tail}</tex> {{---}} индекс хвоста.
 +
 +
Дек состоит из элементов <tex>\mathtt {d[head\dots tail-1]}</tex> или <tex>\mathtt {d[0\dots tail-1]}</tex> и <tex>\mathtt {d[head\dots n-1]}</tex>. Всего он способен вместить не более <tex>n</tex> элементов. В данной реализации учитывается переполнение и правильно обрабатывается изъятие из пустого дека. Недостатком является константная длина массива, хранящего элементы. Все операции выполняются за <tex>O(1)</tex>.
 +
 +
'''function''' pushBack(x : '''T'''):
 +
  '''if''' (head == (tail + 1) % n)
 +
    '''return''' <span style="color:red">error</span> "overflow"
 +
  d[tail] = x
 +
  tail = (tail + 1) % n
 +
 +
'''T''' popBack():
 +
  '''if''' (empty())
 +
    '''return''' <span style="color:red">error</span> "underflow"
 +
  tail = (tail - 1 + n) % n
 +
  '''return''' d[tail]
 +
 +
'''function''' pushFront(x : '''T'''):
 +
  '''if''' (head == (tail + 1) % n)
 +
    '''return''' <span style="color:red">error</span> "overflow"
 +
  head = (head - 1 + n) % n
 +
  d[head] = x
 +
 +
'''T''' popFront():
 +
  '''if''' (empty())
 +
    '''return''' <span style="color:red">error</span> "underflow"
 +
  '''T''' ret = d[head]
 +
  head = (head + 1) % n
 +
  '''return''' ret
 +
 +
=== Циклический дек на динамическом массиве ===
 +
Ключевые поля:
 +
* <tex>\mathtt{n}</tex> {{---}} размер массива,
 +
* <tex>\mathtt{d[0\dots n-1]}</tex> {{---}} массив, в котором хранится дек,
 +
* <tex>\mathtt{newDeque[0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,
 +
* <tex>\mathtt{head}</tex> {{---}} индекс головы дека,
 +
* <tex>\mathtt{tail}</tex> {{---}} индекс хвоста.
 +
 +
Дек состоит из элементов <tex>\mathtt {d[head\dots tail-1]}</tex> или <tex>\mathtt {d[0\dots tail-1]}</tex> и <tex>\mathtt {d[head\dots n-1]}</tex>. Если реализовывать дек на [[Динамический_массив | динамическом массиве]], то мы можем избежать ошибки переполнения. При выполнении операций <tex>\mathtt{pushBack}</tex> и <tex>\mathtt{pushFront}</tex> происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также происходит проверка на избыточность памяти, выделенной под дек при выполнении операций <tex>\mathtt{popBack}</tex> и <tex>\mathtt{popFront}</tex>. Если памяти под дек выделено в четыре раза больше размера дека, то массив сокращается в два раза. Для удобства выделим в отдельную функцию <tex>\mathtt{size}</tex> получение текущего размера дека.
 +
 +
'''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''' <span style="color:red">error</span> "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''' <span style="color:red">error</span> "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
  
Все операции выполняются за <tex>O(1)</tex>.
 
=== На саморасширяющемся массиве ===
 
---
 
 
=== На списке ===
 
=== На списке ===
 
Ключевые поля:
 
Ключевые поля:
Строка 29: Строка 153:
 
* <tex>\mathtt{head}</tex> {{---}} ссылка на голову.
 
* <tex>\mathtt{head}</tex> {{---}} ссылка на голову.
  
Дек очень просто реализуется на списке. Элементы всегда добавляются либо в <tex>\mathtt{tail.prev}</tex>, либо в <tex>\mathtt{head.next}</tex>.
+
Дек очень просто реализуется на [[Список | двусвязном списке]]. Он состоит из элементов <tex>\mathtt {head\dots tail}</tex>. Элементы всегда добавляются либо в <tex>\mathtt{tail.prev}</tex>, либо в <tex>\mathtt{head.next}</tex>. В данной реализации не учитывается изъятие из пустого дека.
 +
 
 +
'''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
 +
 
 
=== На двух стеках ===
 
=== На двух стеках ===
 +
Ключевые поля:
 +
* <tex>\mathtt{leftStack}</tex> {{---}} ссылка на хвост,
 +
* <tex>\mathtt{rightStack}</tex> {{---}} ссылка на голову.
 +
 +
Храним два [[Стек | стека]] — <tex>\mathtt{leftStack}</tex> и <tex>\mathtt{rightStack}</tex>. Левый стек используем для операций <tex>\mathtt{popBack}</tex> и <tex>\mathtt{pushBack}</tex>, правый — для <tex>\mathtt{popFront}</tex> и <tex>\mathtt{pushFront}</tex>. Если мы хотим работать с левым стеком и при этом он оказывается пустым, то достаем нижнюю половину элементов из правого и кладем в левый, воспользовавшись при этом локальным стеком. Аналогично с правым стеком. Худшее время работы — <tex>O(n)</tex>.
 +
 +
'''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()
 +
 +
{{Лемма
 +
|statement=Амортизированная стоимость операции в таком деке {{---}} <tex>O(1)</tex>.
 +
|proof=Воспользуемся методом предоплаты для доказательства. Достаточно доказать, что между двумя балансировками происходит достаточно амортизирующих их операций.
 +
 +
Вначале в обоих стеках пусто, поэтому они сбалансированы. Рассмотрим дек после очередной балансировки, будем использовать две монеты для операций <tex>\mathtt{push}</tex> и <tex>\mathtt{pop}</tex> {{---}} одну для самой операции, а другую {{---}} в качестве резерва.
 +
 +
Разберем худший случай: после очередной балансировки происходит удаление всех элементов только из одного стека. В таком случае при удалении кладем одну резервную монету на элемент из другого стека. Тогда учетная стоимость следующей балансировки равна нулю, поскольку на всех элементах дека лежит по монете.
 +
}}
 +
 +
== См. также ==
 +
* [[Стек]]
 +
* [[Очередь]]
 +
* [[Персистентный дек]]
 +
 +
== Источники информации ==
 +
* [[wikipedia:ru:Двусвязная_очередь|Википедия {{---}} Дек]]
 +
* [[wikipedia:en:Deque|Wikipedia {{---}} Deque]]
 +
* [http://opendatastructures.org/ods-cpp/2_5_Building_Deque_from_Two.html Open Data Structures {{---}} Building a Deque from Two Stacks]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Амортизационный анализ]]

Текущая версия на 19:35, 4 сентября 2022

Определение

Дек

Дек (от англ. 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]

См. также

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