120
правок
Изменения
→Реализация на шести стеках: правки
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <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>3 \cdot n + 3</tex> действий на <tex>n + 1</tex> операций с очередью, то есть выполняя 3 дополнительных действия во время операции мы успеем перекопировать все элементы вовремя. Тогда очередь действительно будет выполнять каждое действие за <tex>O(1)</tex> реального времени.
