Изменения

Перейти к: навигация, поиск

Очередь

2007 байт убрано, 20:38, 7 июня 2013
Реализация на шести стеках: правки
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с <tex>O(1)</tex> истинного времени на операцию.
Сначала будем действовать аналогично случаю с двумя стеками. Пусть у нас есть стек <tex>L</tex> для операций <tex>push</tex> и стек <tex>R</tex> для операций <tex>pop</tex>. К моменту опустошения стека <tex>R</tex> нам нужно успеть получить стек <tex>R'</tex>, содержащий текущие элементы стека <tex>L</tex> в правильном для извлечения порядке. Перекопирование (''recopy mode'') начнется, когда появится опасность того, что мы не сможем за оставшиеся <tex>R.size</tex> операций <tex>pop</tex> со стеком <tex>R</tex> перекопировать стек <tex>L</tex> в новый стек <tex>R'</tex>. Очевидно, это ситуация <tex>L.size>R.size</tex>, пусть такое состояние отражает специальная переменная логического типа <tex>recopy</tex>.
Понятно, что во время перекопирования могут поступить операции <tex>push</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</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>toCopy</tex>, которая показывает, сколько корректных элементов находится в стеке <tex>T</tex> и уменьшается при каждом извлечении из <tex>T</tex> или операции <tex>pop</tex>. К счастью, все некорректные элементы будут нарастать с дна стека, так что мы никогда не извлечем некорректный элемент, если <tex>toCopy>0</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>T</tex>, <tex>n<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>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>empty</tex> не меняет очередь, то есть никакие дополнительные действия не совершаются. Пусть за <tex>n</tex> следующих за активацией меняющих операций (<tex>push, pop</tex>) поступило <tex>x</tex> операций <tex>pop</tex>, <tex>n - x</tex> операций <tex>push</tex>. Очевидно, что после перекопирования в новых стеках окажется: в <tex>L</tex> <tex>n-x</tex>, <tex>R</tex> <tex>2 \ cdot n + 1 - x = (n - x) + (n + 1)</tex> то есть до следующего перекопирования еще <tex>n+2</tex> операции. С другой стороны, стек <tex>Rc</tex> содержал всего <tex>n</tex> элементов, так что мы можем почистить их, просто удаляя по одному элементу при каждой операции в обычном режиме.
Итак, очередь будет состоять из шести стеков <tex>L,L',R,Rc,Rc',T</tex>, а также двух внутренних переменных <tex>recopy, toCopy</tex>, которые нужны для корректности перекопирования.
Инвариант нашей очереди (обычный режим):
# <tex>L.size \leqslant R.size</tex>
# <tex>Rc</tex> {{---}} копия <tex>R</tex>
# <tex>Rc'</tex>
Очередь будет работать в двух режимах:
# Обычный режим, кладем в <tex>L</tex>, извлекаем из <tex>R</tex> и из <tex>Rc</tex> для поддержания порядка.
#
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Если мы использовали стек <tex>L</tex> для операций <tex>push</tex> и стек <tex>R</tex> для операций <tex>pop</tex>, то для перекопирования мы должны заменить текущий стек <tex>R</tex> на новый стек <tex>R'</tex>, который содержит сначала все элементы <tex>L</tex> в обратном порядке, а затем все элементы <tex>R</tex> в прямом порядке. Этого можно добиться, если сначала извлечь все элементы <tex>R</tex> во вспомогательный стек <tex>T</tex>, затем извлечь все элементы <tex>L</tex> в стек <tex>R</tex>, а затем обратно извлечь весь стек <tex>T</tex> в <tex>R</tex>. Поскольку мы выполняем эти действия не сразу, а во время выполнения обычных операций с очередью, нам нужно уметь обрабатывать операции <tex>push</tex>, для этого будем класть поступающие элементы во вспомогательный стек <tex>L'</tex>, а для операций <tex>pop</tex> будем использовать не стек <tex>R</tex>, который во время перекопирования потерял свою структуру, а его копию <tex>Rc</tex>, остающуюся неизменной во время перекопирования. Чтобы сохранить информацию о том, сколько элементов мы уже извлекли из <tex>Rc</tex>, будем использовать счетчик <tex>toCopy</tex>, который показывает, сколько элементов из скопированных в <tex>T</tex> из <tex>R</tex> действительно находятся в очереди, оставшиеся элементы нужно извлечь без копирования.
 
Для такой реализации будем использовать стеки <tex>L_1, L_2, R, Rc_1, Rc_2, T</tex>, причем стеки <tex>L_1, L_2</tex> используются для операций <tex>push</tex>, стек <tex>R</tex> используется для операций <tex>pop</tex>, стеки <tex>Rc_1, Rc_2</tex> используются в качестве копий стека <tex>R</tex> для операций <tex>pop</tex> при перекопировании, стек <tex>T</tex> используется как временное хранилище элементов <tex>R</tex>.
 
В каждый момент времени в очереди зафиксировано, какой <tex>L</tex> из стеков <tex>L_1</tex> и <tex>L_2</tex> используется для помещения туда элементов, пришедших с операцией <tex>push</tex>, а также какой <tex>Rc</tex> из стеков <tex>Rc_1</tex> и <tex>Rc_2</tex> является в данный момент точной копией стека <tex>R</tex>.
 
Также очередь будет запоминать, находится ли она сейчас в режиме перекопирования (''recopy mode''), в который переходит из обычного режима, когда после очередной операции в стеке <tex>L</tex> становится больше элементов, чем в стеке <tex>R</tex>. При активации инициализируется счетчик <tex>toCopy</tex>, показывающий, сколько находится неизвлеченных элементов в стеке <tex>Rc</tex>.
 
Обрабатываем поступающие дальше операции следующим образом: <tex>push</tex> кладет элемент в парный нашему стеку <tex>L</tex> стек <tex>L'</tex>, а <tex>pop</tex> извлекает элемент только из <tex>Rc</tex>, при этом уменьшая счетчик <tex>toCopy</tex>. <tex>empty</tex> в этом режиме всегда возвращает <tex>false</tex>, так как при перекопировании <tex>n+1>0</tex> элементов из <tex>L</tex> всегда остаются в очереди, так как извлечение происходит только из <tex>Rc</tex>.
 
Пусть в этот момент в стеке <tex>R</tex>, а значит, и в стеке <tex>Rc</tex> находились <tex>n</tex> элементов, тогда в стеке <tex>L</tex> их <tex>n+1</tex>. Заметим, что мы можем корректно обработать все операции <tex>push</tex> и первые <tex>n</tex> операций <tex>pop</tex>, то есть у нас есть на перекопирование не меньше <tex>n+1</tex> операции вместе с активирующей.
 
Корректной ситуация станет, когда в стеках <tex>R</tex> и парном стеке <tex>Rc'</tex> окажутся все находящиеся на момент активации в очереди и не извлеченные после активации элементы, причем в порядке, правильном для извлечения.
 
Чтобы получить корректную ситуацию и перейти в обычный режим, нужно:
# Извлечь весь стек <tex>R</tex> в стек <tex>T</tex>, <tex>n</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>Rc'</tex> текущей копией стека <tex>R</tex>, а <tex>L'</tex> {{---}} текущим стеком для операций <tex>push</tex>, <tex>2</tex> действия.
Таким образом, получили <tex>3 \cdot n + 3</tex> действий на <tex>n + 1</tex> операций с очередью, то есть выполняя 3 дополнительных действия во время операции мы успеем перекопировать все элементы вовремя. Тогда очередь действительно будет выполнять каждое действие за <tex>O(1)</tex> реального времени.
120
правок

Навигация