Очередь с поддержкой минимума
Реализуйте очередь с поддержкой минимума.
Входные данные
Первая строка входных данных содержит число n — количество операций с очередью. В каждой следующей строке содержится число ai (0≤ai≤10000). Если ai>0, то это число необходимо добавить в очередь. Если ai=0, то это запрос на удаление элемента из очереди.
Выходные данные
На каждый запрос удаления элемента из очереди необходимо вывести значение минимального элемента очереди (учитывая значение удаляемого элемента). Если запрос удаления вызывается на пустой очереди, то необходимо вывести −1.
Примеры
Ввод
9
5
4
3
6
0
0
0
0
0
Вывод
3
3
3
6
-1
Решать на C++
Ответы
Ответ:
Объяснение:
#include <iostream>
using namespace std;
const int max_size = 2000;
class Queue //класс Очередь
{
int q[max_size]; //массив чисел
int left = 0, right = 0; //первый(крайний левый) и последний(крайний правый) элементы массива
public:
void add(int a); //функция для добаления элемента в очередь
void getMinNum(); //функция для получения минимального числа в очереди
};
void Queue::add(int a)
{
if (a != 0)
{ //если введено число больше 0
q[right] = a;
right++;
}
else if (left == right)
{ //если первый и последний элементы совпадают, очередь пуста
cout << -1 << "\n";
}
else
{ //если введен '0'
this->getMinNum();
left++;
}
}
void Queue::getMinNum()
{
int minID = left;
for (int i = left; i < right; i++)
if (q[minID] > q[i])
minID = i;
cout << q[minID] << "\n";
}
int main()
{
int n; //количество операций
Queue q; //объект класса Очередь
int num;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> num; //вводим число
q.add(num);
}
return 0;
}