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]

Попробуйте прикинуть, сколько времени займёт "обновление".

[freedom_of_sea.livejournal.com]

вставка в стек довольно сложная операция, обновление одной ячейки не сильно её замедлит. А поиск по всему стеку или сортировка в любом случае намного дороже

[migmit.livejournal.com]

Вопрос не в том, сколько займёт запись в одну ячейку. Вопрос в том, сколько займёт выяснение того, что туда нужно записать.

[freedom_of_sea.livejournal.com]

запись в ячейку стека нового значения ничем не отличается от обычной.
Запись в ячейку min производится только если новое значение меньше старого min

[nealar.livejournal.com]

А при удалении головы из стека?

[freedom_of_sea.livejournal.com]

ну да, точно.

проверка стоит недорого, а изменятся значение min будет редко

[migmit.livejournal.com]

Как вы думаете, сколько операций сравнения потребуется для этого "обновления", если сделать следующие операции:

push(5)
push(4)
push(3)
push(2)
push(1)
push(0)
pop()
pop()
pop()
pop()
pop()
pop()

[freedom_of_sea.livejournal.com]

все конечно зависит от величины стека и частоты запроса min. Полный поиск min по стеку (с различными выкрутасами типа индексов) намного дороже обновления min

[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).