Дана реализация структуры данных "стек". Она умеет выполнять операции push_back/pop_back/back за O(1) в среднем.
Задача: реализовать структуру данных "дек", которая выполняет push_back/pop_back/back/push_front/pop_front/front за O(1) в среднем.
Примечание: под средним O(1) понимается амортизированное среднее, т. е. в случае выполнения корректной последовательности из N указанных операций над изначально пустой структурой данных суммарное время не превосходит O(N).
Просьба решения писать под спойлеры.
Спойлер
Спойлер.
Небольшой, но спойлер)
Спойлер.
Не спойлер
Спойлер.
Спойлер
As far as I can tell, it's (de)queue realization in any functional language, which uses one-dimensional lists. Erlangs standart library, for example.
"realization"->"implementation"?
I looked at implementation of deque in erlang. Maybe I'm missing something, but it seems to me that it is bugged: they maintain 2 stacks and if one of them is empty when we want to pop from it, they move everything there from the other stack. That means that the sequence of operations "out, out_r, out, out_r, ..." results in quadratic time. Again, maybe I misunderstood their code (I do not really know erlang), but it really seems that their O(1) guarantees are incorrect.
Update: implemented proof-of-concept. With "pop(pop())" it works 0.33s, with "pop(pop_r())" — infinity. So, Erlang stdlib is bugged.
Re-looked the code.
It seems they leave 2 elements on other list, and move all other in reverse to first list. That's strictly N operations, and for the next N in/drop operations we wouldn't need to do that again. But if I do drop, drop, drop_r, drop_r, it would be O(N) every 4 operations. Guess it's ok, since module is named "queue".
Right, it wasn't the solution, but I think the solution is near. Just need to split list in the middle.
It's not ok, they say that amortized time is O(1) in their documentation.