Очередь с поддержкой минимума Реализуйте очередь с поддержкой минимума. Входные данные Первая строка входных данных содержит число n — ко...
Условие:
Очередь с поддержкой минимума Реализуйте очередь с поддержкой минимума.
Входные данные
Первая строка входных данных содержит число n — количество операций с очередью. В каждой следующей строке содержится число ai (0⩽ai⩽10000 ). Если ai>0 , то это число необходимо добавить в очередь. Если ai=0 , то это запрос на удаление элемента из очереди.
Вы
Решение:
Можно реализовать очередь с поддержкой минимума, используя две структуры данных: стек и дек.
Стек будет использоваться для хранения элементов очереди, а дек будет использоваться для хранения текущего минимального элемента.
При добавлении элемента в очередь, мы добавляем его в стек. Если добавленный элемент меньше или равен текущему минимальному элементу в деке, то мы также добавляем его в начало дека. В противном случае, мы не делаем ничего.
При удалении элемента из очереди, мы удаляем его из стека. Если удаленный элемент равен текущему минимальному элементу в деке, то мы также удаляем его из дека. В противном случае, мы не делаем ничего.
При запросе минимального элемента, мы возвращаем значение, хранящееся в начале дека.
Вот пример реализации на языке Python:
from collections import deque
class MinQueue:
def __init__(self):
self.stack = []
self.min_deque = deque()
def enqueue(self, value):
self.stack.append(value)
if not self.min_deque or value <= self.min_deque[0]:
self.min_deque.appendleft(value)
def dequeue(self):
if not self.stack:
return None
value = self.stack.pop(0)
if value == self.min_deque[0]:
self.min_deque.popleft()
return value
def get_min(self):
if not self.min_deque:
return None
return self.min_deque[0]
Теперь вы можете использовать эту реализацию для решения задачи с очередью с поддержкой минимума.
