Очередь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(additionalOperations: правки)
Строка 104: Строка 104:
 
Понятно, что во время перекопирования могут поступить операции <tex>push</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</tex>, и вроде бы все станет хорошо.
 
Понятно, что во время перекопирования могут поступить операции <tex>push</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</tex>, и вроде бы все станет хорошо.
  
Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек <tex>R</tex> может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит возможен случай (например, когда все поступающие операции <tex>push</tex>), когда при следующем перекопировании у нас не будет свободного стека для копирования туда элементов <tex>L</tex>. Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем копировать элементы из стека <tex>L</tex> в <tex>R</tex>, а затем обратно копировать элементы из стека <tex>T</tex> в <tex>R</tex>. Легко показать, что приведенный алгоритм как раз получает на выходе в <tex>R</tex> все элементы стеков <tex>L,R</tex> в правильном порядке.
+
Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек <tex>R</tex> может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит, возможен случай (например, если все поступающие операции {{---}} <tex>push</tex>), когда при следующем перекопировании у нас не будет свободного стека для копировании туда элементов <tex>L</tex>. Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем копировать элементы из стека <tex>L</tex> в <tex>R</tex>, а затем обратно копировать элементы из стека <tex>T</tex> в <tex>R</tex>. Легко показать, что приведенный алгоритм как раз получает на выходе в <tex>R</tex> все элементы стеков <tex>L,R</tex> в правильном порядке.
  
 
Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека <tex>R</tex>, появляются следующие проблемы:
 
Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека <tex>R</tex>, появляются следующие проблемы:
 
# Что вернуть при операции <tex>pop</tex>? Для этого заведем себе стек <tex>Rc</tex> {{---}} копию стека <tex>R</tex>, из которого мы и будем извлекать требуемые элементы.
 
# Что вернуть при операции <tex>pop</tex>? Для этого заведем себе стек <tex>Rc</tex> {{---}} копию стека <tex>R</tex>, из которого мы и будем извлекать требуемые элементы.
# Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия <tex>Rc'</tex>, в которую мы будем копировать все элементы, которые мы копируем в <tex>R</tex>, а по окончании перекопирования поменяем ролями стеки <tex>Rc, Rc'</tex>, как мы делали со стеками <tex>L, L'</tex>.
+
# Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия <tex>Rc'</tex> для копирования всех элементов, которые мы копируем в <tex>R</tex>, а по окончании перекопирования поменяем ролями стеки <tex>Rc, Rc'</tex>, как мы делали со стеками <tex>L, L'</tex>.
# Как учесть, что во время перекопирования часть элементов была извлечена из <tex>Rc</tex>? Для этого заведем специальную переменную <tex>toCopy</tex>, которая показывает, сколько корректных элементов находится в стеке <tex>T</tex> и уменьшается при каждом извлечении из <tex>T</tex> или операции <tex>pop</tex>. К счастью, все некорректные элементы будут нарастать с дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</tex>.
+
# Как учесть, что во время перекопирования часть элементов была извлечена из <tex>Rc</tex>? Для этого заведем специальную переменную <tex>toCopy</tex>, которая показывает, сколько корректных элементов находится в стеке <tex>T</tex>, и уменьшается при каждом извлечении из <tex>T</tex> или операции <tex>pop</tex>. К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</tex>.
  
 
Теперь может возникнуть проблема с непустым <tex>Rc</tex> после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.
 
Теперь может возникнуть проблема с непустым <tex>Rc</tex> после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.
  
Пусть на начало перекопирования в стеке <tex>R</tex> содержится <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находится <tex>n+1</tex> элементов. Мы корректно можем обработать любое количество операций <tex>push</tex>, а также <tex>n</tex> операций <tex>pop</tex>. Заметим, что операция <tex>empty</tex> во время перекопирования всегда возвращает <tex>false</tex>, так как мы не можем извлекать элементы из стека <tex>L</tex>, который не пустой. Таким образом, вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать <tex>n + 1</tex> операцию.
+
Пусть на начало перекопирования в стеке <tex>R</tex> содержится <tex>n</tex> элементов, тогда в стеке <tex>L</tex> находится <tex>n+1</tex> элементов. Мы корректно можем обработать любое количество операций <tex>push</tex>, а также <tex>n</tex> операций <tex>pop</tex>. Заметим, что операция <tex>empty</tex> во время перекопирования всегда возвращает <tex>false</tex>, так как мы не можем извлекать элементы из стека <tex>L</tex>, который не пустой. Таким образом вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать <tex>n + 1</tex> операцию.
  
 
Посмотрим на дополнительные действия, которые нам предстоят:
 
