Question

Очередь с поддержкой минимума Реализуйте очередь с поддержкой минимума. Входные данные Первая строка входных данных содержит число 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++

Answer 1

Ответ:

Объяснение:

#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;

}

Answer 2

Для решения этой задачи вам понадобится реализовать структуру данных, которая поддерживает операции вставки и удаления элементов с учетом минимума. Вы можете использовать две структуры данных: стек для хранения элементов и другой стек для хранения минимальных значений. Вот пример C++ реализации:

cppCopy code
#include <iostream>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;
    stack<int> mainStack;
    stack<int> minStack;

    for (int i = 0; i < n; i++) {
        int operation;
        cin >> operation;

        if (operation > 0) {
            mainStack.push(operation);

            if (minStack.empty() || operation <= minStack.top()) {
                minStack.push(operation);
            } else {
                minStack.push(minStack.top());
            }
        } else if (operation == 0) {
            if (!mainStack.empty()) {
                mainStack.pop();
                minStack.pop();
            } else {
                cout << -1 << endl;
            }
        }

        if (!mainStack.empty()) {
            cout << minStack.top() << endl;
        } else {
            cout << -1 << endl;
        }
    }

    return 0;
}

Этот код сначала создает два стека: mainStack для хранения элементов и minStack для хранения минимальных значений. Затем он выполняет операции вставки и удаления элементов в соответствии с вводом и выводит минимальное значение при каждой операции удаления.