Различия

Показаны различия между двумя версиями страницы.


ochered_s_prioritetom [2021/07/31 21:58] (текущий) – создано - внешнее изменение 127.0.0.1
Строка 1: Строка 1:
 +====== Очередь с приоритетом C++, C# (си шарп) ======
 +{{htmlmetatags>
 +metatag-description=(Очередь с приоритетом в C++, C#.)
 +}}
  
 +Мы уже познакомились с двумя типами очередей и они оказались достаточно простыми. Однако существует еще одна очередь - очередь с приоритетом. 
 +
 +Дело в том, что часто необходимо создать очередь, где (извините за тавтологию) очередность выхода зависит от приоритетов элементов. В качестве приоритета может выступать какое-либо число, временная константа и т. п. В момент извлечения элемента будет выбран тот элемент, который обладает большим приоритетом. 
 +
 +Существует несколько видов приоритетных очередей:
 +  - **Очередь с приоритетным включением** - последовательность элементов очереди является строго упорядоченной. Другими словами, каждый элемент при попадании в очередь сразу же располагается согласно своего приоритета. А в момент исключения элемента просто извлекается элемент из начала.
 +  - **Очереди с приоритетным исключение**м - элемент добавляется в конец очереди, а при извлечении осуществляется самого приоритетного элемента, который впоследствии удаляется из очереди. 
 +<note important>Т.е. в очередь или может быстро записывать, но медленно удалять или наоборот. В очередь нельзя быстро удалять или записывать, чем-то нужно жертвовать.</note>
 +====== Реализация - очередь с приоритетами ======
 +<file>
 +#include <iostream>
 +#include <string.h>
 +#include <time.h>
 +using namespace std;
 +
 +class QueuePriority
 +{
 + // Очередь
 + int * Wait;
 + // Приоритет
 + int * Pri;
 + // Максимальный размер очереди
 + int MaxQueueLength;
 + // Текущий размер очереди
 + int QueueLength;
 +
 +public:
 + // Конструктор
 + QueuePriority(int m);
 +
 + //Деструктор
 + ~QueuePriority();
 +
 + // Добавление элемента
 + void Add(int c,int p); 
 +
 + // Извлечение элемента
 + int Extract();        
 +
 + // Очистка очереди
 + void Clear();    
 +
 + // Проверка существования элементов в очереди
 + bool IsEmpty();    
 +
 + // Проверка на переполнение очереди
 + bool IsFull();     
 +
 + // Количество элементов в очереди
 + int GetCount();   
 +
 + //демонстрация очереди
 + void Show();
 +};
 +
 +void QueuePriority::Show(){
 + cout<<"\n-------------------------------------\n";
 + //демонстрация очереди
 + for(int i=0;i<QueueLength;i++){
 + cout<<Wait[i]<<" - "<<Pri[i]<<"\n\n";
 + }
 + cout<<"\n-------------------------------------\n";
 +}
 +
 +QueuePriority::~QueuePriority()
 +{
 + //удаление очереди
 + delete[]Wait;
 + delete[]Pri;
 +}
 +
 +QueuePriority::QueuePriority(int m)
 +{
 + //получаем размер
 + MaxQueueLength=m;
 + //создаем очередь
 + Wait=new int[MaxQueueLength];
 + Pri=new int[MaxQueueLength];
 + // Изначально очередь пуста
 + QueueLength = 0;
 +}
 +
 +void QueuePriority::Clear()
 +{
 + // Эффективная "очистка" очереди 
 + QueueLength = 0;
 +}
 +
 +bool QueuePriority::IsEmpty()
 +{
 + // Пуст?
 + return QueueLength == 0;
 +}
 +
 +bool QueuePriority::IsFull()
 +{
 + // Полон?
 + return QueueLength == MaxQueueLength;
 +}
 +
 +int QueuePriority::GetCount()
 +{
 + // Количество присутствующих в стеке элементов
 + return QueueLength;
 +}
 +
 +void QueuePriority::Add(int c,int p)
 +{
 + // Если в очереди есть свободное место, то увеличиваем количество
 + // значений и вставляем новый элемент
 + if(!IsFull()){
 + Wait[QueueLength] = c;
 + Pri[QueueLength] = p;
 + QueueLength++;
 + }
 +}
 +
 +int QueuePriority::Extract()
 +{
 + // Если в очереди есть элементы, то возвращаем тот, 
 + // у которого наивысший приоритет и сдвигаем очередь
 + if(!IsEmpty()){
 +
 +
 + //пусть приоритетный элемент - нулевой
 + int max_pri=Pri[0];
 + //а приоритетный индекс = 0
 + int pos_max_pri=0;
 +
 + //ищем приоритет
 + for(int i=1;i<QueueLength;i++)
 + //если встречен более приоритетный элемент
 + if(max_pri<Pri[i]){
 + max_pri=Pri[i];
 + pos_max_pri=i;
 + }
 +
 + //вытаскиваем приоритетный элемент
 + int temp1=Wait[pos_max_pri];
 + int temp2=Pri[pos_max_pri];
 +
 + //сдвинуть все элементы
 + for(int i=pos_max_pri;i<QueueLength-1;i++){
 + Wait[i]=Wait[i+1];
 + Pri[i]=Pri[i+1];
 + }
 + //уменьшаем количество
 + QueueLength--;
 + // возврат извлеченного элемента
 + return temp1;
 +
 + }
 + else return -1;
 +}
 +
 +void main()
 +{
 + srand(time(0));
 +
 + //создание очереди
 + QueuePriority QUP(25);
 +
 + //заполнение части элементов
 + for(int i=0;i<5;i++){
 +
 + // значения от 0 до 99 (включительно)
 + // и приоритет от 0 до 11 (включительно)
 + QUP.Add(rand()%100,rand()%12);
 + }
 + //показ очереди
 + QUP.Show();
 +
 + //извлечение элемента
 + QUP.Extract();
 +
 + //показ очереди
 + QUP.Show();
 +}
 +</file>

📌 Удобный подбор VPS по параметрам доступен на DIEGfinder.com - официальном инструменте проекта DIEG. Это часть единой экосистемы, созданной для того, чтобы помочь быстро найти подходящий VPS/VDS сервер для любых задач хостинга.

📌 Для тестирования скриптов, установщиков VPN и Python-ботов рекомендуем использовать надежные VPS на короткий срок. Подробнее о быстрой аренде VPS для экспериментов - читайте здесь.

💥 Подпишись в Телеграм 💥 и задай вопрос по сайтам и хостингам бесплатно!