Очередь на шести стеках

TL;DR

Обычная очередь на двух стеках работает амортизированно за [math]\displaystyle{ O(1) }[/math], но отдельная операция может стоить [math]\displaystyle{ \Theta(n) }[/math]: когда выходной стек пуст, приходится разом перевернуть весь входной. Очередь на шести стеках (real-time queue) распределяет этот перенос на маленькие порции — не более 3 действий за операцию — и тем самым даёт [math]\displaystyle{ O(1) }[/math] в худшем случае на каждую операцию, то есть работает в реальном времени. Стеки [math]\displaystyle{ L, L', R, R_c, R_c', S }[/math] и переменные [math]\displaystyle{ \mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied} }[/math] следят за фоновым перекопированием, а копии [math]\displaystyle{ R_c, R_c' }[/math] обслуживают pop, пока выход перестраивается. Из этой конструкции одной заменой [math]\displaystyle{ (R_c, R_c') \to R' }[/math] получается персистентная очередь на пяти стеках: каждая версия занимает [math]\displaystyle{ O(1) }[/math] новых ячеек, а операции остаются [math]\displaystyle{ O(1) }[/math] в худшем случае.

Инфобокс

Свойство	Значение
Класс	Очередь (FIFO) в реальном времени; на стеках
Порядок доступа	FIFO
Худший случай	[math]\displaystyle{ O(1) }[/math] на push, pop, empty
Амортизированный	[math]\displaystyle{ O(1) }[/math] (совпадает с худшим — амортизация не нужна)
Память	[math]\displaystyle{ O(n) }[/math] под элементы; [math]\displaystyle{ \le 3 }[/math] переноса на операцию (не более 6 стеков)
Стеки	[math]\displaystyle{ L, L', R, R_c, R_c', S }[/math]
Переменные	[math]\displaystyle{ \mathtt{recopy} }[/math], [math]\displaystyle{ \mathtt{toCopy} }[/math], [math]\displaystyle{ \mathtt{copied} }[/math]
Режимы	обычный и перекопирования
Сравнение	2 стека — амортизированно [math]\displaystyle{ O(1) }[/math], худший [math]\displaystyle{ \Theta(n) }[/math]; 6 стеков — худший [math]\displaystyle{ O(1) }[/math]; 5 стеков — ещё и персистентность
Авторы идеи	Hood, Melville (1980); персистентный вариант — учебная традиция ИТМО, Okasaki
Где встречается	функциональные языки, персистентные структуры, системы реального времени, версионирование

Определения

Очередь (см. Очередь (план)) — коллекция с порядком FIFO: push добавляет в конец, pop забирает из начала. Реализуется кольцевым буфером, списком или двумя стеками.

Реализация на двух стеках. Входной стек [math]\displaystyle{ L }[/math] принимает push, выходной [math]\displaystyle{ R }[/math] обслуживает pop. Когда [math]\displaystyle{ R }[/math] пуст, все элементы [math]\displaystyle{ L }[/math] переворачиваются в [math]\displaystyle{ R }[/math]: [math]\displaystyle{ L }[/math] разбирается сверху, каждый элемент кладётся в [math]\displaystyle{ R }[/math]. Разовый перенос стоит [math]\displaystyle{ \Theta(n) }[/math], поэтому [math]\displaystyle{ O(1) }[/math] здесь — амортизированный, а не худший.

Очередь в реальном времени (real-time queue). Очередь, у которой каждая операция выполняется за [math]\displaystyle{ O(1) }[/math] в худшем случае, без «долгих» вызовов. Синоним: очередь с ограниченным (постоянным) временем отклика.

Перекопирование (recopy mode). Фоновый режим, в котором часть работы переноса [math]\displaystyle{ (L \to R) }[/math] выполняется маленькими порциями параллельно с обычными операциями. Начинается, когда [math]\displaystyle{ L.size \gt R.size }[/math], и заканчивается, когда служебный стек [math]\displaystyle{ S }[/math] опустеет.

Шесть стеков. Основные: [math]\displaystyle{ L }[/math] — вход обычного режима, [math]\displaystyle{ R }[/math] — выход обычного режима. Вспомогательные: [math]\displaystyle{ L' }[/math] — вход во время перекопирования; [math]\displaystyle{ S }[/math] — буфер двойного переворота; [math]\displaystyle{ R_c }[/math] — копия текущего [math]\displaystyle{ R }[/math] (из неё идут pop во время перекопирования); [math]\displaystyle{ R_c' }[/math] — копия строящегося [math]\displaystyle{ R }[/math].

Переменные состояния. [math]\displaystyle{ \mathtt{recopy} }[/math] — булев флаг режима; [math]\displaystyle{ \mathtt{toCopy} }[/math] — сколько элементов в [math]\displaystyle{ S }[/math] ещё «корректны» (принадлежат очереди); [math]\displaystyle{ \mathtt{copied} }[/math] — начат ли перенос [math]\displaystyle{ L \to R }[/math].

Персистентная структура данных. Структура, к которой доступны все прошлые версии. Функциональная персистентность — сильнейшая форма: ячейка памяти инициализируется один раз и больше не меняется, поэтому версии разделяют неизменяемые данные. См. Персистентные структуры данных.

Персистентная очередь на пяти стеках. Вариант, где пара [math]\displaystyle{ (R_c, R_c') }[/math] заменена одной неизменяемой версией [math]\displaystyle{ R' }[/math], а версия очереди описывается записью [math]\displaystyle{ Q = \langle L, L', R, R', S, \mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied}\rangle }[/math].

