50б. Как создать очередь с поддержкой минимума на языке питон и на с++? Напишите программу на одном из этих языков

Магнитный_Марсианин_6531

60

Программа на языке Python, реализующая очередь с поддержкой минимума:

python

import heapq



class MinQueue:

    def __init__(self):

        self.queue = []

        self.min_queue = []



    def enqueue(self, item):

        heapq.heappush(self.queue, item)

        heapq.heappush(self.min_queue, item)



    def dequeue(self):

        item = heapq.heappop(self.queue)

        self.min_queue.remove(item)

        heapq.heapify(self.min_queue)

        return item



    def get_min(self):

        return self.min_queue[0]



# Получаем количество операций

n = int(input("Введите количество операций: "))



min_queue = MinQueue()



for _ in range(n):

    operation = input("Введите операцию (0 - удаление, любое другое число - добавление): ")

    if operation == "0":

        min_queue.dequeue()

    else:

        item = int(operation)

        min_queue.enqueue(item)



    print(f"Минимальный элемент: {min_queue.get_min()}")

Программа создает класс MinQueue, который реализует очередь с поддержкой минимума. В очереди хранятся элементы в порядке их добавления, а также минимумы из текущего состояния очереди. Для реализации операции поиска минимального элемента используются специальная очередь min_queue, которая позволяет получать минимальный элемент за O(1) время.

В основном цикле программы считываем операцию пользовательского ввода. Если операция равна 0, выполняется удаление элемента из очереди с помощью метода dequeue(). В противном случае, операция рассматривается как число и добавляется в очередь с помощью метода enqueue(). Затем выводится текущий минимальный элемент в очереди с помощью метода get_min().

Можно запустить программу и вводить операции для проверки ее работоспособности.