Изменения

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

Очередь

2421 байт добавлено, 05:31, 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> в обратном порядке, а затем все элементы <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>R</tex>, а значит, и в стеке <tex>Rc</tex> находились <tex>n</tex> элементов, тогда в стеке <tex>L</tex> их <tex>n+1</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>RcL</tex>всегда остаются в очереди, а у нас еще есть элементы в так как извлечение происходит только из <tex>LRc</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> окажутся все находящиеся на момент активации в очереди и не извлеченные после активации элементы, причем в порядке, правильном для извлечения.
Чтобы получить корректную ситуацию и перейти в обычный режим, нужно:
120
правок

Навигация