Инструменты пользователя

Инструменты сайта


ochered_s_prioritetom

Различия

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

Ссылка на это сравнение

ochered_s_prioritetom [2018/11/05 16:20] (текущий)
Строка 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>​
ochered_s_prioritetom.txt · Последние изменения: 2018/11/05 16:20 (внешнее изменение)