Комментарии 13
Очередь — это структура данных с доступом к элементам LIFO (англ. Last In, First Out – «последним пришёл — первым ушёл»)
Эмм… Может очередь это FIFO?
Очередь, pop — достать элемент из конца очереди
Точно не из начала?
Спасибо, "как" довольно очевидно (когда сообразишь, что наихудшее время O(1) не сделать, значит, ищем а ортизированное), а вот "зачем" – в голову не приходило.
К бонусной задачке: есть другой алгоритм поиска бегущего максимума/минимума за O(N), основанный на разбиении на отрезки по M чисел. Интересно, что придумали его только в 80-х.
Есть еще другой алгоритм, без всяких предподсчетов и разбиений, но с одним деком.
Алгоритм не обобщается на любую ассоциативную операцию и работает только для min/max.
Структура поддерживает 3 операции — добавить в начало, убрать с конца и узнать максимум. Добавление амортизационно O(1), удаление и максимум — константны по времени.
Суть в том, что Вы должны держать список/дек элементов в окне, которые могли бы в какой-то момент стать максимумами. Они в окне будут образовывать убывающую последовательность. При добавлении в окно нового элемента, надо с конца выкинуть все элементы, меньше нового, чтобы последовательность осталась убывающей (они в окне уже никогда максимумом не будут, ведь они уйдут из окна раньше нового элемента, который уже больше). При удалении элемента из окна надо проверить, что элемент хранится в деке и удалить, если надо.
То есть, для стека — да. Мы можем получить min за O(1), но разве это свойство сохранится, когда у нас будет очередь из двух стеков.
Как и зачем делать очередь на двух стеках