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




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

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

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

Стек


Стек реализует принцип 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 — наименьшее общее кратное)

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

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

$(element, operationResult)$

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

Ниже пример реализации стека с поддержкой минимума на 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 максимально.

Идея решения 1
Сделай очередь с поддержкой минимума и максимума.

Идея решения 2
aamonster подсказал, что есть другой способ решения (читай здесь).

Заключение


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

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

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

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (12):

  1. timon_aeg
    /#21131720

    Очередь же всегда была FIFO?

    • demitryy
      /#21131774

      Копипаста проросла, поправил :)

  2. avor_il
    /#21131764

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

    Эмм… Может очередь это FIFO?

    • demitryy
      /#21131822

      Благодарю за замечание, опечатался)

  3. Gekus
    /#21131974

    Очередь, pop — достать элемент из конца очереди

    Точно не из начала?

  4. aamonster
    /#21133284 / +1

    Спасибо, "как" довольно очевидно (когда сообразишь, что наихудшее время O(1) не сделать, значит, ищем а ортизированное), а вот "зачем" – в голову не приходило.


    К бонусной задачке: есть другой алгоритм поиска бегущего максимума/минимума за O(N), основанный на разбиении на отрезки по M чисел. Интересно, что придумали его только в 80-х.

    • demitryy
      /#21133374 / +1

      Спасибо, что подсказали. Сразу начал гуглить и нашел статью на хабре на эту тему. Добавлю ссылку на нее тоже)

  5. netricks
    /#21135238

    Хм… Разве это помогает получить min за О(1)?
    То есть, для стека — да. Мы можем получить min за O(1), но разве это свойство сохранится, когда у нас будет очередь из двух стеков.

    • Cerberuser
      /#21136586

      Берём минимум из двух минимумов же.

  6. Filex
    /#21135502

    Очередь на двух стеках была в собеседовании на поступление в школу разработчиков hh

    • AndrewN
      /#21136898

      И еще, видимо, много где, так как попала даже в Cracking the Coding Interview