Обозначения. [math]\displaystyle{ n }[/math] — число элементов очереди; [math]\displaystyle{ |X| }[/math] — размер стека [math]\displaystyle{ X }[/math]; [math]\displaystyle{ \log }[/math] — двоичный. Стеки трактуются как последовательности «дно … верх».

Мотивация и интуиция

Очередь на двух стеках красива, но у неё есть скрытый дефект: один pop на пустом [math]\displaystyle{ R }[/math] тянет за собой перенос всех элементов — [math]\displaystyle{ \Theta(n) }[/math] работы и, что важнее для персистентности, [math]\displaystyle{ \Theta(n) }[/math] новых ячеек памяти в одной операции. Для систем реального времени (планировщики, обработка сигналов, сетевые буферы) задержка должна быть ограничена сверху; один вызов, пропорциональный размеру структуры, недопустим. См. рис. 1.

Рис. 1. Перенос [math]\displaystyle{ L \to R }[/math] происходит разом и даёт пик [math]\displaystyle{ \Theta(n) }[/math]; задача — размазать его по операциям так, чтобы каждая стоила [math]\displaystyle{ O(1) }[/math].

Ключевая идея: дробить дорогую работу. Пока очередь обслуживает обычные push/pop, она потихоньку готовит новый выходной стек, выполняя ровно 3 действия за операцию. Если начать перекопирование заранее — когда [math]\displaystyle{ |L| }[/math] лишь на единицу превысил [math]\displaystyle{ |R| }[/math], — то на перенос останется ровно столько операций, сколько нужно, и «долгих» вызовов не будет вовсе.

Почему именно шесть стеков? Во время переноса стек [math]\displaystyle{ L }[/math] разбирается, поэтому новые push надо куда-то девать — так появляется [math]\displaystyle{ L' }[/math]. Пока строится новый [math]\displaystyle{ R }[/math], старый выход ещё должен отвечать на pop — так появляется копия [math]\displaystyle{ R_c }[/math]. У копии тоже есть версия «на будущее» — [math]\displaystyle{ R_c' }[/math]. Наконец, старый [math]\displaystyle{ R }[/math] может не успеть опустеть (если операций push было много), поэтому его содержимое временно уводят в буфер [math]\displaystyle{ S }[/math], чтобы через двойной переворот вернуть уже над новыми элементами [math]\displaystyle{ L }[/math]. Итого [math]\displaystyle{ L, L', R, R_c, R_c', S }[/math] — шесть стеков.

Устройство

Очередь хранит шесть стеков и три переменные; вместе они реализуют FIFO с постоянным временем отклика (см. рис. 2).

Рис. 2. [math]\displaystyle{ L }[/math] — вход обычного режима, [math]\displaystyle{ R }[/math] — выход; [math]\displaystyle{ L' }[/math] принимает вход во время перекопирования, [math]\displaystyle{ R_c }[/math] и [math]\displaystyle{ R_c' }[/math] — копии выхода, [math]\displaystyle{ S }[/math] — буфер двойного переворота.

Работа идёт в двух режимах (см. рис. 3):

• Обычный режим. push кладёт в [math]\displaystyle{ L }[/math], pop берёт из [math]\displaystyle{ R }[/math] (и синхронно из [math]\displaystyle{ R_c }[/math]); [math]\displaystyle{ \mathtt{empty} = (R = \varnothing) }[/math]. После каждой операции проверка [math]\displaystyle{ \mathtt{recopy} \leftarrow (|L| \gt |R|) }[/math].
• Режим перекопирования. push кладёт в [math]\displaystyle{ L' }[/math], pop берёт из [math]\displaystyle{ R_c }[/math]; [math]\displaystyle{ \mathtt{empty} = \text{false} }[/math]; каждая операция делает не более 3 переносов. Режим длится, пока [math]\displaystyle{ S \neq \varnothing }[/math].

Рис. 3. Переключение режимов: вход в перекопирование по [math]\displaystyle{ \lvert L\rvert \gt \lvert R\rvert }[/math], выход — по пустому [math]\displaystyle{ S }[/math].

Перекопирование не должно затянуться дольше, чем простоит старый выход, — иначе не хватит свободного стека. Гарантию дают инварианты (см. рис. 4). В обычном режиме: [math]\displaystyle{ L }[/math] и [math]\displaystyle{ R }[/math] — половины очереди, [math]\displaystyle{ |L| \le |R| }[/math], [math]\displaystyle{ R = \varnothing \iff Q = \varnothing }[/math], [math]\displaystyle{ R_c }[/math] — копия [math]\displaystyle{ R }[/math], а [math]\displaystyle{ R_c' }[/math] и [math]\displaystyle{ S }[/math] подчищены так, что [math]\displaystyle{ |R_c'| \le |R| - |L| }[/math] и [math]\displaystyle{ |L'| = |S| = 0 }[/math]. В режиме перекопирования: [math]\displaystyle{ |R_c| \ge \mathtt{toCopy} }[/math] (равенство, пока из [math]\displaystyle{ S }[/math] не переносили корректных элементов), и если [math]\displaystyle{ |L| = 0 }[/math], то либо первые [math]\displaystyle{ \mathtt{toCopy} }[/math] элементов [math]\displaystyle{ S }[/math] корректны, либо (при [math]\displaystyle{ \mathtt{toCopy} \le 0 }[/math]) стек [math]\displaystyle{ R }[/math] уже содержит весь правый кусок очереди в правильном порядке.

Рис. 4. Инвариант [math]\displaystyle{ \lvert R_c'\rvert \le \lvert R\rvert - \lvert L\rvert }[/math] гарантирует, что остаток [math]\displaystyle{ R_c' }[/math] рассосётся по элементу за операцию до следующего перекопирования.

Операции и алгоритмы

Ниже — операции очереди. Обозначим [math]\displaystyle{ |X| = \mathtt{X.size} }[/math]; стек как объект со стандартными [math]\displaystyle{ \mathtt{push}, \mathtt{pop} }[/math]; [math]\displaystyle{ \mathtt{swap} }[/math] меняет местами переменные-стеки.

Операция: Empty

Идея. В обычном режиме очередь пуста тогда и только тогда, когда пуст [math]\displaystyle{ R }[/math]; в режиме перекопирования очередь заведомо непуста (см. лемму о корректности Empty ниже).

Операция Empty(Q)
Вход:  очередь Q
Выход: true, если элементов нет
Инвариант: R = ∅ ⟺ Q = ∅ (в обычном режиме)
Сложность: O(1) времени, O(1) памяти

1  return (not Q.recopy) and (|R| = 0)

Крайние случаи. Во время перекопирования Empty всегда false, даже если все «старые» элементы уже извлечены: за время переноса выполняется не более [math]\displaystyle{ n }[/math] извлечений, а в очереди было [math]\displaystyle{ 2n+1 }[/math] элементов, поэтому неперекопированный остаток лежит в [math]\displaystyle{ R_c }[/math] или [math]\displaystyle{ R }[/math].

Операция: Push

Идея. В обычном режиме элемент идёт в [math]\displaystyle{ L }[/math]; попутно подчищаем [math]\displaystyle{ R_c' }[/math] и проверяем, не пора ли начать перекопирование. В режиме перекопирования элемент идёт в [math]\displaystyle{ L' }[/math] (стек [math]\displaystyle{ L }[/math] сейчас разбирается), и продолжаем фоновую работу.

Операция Push(Q, x)
Вход:  очередь Q; x — элемент
Выход: x добавлен в конец очереди
Инвариант: в обычном режиме Q = R (сверху вниз) ++ reverse(L)
Сложность: O(1) в худшем случае (не более 3 переносов)

1  if not Q.recopy
2      push(L, x)
3      if |Rc'| > 0
4          pop(Rc')                       # рассасываем остаток копии
5      Check-Recopy(Q)
6  else
7      push(L', x)
8      Check-Normal(Q)

Крайние случаи. Если очередь была пуста, push запускает перекопирование (так как [math]\displaystyle{ |L| = 1 \gt 0 = |R| }[/math]), но завершает его сразу же за один вызов, попадая в обычный режим.

Операция: Pop

Идея. В обычном режиме берём верх [math]\displaystyle{ R }[/math] (это самый старый элемент) и синхронно чистим [math]\displaystyle{ R_c }[/math]. В режиме перекопирования элемент берётся из копии [math]\displaystyle{ R_c }[/math]; если [math]\displaystyle{ \mathtt{toCopy} \gt 0 }[/math], он «оплачен» корректным элементом из [math]\displaystyle{ S }[/math], иначе берём и из перестраиваемого [math]\displaystyle{ R }[/math].

Операция Pop(Q)
Вход:  очередь Q
Выход: самый старый элемент; error, если очередь пуста
Инвариант: возвращаемый элемент — минимальный по времени поступления
Сложность: O(1) в худшем случае (не более 3 переносов)

1  if not Q.recopy
2      x ← pop(R)
3      pop(Rc)
4      if |Rc'| > 0
5          pop(Rc')
6      Check-Recopy(Q)
7      return x
8  else
9      x ← pop(Rc)
10     if Q.toCopy > 0
11         Q.toCopy ← Q.toCopy − 1
12     else
13         pop(R)
14         pop(Rc')
15     Check-Normal(Q)
16     return x

Крайние случаи. Если в режиме перекопирования [math]\displaystyle{ \mathtt{toCopy} }[/math] дошёл до нуля, значит, оставшиеся старые элементы уже продублированы в [math]\displaystyle{ R }[/math]; тогда pop синхронно снимает элемент из [math]\displaystyle{ R_c }[/math], [math]\displaystyle{ R }[/math] и [math]\displaystyle{ R_c' }[/math]. Обращение к пустой очереди — ошибка (underflow), как и в любой очереди.

Операция: Check-Recopy

Идея. После операции в обычном режиме проверить, не перерос ли вход выход; если да — переключиться в режим перекопирования и сделать первый пакет переносов.

Операция Check-Recopy(Q)
1  Q.recopy ← (|L| > |R|)
2  if Q.recopy
3      Q.toCopy ← |R|                    # столько старых элементов ещё «в деле»
4      Q.copied ← false                 # перенос L → R ещё не начат
5      Check-Normal(Q)

Операция: Check-Normal

Идея. Доделать пакет переносов; режим перекопирования продолжается, пока непуст [math]\displaystyle{ S }[/math].

Операция Check-Normal(Q)
1  Additional-Operations(Q)
2  Q.recopy ← (|S| ≠ 0)                 # S пуст — перекопирование завершено

Операция: Additional-Operations

Идея. За один вызов выполнить не более 3 действий над вспомогательными стеками (см. рис. 5). Четыре фазы:

1. [math]\displaystyle{ R \to S }[/math] — пока [math]\displaystyle{ R }[/math] не пуст и [math]\displaystyle{ \mathtt{copied} = \text{false} }[/math], перекладывать [math]\displaystyle{ R }[/math] в [math]\displaystyle{ S }[/math] (временный переворот выхода).
2. [math]\displaystyle{ L \to R, R_c' }[/math] — как только начали, ставим [math]\displaystyle{ \mathtt{copied} \leftarrow \text{true} }[/math]; каждый элемент [math]\displaystyle{ L }[/math] идёт и в [math]\displaystyle{ R }[/math], и в [math]\displaystyle{ R_c' }[/math].
3. [math]\displaystyle{ S \to R, R_c' }[/math] — первые [math]\displaystyle{ \mathtt{toCopy} }[/math] элементов [math]\displaystyle{ S }[/math] возвращаются в [math]\displaystyle{ R }[/math] и [math]\displaystyle{ R_c' }[/math] (двойной переворот восстанавливает порядок [math]\displaystyle{ R }[/math] и кладёт его над элементами [math]\displaystyle{ L }[/math]); остальные (уже логически извлечённые) отбрасываются.
4. Смена ролей — если [math]\displaystyle{ S }[/math] пуст: [math]\displaystyle{ \mathtt{swap}(L, L') }[/math], [math]\displaystyle{ \mathtt{swap}(R_c, R_c') }[/math].

Операция Additional-Operations(Q)
Вход:  очередь Q в режиме перекопирования
Выход: сделано не более 3 переносов
Инвариант: фазы 1–4 выполняются строго по порядку
Сложность: O(1) (счётчик toDo = 3)

1  toDo ← 3
2  while (not Q.copied) and toDo > 0 and |R| > 0
3      push(S, pop(R))                   # фаза 1: R → S
4      toDo ← toDo − 1
5  while toDo > 0 and |L| > 0
6      Q.copied ← true
7      x ← pop(L)
8      push(R, x)                        # фаза 2: L → R
9      push(Rc', x)                      #         и L → Rc'
10     toDo ← toDo − 1
11 while toDo > 0 and |S| > 0
12     x ← pop(S)                        # фаза 3: S → R, Rc'
13     if Q.toCopy > 0
14         push(R, x)
15         push(Rc', x)
16         Q.toCopy ← Q.toCopy − 1
17     toDo ← toDo − 1
18 if |S| = 0
19     swap(L, L')                       # фаза 4: смена ролей
20     swap(Rc, Rc')

Разбор. Точные состояния стеков на примере push(1..7) и последующих pop приведены в разделе «Трассировка примера». Ключевой момент фазы 3 — двойной переворот [math]\displaystyle{ R \to S \to R }[/math]: он возвращает относительный порядок старого выхода неизменным, но ставит его поверх элементов [math]\displaystyle{ L }[/math]; поскольку старые элементы и есть «перед» очереди, pop из нового [math]\displaystyle{ R }[/math] выдаёт FIFO.

Крайние случаи. Если [math]\displaystyle{ R }[/math] уже пуст, фаза 1 пропускается и работа сразу начинается с фазы 2. Если [math]\displaystyle{ L }[/math] пуст, фаза 2 пропускается. Если [math]\displaystyle{ \mathtt{toCopy} = 0 }[/math], элементы [math]\displaystyle{ S }[/math] просто извлекаются и выбрасываются — они уже были отданы через [math]\displaystyle{ R_c }[/math].

Рис. 5. За вызов additionalOperations — не более 3 переносов; фазы идут строго по порядку.

Сводная таблица сложности

Операция	Худший случай	Амортизированный	Переносов за вызов	Память
Empty	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	0	[math]\displaystyle{ O(1) }[/math]
Push	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ \le 3 }[/math]	[math]\displaystyle{ O(1) }[/math]
Pop	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ \le 3 }[/math]	[math]\displaystyle{ O(1) }[/math]
Check-Recopy / Check-Normal	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ \le 3 }[/math]	[math]\displaystyle{ O(1) }[/math]
Вся очередь	—	—	—	[math]\displaystyle{ O(n) }[/math] под элементы

Здесь худший и амортизированный случаи совпадают: амортизация не нужна, потому что никакая операция не выполняет больше трёх переносов. Для сравнения, очередь на двух стеках имеет амортизированный [math]\displaystyle{ O(1) }[/math], но худший [math]\displaystyle{ \Theta(n) }[/math]. В режиме перекопирования каждая «обычная» операция дополнительно тратит до 3 переносов — это уже учтено в оценке [math]\displaystyle{ O(1) }[/math].

Трассировка примера

Проследим push(1) … push(7), затем семь pop. Стеки записаны в виде «дно … верх»; в столбце «режим»: обыч. — обычный, перекоп. — перекопирование. Значения получены прогоном реализации из раздела «Служебное».

Операция	Режим	[math]\displaystyle{ L }[/math]	[math]\displaystyle{ L' }[/math]	[math]\displaystyle{ R }[/math]	[math]\displaystyle{ R_c }[/math]	[math]\displaystyle{ R_c' }[/math]	[math]\displaystyle{ S }[/math]	toCopy
push(1)	обыч.→перекоп.→обыч.	—	—	1	1	—	—	0
push(2)	обыч.	2	—	1	1	—	—	0
push(3)	обыч.→перекоп.	—	—	3,2	1	3,2	1	1
push(4)	перекоп.→обыч.	4	—	3,2,1	3,2,1	1	—	0
push(5)	обыч.	4,5	—	3,2,1	3,2,1	—	—	0
push(6)	обыч.	4,5,6	—	3,2,1	3,2,1	—	—	0
push(7)	обыч.→перекоп.	4,5,6,7	—	—	3,2,1	—	1,2,3	3
pop() → 1	перекоп.	4	—	7,6,5	3,2	7,6,5	1,2,3	2
pop() → 2	перекоп.	—	—	7,6,5,4,3	3	7,6,5,4,3	1	0
pop() → 3	перекоп.→обыч.	—	—	7,6,5,4	7,6,5,4	—	—	0
pop() → 4	обыч.	—	—	7,6,5	7,6,5	—	—	0
pop() → 5	обыч.	—	—	7,6	7,6	—	—	0
pop() → 6	обыч.	—	—	7	7	—	—	0
pop() → 7	обыч.	—	—	—	—	—	—	0

Разберём два важных момента. Во-первых, push(3) запускает перекопирование сразу, но успевает сделать только 3 переноса (старый [math]\displaystyle{ R = \{1\} }[/math] уходит в [math]\displaystyle{ S }[/math], два элемента [math]\displaystyle{ L }[/math] — в [math]\displaystyle{ R }[/math] и [math]\displaystyle{ R_c' }[/math]); завершается перенос на push(4), после чего пары [math]\displaystyle{ L \leftrightarrow L' }[/math] и [math]\displaystyle{ R_c \leftrightarrow R_c' }[/math] меняются ролями. Во-вторых, при push(7) вход ([math]\displaystyle{ |L| = 4 }[/math]) перерос выход ([math]\displaystyle{ |R| = 3 }[/math]), начался новый перенос: [math]\displaystyle{ R }[/math] целиком ушёл в [math]\displaystyle{ S }[/math], toCopy = 3. Следующие pop берут элементы из [math]\displaystyle{ R_c }[/math] (копия старого [math]\displaystyle{ R }[/math]), пока в фоне [math]\displaystyle{ L }[/math] переливается в новый [math]\displaystyle{ R }[/math]; когда toCopy доходит до нуля, корректная часть [math]\displaystyle{ S }[/math] переносится в [math]\displaystyle{ R }[/math], а остальное отбрасывается, и перекопирование заканчивается. Порядок выдачи — [math]\displaystyle{ 1,2,\dots,7 }[/math] — ровно FIFO, и ни один pop не сделал больше трёх внутренних переносов.

Корректность и оценка сложности

Инвариант и FIFO

Будем считать, что в обычном режиме элементы очереди равны [math]\displaystyle{ R }[/math] (сверху вниз) [math]\displaystyle{ \mathbin{+\!\!+} }[/math] [math]\displaystyle{ \mathrm{reverse}(L) }[/math]. Тогда верх [math]\displaystyle{ R }[/math] — самый старый элемент, и Pop возвращает его.

Лемма (сохранение порядка при перекопировании). После завершения перекопирования стек [math]\displaystyle{ R }[/math] содержит все элементы очереди в правильном порядке для извлечения.

Доказательство. Пусть до перекопирования очередь равна [math]\displaystyle{ R_0 \mathbin{+\!\!+} L_0 }[/math] (в указанном смысле). Фаза 1 переносит [math]\displaystyle{ R_0 }[/math] в [math]\displaystyle{ S }[/math], разворачивая: [math]\displaystyle{ S = \mathrm{reverse}(R_0) }[/math]. Фаза 2 переносит [math]\displaystyle{ L_0 }[/math] в [math]\displaystyle{ R }[/math], разворачивая: [math]\displaystyle{ R = \mathrm{reverse}(L_0) }[/math]. Фаза 3 переносит [math]\displaystyle{ S }[/math] (в порядке [math]\displaystyle{ \mathrm{reverse}(R_0) }[/math]) обратно в [math]\displaystyle{ R }[/math], что даёт [math]\displaystyle{ R = \mathrm{reverse}(L_0) \mathbin{+\!\!+} R_0 }[/math] в смысле стека, то есть сверху оказывается [math]\displaystyle{ R_0 }[/math] в исходном порядке, а под ним — [math]\displaystyle{ L_0 }[/math] в исходном порядке. Поскольку элементы [math]\displaystyle{ R_0 }[/math] старее элементов [math]\displaystyle{ L_0 }[/math], это и есть FIFO-порядок. [math]\displaystyle{ \square }[/math]

Лемма (обслуживание во время перекопирования). Пока перекопирование не завершено, Pop возвращает корректный самый старый элемент, не дожидаясь конца переноса.

Доказательство. В режиме перекопирования Pop читает [math]\displaystyle{ R_c }[/math] — копию старого [math]\displaystyle{ R_0 }[/math]; в варианте на шести стеках она синхронно уменьшается вместе с [math]\displaystyle{ R }[/math], а в персистентном заменена неизменяемой версией [math]\displaystyle{ R' }[/math]. Элементы [math]\displaystyle{ R_0 }[/math] старее всех элементов [math]\displaystyle{ L_0 \cup L' }[/math], поэтому выдача из [math]\displaystyle{ R_c }[/math] сохраняет FIFO. Счётчик [math]\displaystyle{ \mathtt{toCopy} }[/math] уменьшается и при извлечении из [math]\displaystyle{ R_c }[/math], и при переносе корректного элемента из [math]\displaystyle{ S }[/math]; поэтому [math]\displaystyle{ |R_c| \ge \mathtt{toCopy} }[/math]. Пока [math]\displaystyle{ \mathtt{toCopy} \gt 0 }[/math], верх [math]\displaystyle{ R_c }[/math] — ещё не перенесённый корректный элемент; когда счётчик доходит до нуля, старый правый кусок уже распределён между [math]\displaystyle{ R }[/math] и [math]\displaystyle{ R_c }[/math], и Pop синхронно снимает элемент из [math]\displaystyle{ R_c }[/math], [math]\displaystyle{ R }[/math] и [math]\displaystyle{ R_c' }[/math]. Инвариант [math]\displaystyle{ \mathtt{toCopy} }[/math] не даёт прочитать «мусорные» элементы в дне [math]\displaystyle{ S }[/math]. [math]\displaystyle{ \square }[/math]

Лемма (корректность Empty). В обычном режиме [math]\displaystyle{ R = \varnothing \iff Q = \varnothing }[/math]; в режиме перекопирования очередь непуста.

Доказательство. В обычном режиме инвариант [math]\displaystyle{ |L| \le |R| }[/math] и представление очереди как [math]\displaystyle{ R \mathbin{+\!\!+} \mathrm{reverse}(L) }[/math] дают эквивалентность. В режиме перекопирования в момент старта (после запускающей операции) в очереди [math]\displaystyle{ n + (n + 1) = 2n + 1 }[/math] элементов. Перенос занимает [math]\displaystyle{ n + 1 }[/math] операций, включая запускающую; после неё остаётся не более [math]\displaystyle{ n }[/math] операций, поэтому извлечь можно не более [math]\displaystyle{ n }[/math] элементов. Значит, хотя бы один элемент остаётся: при [math]\displaystyle{ \mathtt{toCopy} \gt 0 }[/math] он лежит в [math]\displaystyle{ R_c }[/math], а при [math]\displaystyle{ \mathtt{toCopy} = 0 }[/math] весь правый кусок уже находится в [math]\displaystyle{ R }[/math]. Поэтому Empty возвращает false корректно. [math]\displaystyle{ \square }[/math]

Оценка [math]\displaystyle{ O(1) }[/math] в худшем случае

Все переносы выполняются только в Additional-Operations, где счётчик toDo ограничен тройкой, и в фазах 1–3 каждый шаг — один перенос (pop и один-два push). Значит, одна операция очереди делает не более 3 переносов, то есть [math]\displaystyle{ O(1) }[/math] в худшем случае (см. рис. 6).

Покажем, что перекопирование успевает завершиться. В момент старта [math]\displaystyle{ |R| = n }[/math] и [math]\displaystyle{ |L| = n + 1 }[/math]. Требуется: [math]\displaystyle{ R \to S }[/math] — [math]\displaystyle{ n }[/math] действий; [math]\displaystyle{ L \to R, R_c' }[/math] — [math]\displaystyle{ n + 1 }[/math]; [math]\displaystyle{ S \to R, R_c' }[/math] — [math]\displaystyle{ n }[/math]; две смены ролей — 2. Итого [math]\displaystyle{ 3n + 3 }[/math] действий. В распоряжении — [math]\displaystyle{ n + 1 }[/math] операций (сама запускающая перекопирование плюс следующие за ней до завершения переноса), по 3 действия каждая, то есть ровно [math]\displaystyle{ 3(n + 1) = 3n + 3 }[/math]. Расчёт сходится: перенос гарантированно завершается.

Рис. 6. [math]\displaystyle{ 3(n+1) }[/math] действий на [math]\displaystyle{ n+1 }[/math] операций — ровно 3 действия на операцию, без запаздывания.

После перекопирования. Пусть за [math]\displaystyle{ n }[/math] операций после старта произошло [math]\displaystyle{ x }[/math] извлечений и [math]\displaystyle{ n - x }[/math] добавлений. Тогда в новых стеках останется [math]\displaystyle{ n - x }[/math] элементов в [math]\displaystyle{ L }[/math] и [math]\displaystyle{ 2n + 1 - x = (n - x) + (n + 1) }[/math] в [math]\displaystyle{ R }[/math], значит, до следующего перекопирования не менее [math]\displaystyle{ n + 2 }[/math] операций. За это время остаток [math]\displaystyle{ R_c' }[/math] (не более [math]\displaystyle{ n }[/math] элементов) успевает рассосаться: он уменьшается на 1 при каждой операции в обычном режиме. Это и есть содержание инварианта [math]\displaystyle{ |R_c'| \le |R| - |L| }[/math].

Персистентная очередь на пяти стеках

Сделаем все стеки персистентными (неизменяемыми): операция возвращает новую версию, старые остаются доступны. Тогда шесть стеков превращаются в пять: пара [math]\displaystyle{ (R_c, R_c') }[/math] избыточна — достаточно одной версии [math]\displaystyle{ R' }[/math], записанной в момент старта перекопирования; pop обращается к ней, и никакой синхронизации не нужно. Освобождать [math]\displaystyle{ R' }[/math] тоже не требуется: ячейки используются другими версиями очереди. Версия очереди — запись [math]\displaystyle{ Q = \langle L, L', R, R', S, \mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied}\rangle }[/math]; push и pop возвращают новую версию вместе с результатом. Переносы по-прежнему ограничены тремя на операцию, поэтому каждая версия занимает [math]\displaystyle{ O(1) }[/math] новых ячеек и время [math]\displaystyle{ O(1) }[/math] в худшем случае. Псевдокод (упрощённо, по источнику):

Версия Push(Q, x)
1  if not Q.recopy
2      Ln ← push(Q.L, x)
3      return Check-Recopy(⟨Ln, Q.L', Q.R, Q.R', Q.S, Q.recopy, Q.toCopy, Q.copied⟩)
4  else
5      Ln' ← push(Q.L', x)
6      return Check-Normal(⟨Q.L, Ln', Q.R, Q.R', Q.S, Q.recopy, Q.toCopy, Q.copied⟩)

Версия Pop(Q)
1  if not Q.recopy
2      ⟨Rn, x⟩ ← pop(Q.R)
3      return ⟨Check-Recopy(⟨Q.L, Q.L', Rn, Q.R', Q.S, …⟩), x⟩
4  else
5      ⟨Rn', x⟩ ← pop(Q.R')
6      if Q.toCopy > 0
7          cur ← Q.toCopy − 1
8          return ⟨Check-Normal(⟨Q.L, Q.L', Q.R, Rn', Q.S, …, cur, Q.copied⟩), x⟩
9      else
10         ⟨Rn, x⟩ ← pop(Q.R)
11         return ⟨Check-Normal(⟨Q.L, Q.L', Rn, Rn', Q.S, …, 0, Q.copied⟩), x⟩

Функции Check-Recopy, Check-Normal, Additional-Operations повторяют версию на шести стеках, но вместо мутации создают новые версии стеков. Важное отличие: в пятистековом варианте Check-Recopy при входе в перекопирование фиксирует [math]\displaystyle{ R' \leftarrow R }[/math] — текущую версию выхода; без этого pop в режиме перекопирования читал бы устаревшую версию. См. рис. 7.

Сравнение с альтернативами

Реализация	Худший	Амортизированный	Память на версию	Персистентность
Два стека	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ O(1) }[/math]	неприменима ([math]\displaystyle{ \Theta(n) }[/math])	нет
Шесть стеков (реальное время)	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	— (не персистентна)	нет
Пять стеков (персистентная)	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math] новых ячеек	да (функциональная)
Кольцевой буфер	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ \Theta(n) }[/math] на копию	нет
Связный список	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ \Theta(1) }[/math], но с риском разделения	частично (copy-on-write)

Рис. 7. Три уровня компромисса: амортизированно [math]\displaystyle{ O(1) }[/math] → худший [math]\displaystyle{ O(1) }[/math] → худший [math]\displaystyle{ O(1) }[/math] с персистентностью.

Когда что выбирать. Нужна простая очередь общего назначения — кольцевой буфер или двусвязный список из Очередь (план). Нужна гарантия времени отклика — шесть стеков. Нужны прошлые версии (undo, функциональный язык) — персистентная очередь на пяти стеках. Если допустимы амортизированные оценки и не важна задержка, двух стеков достаточно.

Где применяется

1. Функциональные языки и библиотеки. В Haskell, OCaml, Standard ML очереди и деки — персистентные структуры; техника раскрытия «ленивого» переноса восходит к реальному времени и используется в Data.Sequence, очередях Okasaki и структурах с неизменяемыми версиями. Почему: в чисто функциональном коде структура не мутируется, а старые версии должны сохраняться [4][5].

1. Системы реального времени. Планировщики, обработчики прерываний, буферы событий требуют ограниченного сверху времени отклика. Очередь с [math]\displaystyle{ O(1) }[/math] в худшем случае исключает редкие «долгие» вызовы, которые опасны в контурах управления и телеком-оборудовании [1][3].

1. Персистентность и версионирование. Undo/redo в редакторах, транзакционные снимки, инкрементальные вычисления и системы контроля версий выигрывают от структур, где каждая версия стоит [math]\displaystyle{ O(1) }[/math] новых ячеек. Персистентная очередь — базовый кирпич таких систем [4].

1. Логи событий и распределённые потоки. Очередь сообщений, к которой нужен доступ к прошлым состояниям (replay, аудит), строится на персистентных структурах; неизменяемость упрощает репликацию и откат [4].

1. Обучение алгоритмам. Конструкция «очередь на шести стеках» — классическая задача курса дискретной математики и алгоритмов (Викиконспекты ИТМО): она тренирует инварианты, амортизационный анализ и персистентность [1][2].

1. Олимпиадное программирование. Персистентная очередь и её «друзья» (персистентный стек, дек, приоритетная очередь) — инструменты задач на версии и откаты; разборы публикуются в блогах сообщества [2].

Историческая справка

Операции над очередью в реальном времени первыми описали Роберт Худ и Роберт Мелвилл (R. Hood, R. Melville) в работе Real Time Queue Operations in Pure LISP (Cornell University, 1980; отчёт доступен через библиотечный депозитарий Корнеллского университета) [3]. Они показали, как реализовать очередь без долгих операций в чистом LISP, где данные неизменяемы, — именно персистентность и подталкивала к распределению переноса по операциям.

Идею подхватил Крис Окасаки (Chris Okasaki): в статье Simple and Efficient Purely Functional Queues and Deques (Journal of Functional Programming, 1995) и книге Purely Functional Data Structures (Cambridge University Press, 1998) он систематизировал персистентные очереди — «банкирскую», «физическую» и очередь реального времени [4]. Формальный амортизированный анализ (и метод потенциала) восходит к Роберту Тарьяну (R. E. Tarjan, «Amortized Computational Complexity», 1985) [5] и служит языком описания оценок в этой области.

Изложение конструкции «очередь на шести стеках» и её персистентного варианта на пяти стеках — учебная традиция кафедры компьютерных технологий ИТМО; конспект доступен на «Викиконспектах» (neerc.ifmo.ru) [1]. Популярные разборы — в блоге Codeforces [2] и на Хабрахабре [7]. Отметим, что конкретное число стеков (шесть против пяти) зависит от того, требуется ли явная копия выхода: persistence позволяет обойтись меньшим числом стеков [1].

Типичные ошибки и подводные камни

• Путать амортизированное с худшим. Очередь на двух стеках — амортизированно [math]\displaystyle{ O(1) }[/math], но худший случай [math]\displaystyle{ \Theta(n) }[/math]; только конструкция на шести стеках даёт [math]\displaystyle{ O(1) }[/math] в каждом вызове.
• Забыть подчищать [math]\displaystyle{ R_c' }[/math]. В обычном режиме остаток копии нужно уменьшать на 1 за операцию (инвариант [math]\displaystyle{ |R_c'| \le |R| - |L| }[/math]), иначе к следующему перекопированию не найдётся свободного стека.
• Неверный момент запуска. Перекопирование нужно начинать ровно при [math]\displaystyle{ |L| = |R| + 1 }[/math]; позже — не хватит операций на перенос, раньше — нарушится инвариант и лишняя работа.
• Ошибка на единицу в toCopy. Это число корректных элементов в [math]\displaystyle{ S }[/math]; при pop во время перекопирования его нужно уменьшать, иначе можно прочитать уже извлечённый элемент.
• Забыть фазу 1 ([math]\displaystyle{ R \to S }[/math]). Без буфера [math]\displaystyle{ S }[/math] старый выход не опустеет, если операций push больше, чем pop, и не хватит стека для нового [math]\displaystyle{ R }[/math]; двойной переворот через [math]\displaystyle{ S }[/math] обязателен.
• Не сделать смену ролей. Без [math]\displaystyle{ \mathtt{swap}(L, L') }[/math] и [math]\displaystyle{ \mathtt{swap}(R_c, R_c') }[/math] новые результаты останутся в служебных стеках, а очередь будет читать старое.
• Попытка сделать двухстековую очередь персистентной «в лоб». Дорогая операция переноса порождает [math]\displaystyle{ \Theta(n) }[/math] новых ячеек на версию — нужна именно конструкция с дроблением.
• Мутируемые стеки в персистентном варианте. Персистентность требует неизменяемости; изменение «на месте» разрушит прошлые версии.
• Закольцованная рекурсия проверок. Check-Recopy вызывает Check-Normal, который может выставить recopy снова; рекурсии здесь нет — это разные шаги одной операции, но при переносе в код важно не зациклиться.
• Предположение, что Empty ложен всегда в перекопировании. Так и есть (в [math]\displaystyle{ R_c }[/math] или [math]\displaystyle{ R }[/math] остаются элементы), но если реализация не поддерживает инвариант [math]\displaystyle{ |L| = |R| + 1 }[/math] в момент старта, Empty может соврать.

Задачи для практики

1. Два стека. Реализуйте очередь на двух стеках и определите худший случай. Ограничение: не более [math]\displaystyle{ O(1) }[/math] памяти на элемент. Подсказка: перенос происходит при опустошении выхода; худший вызов — [math]\displaystyle{ \Theta(n) }[/math].

1. Инвариант. Докажите, что в обычном режиме [math]\displaystyle{ R = \varnothing \iff Q = \varnothing }[/math]. Подсказка: используйте [math]\displaystyle{ |L| \le |R| }[/math] и представление [math]\displaystyle{ R \mathbin{+\!\!+} \mathrm{reverse}(L) }[/math].

1. Счёт действий. Покажите, что при старте перекопирования ([math]\displaystyle{ |L| = |R| + 1 = n + 1 }[/math]) требуется ровно [math]\displaystyle{ 3n + 3 }[/math] действий и что их укладывает ровно [math]\displaystyle{ n + 1 }[/math] операция по 3. Подсказка: сложите вклады фаз 1–4.

1. toCopy. Объясните, почему некорректные элементы [math]\displaystyle{ S }[/math] скапливаются у дна, и почему условие toCopy > 0 защищает от чтения мусора. Подсказка: элементы [math]\displaystyle{ S }[/math] переносятся по одному, а уменьшение toCopy соответствует уже отданным элементам.

1. Трассировка. Вручную повторите семь push и семь pop из раздела «Трассировка примера» и сверьте состояния стеков. Подсказка: следите за флагами recopy, copied, toCopy.

1. Реальное время vs персистентность. Объясните, почему шестистековый вариант годится для реального времени, а для персистентности достаточно пяти стеков. Подсказка: роль копии [math]\displaystyle{ R_c }[/math] берёт на себя версия [math]\displaystyle{ R' }[/math].

1. Пятистековая очередь. Реализуйте персистентную очередь на пяти неизменяемых стеках так, чтобы каждая версия занимала [math]\displaystyle{ O(1) }[/math] новых ячеек. Ограничение: стеки неизменяемы.

1. Расширение до дека. Попробуйте добавить pop_back/push_front и обсудите, почему дек на стеках сложнее очереди. Подсказка: симметрия «лево/право» требует mirrored-структуры.

Связанные темы

• Очередь (план) — базовая FIFO, кольцевой буфер, очередь на двух стеках.
• Стек (план) — строительный блок; стек как персистентная структура.
• Персистентный стек (план) — неизменяемый стек; основа персистентной очереди.
• Персистентная очередь (план) — персистентность очереди, ленивые очереди Окасаки.
• Асимптотическая сложность — амортизация, худший случай, худший и амортизированный.
• Персистентные структуры данных — неизменяемость и версии.
• Декартово дерево (план) — персистентный treap как ещё один пример персистентности.
• Очередь с приоритетом (план) — родственная структура; персистентный вариант.

Источники

1. Викиконспекты ИТМО: Персистентная очередь (разделы «Реализация очереди на шести стеках», «Персистентная очередь на пяти стеках»). URL: https://neerc.ifmo.ru/wiki/index.php?title=Персистентная_очередь.
2. Codeforces. Персистентная очередь и её друзья (блог). URL: https://codeforces.com/blog/entry/15685.
3. Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980. URL: http://hdl.handle.net/1813/6273.
4. Okasaki C. Simple and Efficient Purely Functional Queues and Deques // Journal of Functional Programming. — 1995. — Vol. 5, № 4; и Okasaki C. Purely Functional Data Structures. — Cambridge University Press, 1998.
5. Tarjan R. E. Amortized Computational Complexity // SIAM J. Algebraic and Discrete Methods. — 1985. — Vol. 6, № 2.
6. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 10 (элементарные структуры: стек, очередь).
7. Хабрахабр. Персистентная очередь (пост 241231). URL: https://habr.com/ru/post/241231/ (проверено 2026-11-03: статья о персистентной очереди, другой алгоритм — на деревьях).