- PVSM.RU - https://www.pvsm.ru -
Привет!
Данный пост написан для новичков в олимпиадном программировании и начинающих разработчиков, готовящихся к прохождению алгоритмических интервью. В конце бонусная задачка. Если заинтересовал, прошу под кат :)
Для начала вспомним основы:
Стек реализует принцип LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Стек имеет две основные операции:
Стек обычно реализуется на массиве (еще можно на связном списке). Подробнее про стек и его реализацию можно прочитать здесь [1]
Очередь — это структура данных с доступом к элементам FIFO (англ. First In, First Out – «первым пришёл — первым ушёл»)
Очередь имеет два основных метода в своем интерфейсе:
Подробнее про обычную очередь можно прочитать здесь [2].
Обычно рассматривают два базовых подхода к реализации очереди:
Представим себе, что наша структура данных должна поддерживать следующий набор операций:
Все перечисленные операции ассоциативны (образуют полугруппу), но ни одна из них не имеет обратного элемента (не образует группу).
Для стека можно очень просто поддерживать любую из приведенных операций: достаточно хранить на его вершине пару:
, где второй элемент пары — результат операции, примененной ко всем элементам стека.
Ниже пример реализации стека с поддержкой минимума на 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).
Дана последовательность N чисел. Задано число M < N. Требуется за линейное время найти отрезок длины M, на котором произведение min * max максимально.
Спасибо, что дочитали до конца!
Если вас заинтересовала тема, можете почитать как сделать персистентную очередь на двух стеках здесь [3], либо дождаться выхода следующего моего топика.
Пишите в комментариях какие задачи на двух стеках вам приходилось решать на интервью или контестах.
Автор: demitryy
Источник [4]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/struktury-danny-h/343208
Ссылки в тексте:
[1] здесь: https://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%82%D0%B5%D0%BA
[2] здесь: https://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C
[3] здесь: https://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D0%B0%D1%8F_%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C
[4] Источник: https://habr.com/ru/post/483944/?utm_campaign=483944&utm_source=habrahabr&utm_medium=rss
Нажмите здесь для печати.