Очередь с приоритетами

Я уже писал ранее, что представляет из себя структура данных типа очередь, однако порой случаются такие ситуации, когда, глядя на структуру данных, с одной стороны кажется, что это — очередь, а с другой — что-то не похожа. Рассмотрим пример. Допустим несколько человек стоят в очереди на прием к врачу. Через некоторое время подходит еще один и говорит, что ему мол только спросить. Предположим, его пропустили, тогда получается, что он автоматически стал в голову очереди, и войдет в кабинет первым из всех ожидающих. Данный пример — ни что иное, как пример очереди с приоритетами.

Понятие очереди с приоритетами

Очередь с приоритетами — это очередь в которой включение либо исключение, элементов производится в соответствии с их приоритетами.

Исходя из определения, можно выделить два вида таких очередей:

  1. С приоритетным включением
  2. С приоритетным исключением

Очередь с приоритетным включением

Очередь с приоритетным включением — такая очередь, в которой последовательность элементов все время поддерживается упорядоченной по убыванию приоритета. То есть, при включении элемента, выполняется поиск места, куда он будет включен, а затем происходит сама процедура включения. При исключении же будет удален элемент, стоящий в начале.

Очередь с приоритетным исключением

Очередь с приоритетным исключением — очередь, в которой включение элементов осуществляется в конец, а при исключении производится поиск элемента с максимальным приоритетом.

Задание приоритета

Поговорим о том, что такое приоритет, и, как его задать. В качестве приоритета может выступать что угодно, что Вы сами захотите, например время или стоимость. Все это зависит от того, для каких целей Вы используете очередь. Кстати, если в качестве приоритета рассматривать время включения элемента, то можно считать, что кольцевая очередь и стек являются частными случаями очередей с приоритетами.

Для задания приоритета используется структура с двумя полями данные и приоритет.

typedef struct {
int data;							// Данные
int priority;						// Приоритет
} baseType;

Реализация на языке C

С теорией разобрались, приступим теперь к самой реализации. Как всегда все файлы будут написаны на языке С (Си).

Файл QueuePriority.h

/****************************************/
/*			Очередь с приоритетами		*/
/****************************************/
#ifndef _QUEUE_PRIORITY_H_
#define _QUEUE_PRIORITY_H_
/*Размер очереди*/
#define SIZE_QUEUE_PRIORITY 5
/*Описание исключительных ситуаций*/
const int okQueuePriority = 0;			// Все нормально
const int fullQueuePriority = 1;		// Очередь переполнена
const int emptyQueuePriority = 2;		// Очередь пуста
/**********************************/
/*Переменная ошибок*/
extern int errorQueuePriority;
/*Базовый тип очереди*/
typedef struct {
int data;							// Данные
int priority;						// Приоритет
} queuePriorityBaseType;
/*Дескриптор очереди*/
typedef struct {
queuePriorityBaseType buf[SIZE_QUEUE_PRIORITY];	// Буфер очереди
unsigned uk;									// Указатель на хвост
} QueuePriority;
/********************/
/*Функции работы с очередью*/
void initQueuePriority(QueuePriority *F);							// Инициализация очереди
void putQueuePriority(QueuePriority *F, queuePriorityBaseType E);	// Включение в очередь
void getQueuePriority(QueuePriority *F, queuePriorityBaseType *E);	// Исключение из очереди
int isFullQueuePriority(QueuePriority *F);							// Предикат: полна ли очередь
int isEmptyQueuePriority(QueuePriority *F);							// Предикат: пуста ли очередь
/***************************/
#endif

Файл QueuePriority.с

/****************************************/
/*			Очередь с приоритетами		*/
/****************************************/
#include <stdio.h>
#include "QueuePriority.h"
/*Переменная ошибок*/
int errorQueuePriority;
/*Инициализация очереди*/
void initQueuePriority(QueuePriority *F) {
F->uk = 0;
errorQueuePriority = okQueuePriority;
}
/*Включение в очередь*/
void putQueuePriority(QueuePriority *F, queuePriorityBaseType E) {
/*Если очередь переполнена*/
if (isFullQueuePriority(F)) {
return;
}
/*Иначе*/
F->buf[F->uk] = E;
F->uk++;
}
/*Исключение из очереди*/
void getQueuePriority(QueuePriority *F, queuePriorityBaseType *E) {
/*Если очередь пуста*/
if (isEmptyQueuePriority(F)) {
return;
}
/*Иначе поиск элемента с максимальным приоритетом*/
queuePriorityBaseType max = F->buf[0];			// Максимальным примем 1-й элемент
int maxPos = 0;									// Позиция элемента в макс. приоритетом
for (unsigned i = 1; i < F->uk; i++) {			// Для всех элементов начиная со второго выполнить
if (F->buf[i].priority > max.priority) {		// поиск элемента с максимальным приоритетом
max = F->buf[i];
maxPos = i;
}
}
/*Максимальный найден. Производим исключение*/
*E = max;											// Запись данных в переменную
F->buf[maxPos] = F->buf[--F->uk];					// Установка на позицию исключаемого элемента последнего
// Уменьшение длины очереди
}
/*Предикат: полна ли очередь*/
int isFullQueuePriority(QueuePriority *F) {
if (F->uk == SIZE_QUEUE_PRIORITY) {
errorQueuePriority = fullQueuePriority;
return 1;
}
return 0;
}
/*Предикат: пуста ли очередь*/
int isEmptyQueuePriority(QueuePriority *F) {
if (F->uk == 0) {
errorQueuePriority = emptyQueuePriority;
return 1;
}
return 0;
}

Думаю, что в пояснении нет смысла, так как комментариев достаточно, если что непонятно, пишите в комментариях, а на этом все.

2 отзыва на “Очередь с приоритетами

  1. Людмила

    А как включается элемент в очередь с приоритетным включением? Допустим, нашли элемент большего приоритета, чем включаемый элемент, и следующий за ним элемент меньшего приоритета ( т.е. нашли место для вставки). Теперь, получается нужно сдвигать элемент меньшего приоритета и все, следующие за ним вправо и тогда вставлять элемент?

  2. Mike_Device

    Верно, но это только в том случае, если очередь реализована на массиве (как в статье). Если же очередь делать на списке, то там достаточно будет сделать перемычку указателей.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *