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

d0bed187d0b5d180d0b5d0b4d18c d181 d0bfd180d0b8d0bed180d0b8d182d0b5d182d0b0d0bcd0b8 статьи

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

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

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

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

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

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

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

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

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

Файл QueuePriority.h

Файл QueuePriority.с

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

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

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

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

Каталог сайтов Всего.ру
Оцените статью
Секреты программирования
Добавить комментарий