Посмотрим на дополнительные действия, которые нам предстоят:
Строка 119: Строка 119:
 
# Переместить содержимое <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n + 1</tex> действий.
 
# Переместить содержимое <tex>L</tex> в стеки <tex>R, Rc'</tex>, <tex>n + 1</tex> действий.
 
# Переместить первые <tex>toCopy</tex> элементов из <tex>T</tex> в <tex>R, Rc'</tex>, <tex>n</tex> действий.
 
# Переместить первые <tex>toCopy</tex> элементов из <tex>T</tex> в <tex>R, Rc'</tex>, <tex>n</tex> действий.
# Поменять ролями стеки <tex>Rc, Rc'</tex>, а также <tex>L, L'</tex>, <tex>2</tex> действия.
+
# Поменять ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>, <tex>2</tex> действия.
  
Таким образом, получили <tex>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, или <tex>3=O(1)</tex> дополнительных действия на операцию в режиме перекопирования, что и требовалось.
+
Таким образом, получили <tex>3 \cdot n + 3</tex> дополнительных действия за <tex>n + 1</tex> операций, или <tex>3=O(1)</tex> дополнительных действий на операцию в режиме перекопирования, что и требовалось.
  
 
Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция <tex>empty</tex> не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за <tex>n</tex> следующих за активацией меняющих операций (<tex>push, pop</tex>) поступило <tex>x</tex> операций <tex>pop</tex>, <tex>n - x</tex> операций <tex>push</tex>. Очевидно, что после перекопирования в новых стеках окажется: <tex>n-x</tex> элементов в <tex>L</tex>, <tex>2 \cdot n + 1 - x = (n - x) + (n + 1)</tex> элементов в <tex>R</tex>, то есть до следующего перекопирования еще <tex>n+2</tex> операции. С другой стороны, стек <tex>Rc</tex> содержал всего <tex>n</tex> элементов, так что мы можем очистить его, просто удаляя по одному элементу при каждой операции в обычном режиме.
 
Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция <tex>empty</tex> не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за <tex>n</tex> следующих за активацией меняющих операций (<tex>push, pop</tex>) поступило <tex>x</tex> операций <tex>pop</tex>, <tex>n - x</tex> операций <tex>push</tex>. Очевидно, что после перекопирования в новых стеках окажется: <tex>n-x</tex> элементов в <tex>L</tex>, <tex>2 \cdot n + 1 - x = (n - x) + (n + 1)</tex> элементов в <tex>R</tex>, то есть до следующего перекопирования еще <tex>n+2</tex> операции. С другой стороны, стек <tex>Rc</tex> содержал всего <tex>n</tex> элементов, так что мы можем очистить его, просто удаляя по одному элементу при каждой операции в обычном режиме.
Строка 148: Строка 148:
 
После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>recopy=T.size==0</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>.
 
После операции в режиме перекопирования следует проверка на завершение перекопирования (<tex>recopy=T.size==0</tex>), а при завершении меняются ролями стеки <tex>Rc, Rc'</tex>, <tex>L, L'</tex>.
  
Пусть наша очередь <tex>Q</tex> имеет стеки <tex>L, L', R, Rc, Rc', T</tex>, а также переменные <tex>recopy</tex> и <tex>toCopy</tex>, тогда следующий псевдокод выполняет требуемые операции.
+
Следующий псевдокод выполняет требуемые операции:
 
=== empty ===
 
=== empty ===
 
<code>
 
<code>
 
  empty()
 
  empty()
     return !recopy and R.size == 0
+
     '''return''' !recopy '''and''' R.size == 0
 
</code>
 
</code>
 
=== push ===
 
