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> в правильном для извлечения порядке. Перекопирование начнется, когда появится опасность того, что мы не сможем за оставшиеся <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>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>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>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> действительно находятся в очереди, оставшиеся элементы нужно извлечь без копирования.
