Как и зачем делать очередь на двух стеках

Привет, Хабр!

Данный пост написан для новичков в олимпиадном программировании и начинающих разработчиков, готовящихся к прохождению алгоритмических интервью. В конце бонусная задачка. Если заинтересовал, прошу под кат :)

Для начала вспомним основы:

Стек

Стек реализует принцип LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Стек имеет две основные операции:

• push — положить элемент на стек
• pop — достать элемент из стека

Стек обычно реализуется на массиве (еще можно на связном списке). Подробнее про стек и его реализацию можно прочитать здесь

Очередь

Очередь — это структура данных с доступом к элементам FIFO (англ. First In, First Out – «первым пришёл — первым ушёл»)

Очередь имеет два основных метода в своем интерфейсе:

• push — положить элемент в конец очереди
• pop — достать элемент из начала очереди

Подробнее про обычную очередь можно прочитать здесь.

Обычно рассматривают два базовых подхода к реализации очереди:

1. На массиве
2. На связном списке

Почему стек круче, чем очередь

Представим себе, что наша структура данных должна поддерживать следующий набор операций:

• Поддержка минимума (min)
• Поддержка максимума (max)
• Поддержка gcd (англ. greatest common divisor — наибольший общий делитель)
• Поддержка lcm (англ. least common multiple — наименьшее общее кратное)

Все перечисленные операции ассоциативны (образуют полугруппу), но ни одна из них не имеет обратного элемента (не образует группу).

Для стека можно очень просто поддерживать любую из приведенных операций: достаточно хранить на его вершине пару:

, где второй элемент пары — результат операции, примененной ко всем элементам стека.

Ниже пример реализации стека с поддержкой минимума на Python:

class Stack:
    def __init__(self):
        self.stack = []

    def __bool__(self):
        return bool(self.stack)

    def push(self, elem):
        if self.stack:
            self.stack.append((elem, min(elem, self.stack[-1][1])))
        else:
            self.stack.append((elem, elem))

    def pop(self):
        return self.stack.pop()[0]

    def get_min(self):
        if not self.stack:
            return math.inf
        return self.stack[-1][1]

А теперь подумайте, как проделать тот же фокус с очередью? Если пробовать с классической очередью, организованной на массиве, вряд ли что-то получится. Это связано с тем, что операция минимум не имеет обратную операцию (как операция сложения имеет операцию вычитания, например). Как вы могли догадаться, далее я расскажу о не совсем классической реализации очереди на двух стеках.

Очередь на двух стеках

Главное условие, которое должно быть выполнено — все операции должны выполняться за амортизированное O(1).

Возьмем два стека: s1 и s2.

Операцию push будем всегда делать в стек s1.

Операция pop будет устроена так: если стек s2 пустой, перекладываем все элементы из s1 в s2 последовательными вызовами pop и push. Теперь в стеке s2 лежат элементы в обратном порядке (самый верхний элемент — это самый первый положенный элемент в нашу очередь).

Если s2 не пуст, тупо достаем элементы из него. Как только s2 окажется снова пустым повторяем ту же операцию.

Код на Python:

class Queue:
    def __init__(self):
        self.s1 = Stack()
        self.s2 = Stack()

    def push(self, elem):
        self.s1.push(elem)

    def pop(self):
        if not self.s2:
            while self.s1:
                self.s2.push(self.s1.pop())
        return self.s2.pop()

    def get_min(self):
        return min(self.s1.get_min(), self.s2.get_min())

Время работы

Операция push: Мы тупо кладем элемент в стек s1. Время работы O(1).

Операция pop: Для каждого элемента мы делаем не более одного перекладывания из стека в стек, следовательно амортизированное время работы составит O(1).

Операция get_min: Для стеков s1 и s2 известны минимумы, поэтому мы просто берем минимум из минимумов. Время работы O(1).

Бонусная задачка

Дана последовательность N чисел. Задано число M < N. Требуется за линейное время найти отрезок длины M, на котором произведение min * max максимально.

Заключение

Спасибо, что дочитали до конца!

Если вас заинтересовала тема, можете почитать как сделать персистентную очередь на двух стеках здесь, либо дождаться выхода следующего моего топика.

Пишите в комментариях какие задачи на двух стеках вам приходилось решать на интервью или контестах.