=== push ===
 
<code>
 
<code>
 
  push(x)
 
  push(x)
     if !recopy
+
     '''if''' !recopy:
 
       L.push(x)
 
       L.push(x)
       if Rc'.size > 0
+
       '''if''' Rc'.size > 0:
 
           Rc'.pop()
 
           Rc'.pop()
 
       checkRecopy()
 
       checkRecopy()
     else
+
     '''else''':
 
       L'.push(x)
 
       L'.push(x)
 
       checkNormal()
 
       checkNormal()
Строка 169: Строка 169:
 
<code>
 
<code>
 
  pop()
 
  pop()
     if !recopy
+
     '''if''' !recopy:
 
       tmp = R.pop()
 
       tmp = R.pop()
 
       Rc.pop()
 
       Rc.pop()
       if Rc'.size > 0
+
       '''if''' Rc'.size > 0:
 
           Rc'.pop()
 
           Rc'.pop()
 
       checkRecopy()
 
       checkRecopy()
       return tmp
+
       '''return''' tmp
     else
+
     '''else''':
 
       tmp = Rc.pop()
 
       tmp = Rc.pop()
 
       toCopy = toCopy - 1
 
       toCopy = toCopy - 1
 
       checkNormal()
 
       checkNormal()
       return tmp
+
       '''return''' tmp
 
</code>
 
</code>
 
=== checkRecopy ===
 
=== checkRecopy ===
Строка 186: Строка 186:
 
  checkRecopy()     
 
  checkRecopy()     
 
     recopy = L.size > R.size
 
     recopy = L.size > R.size
     if recopy
+
     '''if''' recopy:
 
       toCopy = R.size
 
       toCopy = R.size
 
       additionalOperations()
 
       additionalOperations()
Строка 195: Строка 195:
 
     additionalOperations()
 
     additionalOperations()
 
     // Если мы не все перекопировали, то у нас не пуст стек T
 
     // Если мы не все перекопировали, то у нас не пуст стек T
     recopy = T.size != 0
+
     recopy = T.size <tex> \ne </tex> 0
 
</code>
 
</code>
 
=== additionalOperations ===
 
=== additionalOperations ===
Строка 203: Строка 203:
 
     toDo = 3
 
     toDo = 3
 
     // Пытаемся перекопировать R в T
 
     // Пытаемся перекопировать R в T
     while toDo > 0 and R.size > 0
+
     '''while''' toDo > 0 '''and''' R.size > 0:
 
       T.push(R.pop())
 
       T.push(R.pop())
 
       toDo = toDo - 1
 
       toDo = toDo - 1
 
     // Пытаемся перекопировать L в R и Rc'
 
     // Пытаемся перекопировать L в R и Rc'
     while toDo > 0 and L.size > 0
+
     '''while''' toDo > 0 '''and''' L1.size > 0:
 
       x = L.pop()
 
       x = L.pop()
 
       R.push(x)
 
       R.push(x)
Строка 213: Строка 213:
 
       toDo = toDo - 1
 
       toDo = toDo - 1
 
     // Пытаемся перекопировать T в R и Rc' с учетом toCopy
 
     // Пытаемся перекопировать T в R и Rc' с учетом toCopy
     while toDo > 0 and T.size > 0
+
     '''while''' toDo > 0 '''and''' T.size > 0:
 
       x = T.pop()
 
       x = T.pop()
       if toCopy > 0
+
       '''if''' toCopy > 0:
 
           R.push(x)
 
           R.push(x)
 
           Rc'.push(x)
 
           Rc'.push(x)
Строка 221: Строка 221:
 
       toDo = toDo - 1
 
       toDo = toDo - 1
 
     // Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2
 
     // Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2
     if T.size == 0
