Deque

[migmit]

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

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

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

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

Comments

[migmit.livejournal.com]

Ужасы какие рассказываете.

По-нормальному нужно просто держать два стека, один обычный, а другой состоящий из тех элементов первого, глубже которых нет ни одного элемента меньше. Будет O(1) на push, pop и min.

[kgeorgiy.livejournal.com]

Можно еще проще -- хранить в стеке пары (элемент, соответствующий минимум).

[migmit.livejournal.com]

Или так, да.

[nealar.livejournal.com]

Таки да! Если всё равно O(2N) память, то зачем извращаться.

[migmit.livejournal.com]

O(N), в общем-то, от O(N) ничем не отличается.

[nealar.livejournal.com]

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

[migmit.livejournal.com]

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

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

[nealar.livejournal.com]

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

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