Deque

[migmit]

Наткнулся тут на простенькую задачку: написать стек, поддерживающий, кроме стандартных push и pop, ещё и операцию min, которая возвращает минимальное значение из содержащихся в стеке. При этом все три операции должны выполняться за O(1).

Ну, задачка действительно простая, но меня натолкнула на мысль: а что, если вместо стека делать deque, т.е., массив элементов, к которому можно добавлять новые (и удалять старые) как с левого конца, так и с правого? При этом по-прежнему хочется делать min.

Пока что у меня получилась реализация, делающая pop_front, pop_back и min за O(1), а push_back и push_front - за амортизированное O(1).

Вопрос к коллегам: это где-нибудь есть?

Comments

[nealar.livejournal.com]

Я как бы в курсе.

[migmit.livejournal.com]

Блин. Я, оказывается, пропустил 2.

Я не сомневаюсь, что в курсе, но людей, на голубом глазу утверждавших, что O(2N) и O(N) — разные вещи, я видел.

[nealar.livejournal.com]

Я, оказывается, пропустил 2.
Я решил, что это такая подколка. Ведь так в итоге и получается.

утверждавших, что O(2N) и O(N) — разные вещи
Уже интересно, что они говорили за O(N+1).