120
правок
Изменения
правки
'''Персистентная очередь''' {{---}} это [[Очередь|очередь]], реализующая персистентность, то есть позволяющая получить доступ ко всем своим предыдущим версиям. Как будет показано далее, можно реализовать функциональную персистентность, то есть каждая ячейка памяти в такой структуре будет инициализирована один раз и в дальнейшем не изменятьсяизменится.
= Основная идея =
Для создания персистентной очереди очень удобно пользоваться ее реализацией на стеках, поскольку стеки легко сделать персистентными, причем в этом случае мы добьемся функциональной персистетнтности. Реализация на двух стеках не подходит для этого, так как в худшем сучае требует <tex>O(n)</tex> времени, а значит и <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>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> в правильном порядке.
<code>
push(x)
'''if''' !recopy:
L.push(x)
'''if''' Rc'.size > 0:
Rc'.pop()
checkRecopy()
'''else''':
L'.push(x)
checkNormal()
<code>
pop()
'''if''' !recopy:
tmp = R.pop()
Rc.pop()
'''if''' Rc'.size > 0:
Rc'.pop()
checkRecopy()
'''return''' tmp
'''else''':
tmp = Rc.pop()
'''if''' toCopy > 0:
toCopy = toCopy - 1
'''else''':
R.pop()
Rc'.pop()
checkRecopy()
recopy = L.size > R.size
'''if''' recopy:
toCopy = R.size
copied = false
toDo = 3
// Пытаемся перекопировать R в T
'''while''' '''not''' copied '''and''' toDo > 0 '''and''' R.size > 0:
T.push(R.pop())
toDo = toDo - 1
// Пытаемся перекопировать L в R и Rc'
'''while''' toDo > 0 '''and''' L.size > 0:
copied = true
x = L.pop()
toDo = toDo - 1
// Пытаемся перекопировать T в R и Rc' с учетом toCopy
'''while''' toDo > 0 '''and''' T.size > 0:
x = T.pop()
'''if''' toCopy > 0:
R.push(x)
Rc'.push(x)
toDo = toDo - 1
// Если все скопировано, то меняем роли L, L' и Rc, Rc'
'''if''' T.size == 0:
swap(L, L')
swap(Rc, Rc')
<code>
push(x)
'''if''' !recopy:
Ln = L.push(x)
Q' = <Ln, L', R, R', T, recopy, toCopy, copied>
'''return''' Q'.checkRecopy()
'''else''':
Ln' = L'.push(x)
Q' = <L, Ln', R, R', T, recopy, toCopy, copied>
<code>
pop()
'''if''' !recopy:
<Rn, x> = R.pop()
Q' = <L, L', Rn, R', T, recopy, toCopy, copied>
'''return''' <Q'.checkRecopy(), x>
'''else''':
<Rn', x> = R'.pop()
curCopy = toCopy
Rn = R
'''if''' toCopy > 0:
curCopy = curCopy - 1
'''else''':
<Rn, x> = Rn.pop()
Q' = <L, L', Rn, Rn', T, recopy, curCopy, copied>
<code>
checkRecopy()
'''if''' L.size > R.size:
Q' = <L, L', R, R', T, true, R.size, false>
'''return''' Q'.checkNormal()
'''else''':
'''return''' <L, L', R, R', T, false, toCopy, copied>
</code>
Tn = T
curCopied = copied
'''while''' '''not''' curCopied '''and''' toDo > 0 '''and''' Rn.size > 0:
<Rn, x> = Rn.pop()
Tn = Tn.push(x)
Ln = L
// Пытаемся перекопировать L в R
'''while''' toDo > 0 '''and''' Ln.size > 0:
curCopied = true
<Ln, x> = Ln.pop()
curCopy = toCopy
// Пытаемся перекопировать T в R с учетом toCopy
'''while''' toDo > 0 '''and''' Tn.size > 0:
<Tn, x> = Tn.pop()
'''if''' curCopy > 0:
Rn = Rn.push(x)
curCopy = curCopy - 1
Ln' = L'
// Если все скопировано, то меняем роли L1, L2
'''if''' T.size == 0:
swap(Ln, Ln')
'''return''' <Ln, Ln', Rn, R', Tn, recopy, curCopy, curCopied>