+
     '''if''' T.size = 0:
 
       swap(L, L')
 
       swap(L, L')
 
       swap(Rc, Rc')
 
       swap(Rc, Rc')

Версия 21:45, 7 июня 2013

Определение

Fifo new.png

Очередь (Queue)  — это структура данных, добавление и удаление элементов в которой происходит путём операций Push и Pop соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (first-in, first-out — FIFO). У очереди имеется голова (head) и хвост (tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.

  • [math]push[/math] (запись в очередь) - операция вставки нового элемента.
  • [math]pop[/math] (снятие с очереди) - операция удаления нового элемента.
  • [math]empty[/math] - проверка очереди на наличие в ней элементов

Реализация на массиве

Очередь, способную вместить не более [math]n[/math] элементов, можно реализовать с помощью массива [math]elements[1..n][/math]. Она будет обладать следующими полями:

  • [math]head[/math] (голова очереди)
  • [math]tail[/math] (хвост очереди)
  • [math]size[/math] (размер очереди)

push

push(x)
   elements[tail] = x
   tail = (tail + 1) % elements.length
   size++

pop

pop()
   if !empty()
      x = elements[head]
      head = (head + 1) % elements.length
      size--
      return x

empty

empty()
   return size == 0

Из-за того что нам не нужно перевыделять память, каждая операция выполняется за [math]O(1)[/math] времени.

Плюсы:

- прост в разработке
- по сравнению с реализацией на списке, есть незначительная экономия памяти

Минусы:

- количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива)
- при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив

Реализация на списке

Для данной реализации очереди необходимо создать список ([math]list[/math]) и операции работы на созданном списке.

Реализация очереди на односвязном списке:

list

  • [math]x.value[/math] - поле, в котором хранится значение элемента
  • [math]x.next[/math] - указатель на следующий элемент очереди

push

push(x)
   element = tail
   tail = new list(x, NULL)
   if size == 0
      head = tail
   else 
      element.next = tail
   size++

pop

pop()
   if empty()
      return
   element = head
   head = head.next
   size--
   return element

empty

empty()
   return size == 0
Queue.png

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

Минусы:

  • Память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве

Реализация на двух стеках

Очередь можно реализовать на двух стеках [math]leftStack[/math] и [math]rightStack[/math]. Один из стеков [math](leftStack)[/math] будем использовать для операции [math]push[/math], другой для операции [math]pop[/math]. При этом, если при попытке извлечения элемента из [math]rightStack[/math] он оказался пустым, просто перенесем все элементы из [math]leftStack[/math] в него (при этом элементы в [math]rightStack[/math] получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а [math]leftStack[/math] станет пустым).

  • [math]pushLeft[/math] и [math]pushRight[/math] - функции, реализующие операцию [math]push[/math] для соответствующего стека;
  • [math]popLeft[/math] и [math]popRight[/math] - аналогично операции [math]pop[/math].

push

push(x)
   pushLeft(x)

pop

if !rigthStack.empty()
   return popRight()

else
   while !leftStack.empty()
      pushRight(popLeft())
   return popRight()

При выполнении операции [math]push[/math] будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию [math]pop[/math] из первого стека, третью во второй стек на финальный [math]pop[/math]. Тогда для операций [math]pop[/math] учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции [math]push[/math].

Таким образом, для каждой операции требуется [math]O(1)[/math] монет, а значит, амортизационная стоимость операций [math]O(1)[/math].

Минусы:

  • Если [math]leftStack[/math] не пуст, то операция [math]pop[/math] может выполняться [math]O(n)[/math] времени, в отличии от других реализаций, где [math]pop[/math] всегда выполняется за [math]O(1)[/math]

Реализация на шести стеках

Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим [math]O(n)[/math] времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с [math]O(1)[/math] истинного времени на операцию.

Сначала будем действовать аналогично случаю с двумя стеками. Пусть у нас есть стек [math]L[/math] для операций [math]push[/math] и стек [math]R[/math] для операций [math]pop[/math]. К моменту опустошения стека [math]R[/math] нам нужно успеть получить стек [math]R'[/math], содержащий текущие элементы стека [math]L[/math] в правильном для извлечения порядке. Перекопирование (recopy mode) начнется, когда появится опасность того, что мы не сможем за оставшиеся [math]R.size[/math] операций [math]pop[/math] со стеком [math]R[/math] перекопировать стек [math]L[/math] в новый стек [math]R'[/math]. Очевидно, это ситуация [math]L.size\gt R.size[/math], пусть такое состояние отражает специальная переменная логического типа [math]recopy[/math].

Понятно, что во время перекопирования могут поступить операции [math]push[/math], а стек [math]L[/math] в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек [math]L'[/math], в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями [math]L,L'[/math] и [math]R,R'[/math], и вроде бы все станет хорошо.

Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек [math]R[/math] может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит, возможен случай (например, если все поступающие операции — [math]push[/math]), когда при следующем перекопировании у нас не будет свободного стека для копировании туда элементов [math]L[/math]. Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека [math]R[/math] во вспомогательный стек [math]T[/math], затем копировать элементы из стека [math]L[/math] в [math]R[/math], а затем обратно копировать элементы из стека [math]T[/math] в [math]R[/math]. Легко показать, что приведенный алгоритм как раз получает на выходе в [math]R[/math] все элементы стеков [math]L,R[/math] в правильном порядке.

Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека [math]R[/math], появляются следующие проблемы:

  1. Что вернуть при операции [math]pop[/math]? Для этого заведем себе стек [math]Rc[/math] — копию стека [math]R[/math], из которого мы и будем извлекать требуемые элементы.
  2. Как поддерживать корректность такой копии? Поскольку этот стек нужен только для перекопирования, а во время него он занят, нужна запасная копия [math]Rc'[/math] для копирования всех элементов, которые мы копируем в [math]R[/math], а по окончании перекопирования поменяем ролями стеки [math]Rc, Rc'[/math], как мы делали со стеками [math]L, L'[/math].
  3. Как учесть, что во время перекопирования часть элементов была извлечена из [math]Rc[/math]? Для этого заведем специальную переменную [math]toCopy[/math], которая показывает, сколько корректных элементов находится в стеке [math]T[/math], и уменьшается при каждом извлечении из [math]T[/math] или операции [math]pop[/math]. К счастью, все некорректные элементы будут нарастать со дна стека, так что мы никогда не извлечем некорректный элемент, если [math]toCopy\gt 0[/math].

Теперь может возникнуть проблема с непустым [math]Rc[/math] после завершения перекопирования. Покажем, что мы всегда успеем его опустошить, если будем использовать дополнительное извлечение из него при каждой операции в обычном режиме, для этого полностью проанализируем алгоритм.

Пусть на начало перекопирования в стеке [math]R[/math] содержится [math]n[/math] элементов, тогда в стеке [math]L[/math] находится [math]n+1[/math] элементов. Мы корректно можем обработать любое количество операций [math]push[/math], а также [math]n[/math] операций [math]pop[/math]. Заметим, что операция [math]empty[/math] во время перекопирования всегда возвращает [math]false[/math], так как мы не можем извлекать элементы из стека [math]L[/math], который не пустой. Таким образом вместе с операцией, активирующей перекопирование, мы гарантированно можем корректно обработать [math]n + 1[/math] операцию.

Посмотрим на дополнительные действия, которые нам предстоят:

  1. Переместить содержимое [math]R[/math] в [math]T[/math], [math]n[/math] действий.
  2. Переместить содержимое [math]L[/math] в стеки [math]R, Rc'[/math], [math]n + 1[/math] действий.
  3. Переместить первые [math]toCopy[/math] элементов из [math]T[/math] в [math]R, Rc'[/math], [math]n[/math] действий.
  4. Поменять ролями стеки [math]Rc, Rc'[/math], [math]L, L'[/math], [math]2[/math] действия.

Таким образом, получили [math]3 \cdot n + 3[/math] дополнительных действия за [math]n + 1[/math] операций, или [math]3=O(1)[/math] дополнительных действий на операцию в режиме перекопирования, что и требовалось.

Теперь рассмотрим, как изменились наши стеки за весь период перекопирования. Договоримся, что операция [math]empty[/math] не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за [math]n[/math] следующих за активацией меняющих операций ([math]push, pop[/math]) поступило [math]x[/math] операций [math]pop[/math], [math]n - x[/math] операций [math]push[/math]. Очевидно, что после перекопирования в новых стеках окажется: [math]n-x[/math] элементов в [math]L[/math], [math]2 \cdot n + 1 - x = (n - x) + (n + 1)[/math] элементов в [math]R[/math], то есть до следующего перекопирования еще [math]n+2[/math] операции. С другой стороны, стек [math]Rc[/math] содержал всего [math]n[/math] элементов, так что мы можем очистить его, просто удаляя по одному элементу при каждой операции в обычном режиме.

Итак, очередь [math]Q[/math] будет состоять из шести стеков [math]L,L',R,Rc,Rc',T[/math], а также двух внутренних переменных [math]recopy, toCopy[/math], которые нужны для корректности перекопирования.

Инвариант очереди (обычный режим):

  1. [math]L.size \leqslant R.size[/math]
  2. [math]R.size = 0 \equiv Q.size = 0[/math]
  3. [math]Rc[/math] — копия [math]R[/math]
  4. [math]Rc'.size \lt R.size - L.size[/math]
  5. [math]L'.size = 0, T.size = 0[/math]

Тогда к следующему перекопированию ([math]L.size=R.size+1[/math]) мы гарантированно будем иметь пустые стеки [math]L',T,Rc'[/math], которые нам понадобятся.

Инвариант очереди (режим перекопирования):

  1. [math]Rc.size = toCopy[/math]
  2. Если [math]L.size = 0[/math], то первые [math]toCopy[/math] элементов [math]T[/math] — корректны, то есть действительно содержатся в очереди.

Очередь будет работать в двух режимах:

  1. Обычный режим, кладем в [math]L[/math], извлекаем из [math]R[/math] и из [math]Rc, Rc'[/math] для поддержания порядка, операция [math]empty = (R.size = 0)[/math].
  2. Режим перекопирования, кладем в [math]L'[/math], извлекаем из [math]Rc[/math], [math]empty=false[/math], совершаем дополнительные действия.

Также после операции в обычном режиме следует проверка на активацию перекопирования([math]recopy = (L.size \gt R.size)[/math]), если это так, [math]toCopy=R.size, recopy=true[/math], совершается первый набор дополнительных действий.

После операции в режиме перекопирования следует проверка на завершение перекопирования ([math]recopy=T.size==0[/math]), а при завершении меняются ролями стеки [math]Rc, Rc'[/math], [math]L, L'[/math].

Следующий псевдокод выполняет требуемые операции:

empty

empty()
   return !recopy and R.size == 0

push

push(x)
   if !recopy:
      L.push(x)
      if Rc'.size > 0:
         Rc'.pop()
      checkRecopy()
   else:
      L'.push(x)
      checkNormal()

pop

pop()
   if !recopy:
      tmp = R.pop()
      Rc.pop()
      if Rc'.size > 0:
         Rc'.pop()
      checkRecopy()
      return tmp
   else:
      tmp = Rc.pop()
      toCopy = toCopy - 1
      checkNormal()
      return tmp

checkRecopy

checkRecopy()    
   recopy = L.size > R.size
   if recopy:
      toCopy = R.size
      additionalOperations()

checkNormal

checkNormal()
   additionalOperations()
   // Если мы не все перекопировали, то у нас не пуст стек T
   recopy = T.size [math] \ne [/math] 0

additionalOperations

additionalOperations()
   // Нам достаточно 3 операций на вызов
   toDo = 3
   // Пытаемся перекопировать R в T
   while toDo > 0 and R.size > 0:
      T.push(R.pop())
      toDo = toDo - 1
   // Пытаемся перекопировать L в R и Rc'
   while toDo > 0 and L1.size > 0:
      x = L.pop()
      R.push(x)
      Rc'.push(x)
      toDo = toDo - 1
   // Пытаемся перекопировать T в R и Rc' с учетом toCopy
   while toDo > 0 and T.size > 0:
      x = T.pop()
      if toCopy > 0:
         R.push(x)
         Rc'.push(x)
         toCopy = toCopy - 1
      toDo = toDo - 1
   // Если все скопировано, то меняем роли L1, L2 и Rc1, Rc2
   if T.size = 0:
      swap(L, L')
      swap(Rc, Rc')

Плюсы:

Минусы:

  • Больше константа на операции.
  • Больше расход памяти.
  • Больше сложность реализации.

См. также

Ссылки