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]

Э-э-э, не вижу особого сходства. Вроде, там и интерфейс другой (не pop_front и pop_back, а один pop_min), и временные показатели (в классической реализации) другие.

[nponeccop.livejournal.com]

Вам нужна штука, умеющая

а) делать get_min, являющийся частным случаем pop_min
б) выполнять другие операции (pop_front и pop_back)

Очевидно, что любая priority queue умеет пункт А. Соответственно, я посоветовал полистать литературу на тему priority queue, может окажется, что некоторые варианты умеют нужные Вам операции, ну и заполучить нужные ключевые слова.

А какая это реализация priority queue выделена Вами как классическая? array-backed binary heap?

[migmit.livejournal.com]

Очевидно, что любой стек умеет часть того, что требуется. Причём большую часть, чем priority queue. Тем не менее, стек не годится.

Кроме того, подразумеваемым обычно свойством priority queue является частичное НЕсохранение порядка, в то время как нам нужно держать порядок точно.

Короче говоря, страшно далеки они от того, что надо. Впрочем, решение с амортизированным O(1) я, как уже говорил, придумал, а ниже привели решение с настоящим O(1). И ни то, ни другое не имеет отношения к priority queue.

> array-backed binary heap?

Она, родимая.