Очередь с поддержкой минимума можно реализовать с помощью двух стеков.
Шаги решения:
1. Создать два пустых стека – stack и min_stack.
2. Инициализировать переменную min_value значением “бесконечность”.
3. Повторить следующие действия n раз:
1. Считать число ai.
2. Если ai больше нуля, значит это операция добавления элемента в очередь.
1. Положить ai в стек stack.
2. Если ai меньше или равно min_value, обновить min_value значением ai и добавить ai в стек min_stack.
3. Если ai равно нулю, значит это операция удаления элемента из очереди.
1. Если стек stack пустой, вывести сообщение об ошибке.
2. Иначе, снять элемент из стека stack.
1. Если удаленный элемент равен min_value, значит мы удалили минимальный элемент из очереди.
1. Снять элемент из стека min_stack.
2. Если стек min_stack пустой, обновить min_value значением “бесконечность”.
4. Вывести min_value – минимальный элемент в очереди.
Пример:
Входные данные:
6
3
0
4
2
0
1
Шаги решения:
1. Создать пустые стеки stack и min_stack, и инициализировать min_value значением “бесконечность”.
2. Цикл #1:
– ai = 3, добавить 3 в стек stack, обновить min_value значением 3, добавить 3 в min_stack.
3. Цикл #2:
– ai = 0, удалить элемент из стека stack: 3.
– Удаленный элемент равен min_value, снять элемент из min_stack: 3.
– min_stack пустой, обновить min_value значением “бесконечность”.
– Вывести min_value: “бесконечность”.
4. Цикл #3:
– ai = 4, добавить 4 в стек stack, обновить min_value значением 4, добавить 4 в min_stack.
5. Цикл #4:
– ai = 2, добавить 2 в стек stack, min_value не изменяется, не добавлять 2 в min_stack.
6. Цикл #5:
– ai = 0, удалить элемент из стека stack: 2.
– Удаленный элемент не равен min_value.
– Вывести min_value: 4.
7. Цикл #6:
– ai = 1, добавить 1 в стек stack, min_value не изменяется, не добавлять 1 в min_stack.
8. Вывести min_value: 4.