fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. template<class Item>
  6. class PQ
  7. {
  8. private:
  9.     // По-хорошему, для реализации очереди с приоритетами надо юзать кучу
  10.     // (см. вики по "куча структура данных")
  11.     // но тебе будет сложно ее реализовать, раз с массивом уже проблемы
  12.     // а юзать std::priority_queue<T> и реализации кучи из STL будет совсем уж
  13.     // читерством. Дек (deque) был бы быстрее массива, т.к. умеет быстро
  14.     // вставлять в начало и в конец, но мы его юзать тоже не будем.
  15.     // Не меняя твоего алгоритма, за основу возьмём вектор.
  16. 	std::vector<Item> items;
  17.  
  18. public:
  19.  
  20.     PQ(int max) {
  21.     	items.reserve(max);
  22.     }
  23.  
  24.     // деструктор и операторы копирования-присваивания в этом случае нам не нужны
  25.     // т.к. лунная призма^W^W магия компилятора и соотв. методы в деке сделают всё сами
  26.  
  27. 	int empty() const {
  28. 		return items.empty();
  29. 	}
  30.  
  31.     // вставка
  32.     // можно вместо bool исключение кинуть, но игнорить вставку - плохое решение
  33.     // дай вызывающему возможность самому решать, хочет он игнорить или делать что-то ещё
  34. 	bool insert(const Item & item) {
  35.  
  36. 		// проверим, не полна ли очередь
  37. 		if (items.size() == items.capacity())
  38. 		    return false;
  39.  
  40. 		// найдём первый элемент, который строго больше нового
  41. 		// мы будем вставлять новый элемент на его место
  42.         typename std::vector<Item>::iterator location = std::upper_bound(items.begin(), items.end(), item);
  43.  
  44.         // вставляем новый элемент, сдвигая все элементы, лежащие правее, вправо
  45.         items.insert(location, item);
  46.  
  47.         // всё ок
  48.         return true;
  49. 	}
  50.  
  51.     // минимум, удаляем нулевой элемент сдвигая остальные
  52.     Item getMin() {
  53.     	Item tmp = items.front();
  54.     	items.erase(items.begin());
  55.     	return tmp;
  56.     }
  57.  
  58.     // максимум, здесь всё просто
  59.     Item getMax() {
  60.     	Item tmp = items.back();
  61.     	items.pop_back();
  62.     	return tmp;
  63.     }
  64.  
  65. };
  66.  
  67. int main() {
  68. 	PQ<int> queue(4);
  69. 	std::cout << queue.insert(2) << std::endl;
  70. 	std::cout << queue.insert(4) << std::endl;
  71. 	std::cout << queue.insert(3) << std::endl;
  72. 	std::cout << queue.insert(1) << std::endl;
  73. 	std::cout << queue.insert(7) << std::endl; // false
  74.  
  75. 	std::cout << queue.getMax() << std::endl; // 4
  76. 	std::cout << queue.getMin() << std::endl; // 1
  77. 	std::cout << queue.getMax() << std::endl; // 3
  78. 	std::cout << queue.getMax() << std::endl; // 2
  79.  
  80. 	std::cout << queue.empty() << std::endl; // true
  81. 	return 0;
  82. }
  83.  
  84. // P.S. За кадром остались вопросы о безопасности исключений
  85. // Но надеюсь, что ты и так понял, что с++ - совсем не тот язык, который тебе
  86. // нужен для старта
Success #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
1
1
1
0
4
1
3
2
1
https://ideone.com/kxVx8s
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!