#include <iostream>
#include <vector>
#include <algorithm>
template<class Item>
class PQ
{
private:
// По-хорошему, для реализации очереди с приоритетами надо юзать кучу
// (см. вики по "куча структура данных")
// но тебе будет сложно ее реализовать, раз с массивом уже проблемы
// а юзать std::priority_queue<T> и реализации кучи из STL будет совсем уж
// читерством. Дек (deque) был бы быстрее массива, т.к. умеет быстро
// вставлять в начало и в конец, но мы его юзать тоже не будем.
// Не меняя твоего алгоритма, за основу возьмём вектор.
std::vector<Item> items;
public:
PQ(int max) {
items.reserve(max);
}
// деструктор и операторы копирования-присваивания в этом случае нам не нужны
// т.к. лунная призма^W^W магия компилятора и соотв. методы в деке сделают всё сами
int empty() const {
return items.empty();
}
// вставка
// можно вместо bool исключение кинуть, но игнорить вставку - плохое решение
// дай вызывающему возможность самому решать, хочет он игнорить или делать что-то ещё
bool insert(const Item & item) {
// проверим, не полна ли очередь
if (items.size() == items.capacity())
return false;
// найдём первый элемент, который строго больше нового
// мы будем вставлять новый элемент на его место
typename std::vector<Item>::iterator location = std::upper_bound(items.begin(), items.end(), item);
// вставляем новый элемент, сдвигая все элементы, лежащие правее, вправо
items.insert(location, item);
// всё ок
return true;
}
// минимум, удаляем нулевой элемент сдвигая остальные
Item getMin() {
Item tmp = items.front();
items.erase(items.begin());
return tmp;
}
// максимум, здесь всё просто
Item getMax() {
Item tmp = items.back();
items.pop_back();
return tmp;
}
};
int main() {
PQ<int> queue(4);
std::cout << queue.insert(2) << std::endl;
std::cout << queue.insert(4) << std::endl;
std::cout << queue.insert(3) << std::endl;
std::cout << queue.insert(1) << std::endl;
std::cout << queue.insert(7) << std::endl; // false
std::cout << queue.getMax() << std::endl; // 4
std::cout << queue.getMin() << std::endl; // 1
std::cout << queue.getMax() << std::endl; // 3
std::cout << queue.getMax() << std::endl; // 2
std::cout << queue.empty() << std::endl; // true
return 0;
}
// P.S. За кадром остались вопросы о безопасности исключений
// Но надеюсь, что ты и так понял, что с++ - совсем не тот язык, который тебе
// нужен для старта