Редактирование: Персистентный стек

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Алгоритм ==
 
== Алгоритм ==
 
+
Будем использовать узел, у которого будет значение и ссылка на прошлую версию стека. При этом сам узел - это версия стека.
 +
  '''struct''' '''Node''':
 +
    '''T''' value
 +
    '''Node''' prev
 
=== Реализация на массиве ===
 
=== Реализация на массиве ===
 
Заведем массив запросов, модифицирующих стек.<br>
 
Заведем массив запросов, модифицирующих стек.<br>
  '''struct''' '''Query''':
 
    '''T''' value
 
    '''uint''' prev
 
 
У каждого элемента массива будет <tex>2</tex> поля: значение в вершине стека и индекс предыдущей версии стека.<br>
 
У каждого элемента массива будет <tex>2</tex> поля: значение в вершине стека и индекс предыдущей версии стека.<br>
 
Тогда операции push и pop будут иметь следующий вид:<br>
 
Тогда операции push и pop будут иметь следующий вид:<br>
Строка 15: Строка 15:
 
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером <tex>i</tex> и копирует элемент, предыдущий для него, результирующий стек будет иметь номер <tex> n + 1 </tex>.
 
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером <tex>i</tex> и копирует элемент, предыдущий для него, результирующий стек будет иметь номер <tex> n + 1 </tex>.
 
   '''T''' pop(i : '''uint'''):
 
   '''T''' pop(i : '''uint'''):
     '''Query''' k = s[i]
+
     '''Node''' k = s[i]
 
     k = s[k.prev]
 
     k = s[k.prev]
 
     push(k.prev, k.value)
 
     push(k.prev, k.value)
Строка 21: Строка 21:
  
 
=== Реализация на списке ===
 
=== Реализация на списке ===
Будем использовать узел, у которого будет значение и ссылка на прошлую версию стека. При этом сам узел - это версия стека.
+
 
  '''struct''' '''Node''':
 
    '''T''' value
 
    '''Node''' prev
 
 
Будем хранить состояния в узлах. Будем возвращать пользователю информацию о текущей вершине.<br>
 
Будем хранить состояния в узлах. Будем возвращать пользователю информацию о текущей вершине.<br>
 
У каждого узла будет <tex>2</tex> поля: значение в вершине стека и ссылка на предыдущую версию стека.<br>
 
У каждого узла будет <tex>2</tex> поля: значение в вершине стека и ссылка на предыдущую версию стека.<br>
Сам персистентный стек будет обозначаться <tex>s</tex>.<br>
+
Сам персистентный стек будет обозначатся <tex>s</tex>.<br>
  
 
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек узла <tex>i</tex>,
 
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек узла <tex>i</tex>,
Строка 38: Строка 35:
 
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в узле <tex>i</tex> и копирует элемент, предыдущий для него.
 
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в узле <tex>i</tex> и копирует элемент, предыдущий для него.
 
   '''pair<T, Stack>''' pop(i : '''Node'''):
 
   '''pair<T, Stack>''' pop(i : '''Node'''):
     '''T''' val = i.value
+
     '''Node''' k = i.prev
     i = i.prev
+
     push(k.prev, k.value)
     '''return''' pair(val, s)
+
     '''return''' pair(i.value, s)
  
 
== Пример ==
 
== Пример ==
Строка 98: Строка 95:
  
  
Выполним <tex>\mathrm{pop}(3)</tex>. Он возвращает <tex>5</tex> и копирует 2-ую вершину.
+
Выполним <tex>\mathrm{pop}(3)</tex>. он возвращает <tex>5</tex> и копирует 2-ую вершину.
 
[[Файл:стек4.png|500px|nothumb|right|]]
 
[[Файл:стек4.png|500px|nothumb|right|]]
 
{| border = 1; cellspacing = 0; class="wikitable"
 
{| border = 1; cellspacing = 0; class="wikitable"
Строка 164: Строка 161:
  
 
== Применение ==
 
== Применение ==
Используя персистентый стек, можно реализовать легко перстистентную очередь (если вспомнить её реализацию на двух стеках). <br>
+
В основном используется когда нужно быстрое обращение по результатам команд добавить/удалить.
См. [[Персистентная очередь]]
 
  
 
== См. также==
 
== См. также==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: