1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''Персистентная очередь''' (англ. ''persistent queue'') {{---}} это [[Очередь|очередь]], реализующая [[Персистентные структуры данных|персистентность]], то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменится.
== Основная идея ==
Понятно, что во время перекопирования могут поступить операции <tex>\mathtt{push}</tex>, а стек <tex>L</tex> в это время потеряет свою структуру, сложить элементы туда мы уже не сможем, значит нужно завести еще один стек <tex>L'</tex>, в который мы и будем складывать новые элементы. После окончания перекопирования мы поменяем ролями <tex>L,L'</tex> и <tex>R,R'</tex>, на первый взгляд, все станет хорошо.
Однако, если реализовать этот алгоритм, мы получим неприятную вещь: старый стек <tex>R</tex> может и не опустошиться за это время, то есть мы получили два стека с выходными данными, а значит, возможен случай (например, если все поступающие операции {{---}} <tex>\mathtt{push}</tex>), когда при следующем перекопировании у нас не будет свободного стека для копировании копирования туда элементов <tex>L</tex>. Для преодоления этой проблемы мы принудительно будем извлекать все элементы из стека <tex>R</tex> во вспомогательный стек <tex>S</tex>, затем копировать элементы из стека <tex>L</tex> в <tex>R</tex>, а затем обратно копировать элементы из стека <tex>S</tex> в <tex>R</tex>. Легко показать, что приведенный алгоритм как раз получает на выходе в <tex>R</tex> все элементы стеков <tex>L,R</tex> в правильном порядке.
Но этого еще недостаточно. Если мы принудительно извлекаем элементы из стека <tex>R</tex>, появляются следующие проблемы:
additionalOperations()
<span style="color:#008000">// Если мы не все перекопировали, то у нас не пуст стек S</span>
recopy = S.size <tex> \ne neq </tex> 0
</code>
=== additionalOperations ===
<code>
* [http://hdl.handle.net/1813/6273 ''Hood R., Melville R.'' Real Time Queue Operations in Pure LISP. {{---}} Cornell University, 1980]
* [http://habrahabr.ru/post/241231 Хабрахабр {{---}} Персистентная очередь]
* [http://codeforces.com/blog/entry/15685 Codeforces {{---}} Персистентная очередь и её друзья]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
[[Категория: Структуры данных]]
