Лабораторная работа №3
Использование структуры Очередь с приоритетом
Понятие очереди с приоритетом
Очередь является одним из ключевых понятий в многозадачных операционных системах (Windows NT, Unix, OS/2, ЕС и др.). Ресурсы вычислительной системы (процессор, оперативная память, внешние устройства и т.п.) используются всеми задачами, одновременно выполняемыми в среде такой операционной системы. Поскольку многие виды ресурсов не допускают реально одновременного использования разными задачами, такие ресурсы предоставляются задачам поочередно. Таким образом, задачи, претендующие на использование того или иного ресурса, выстраиваются в очередь к этому ресурсу. Некоторые операционные системы для планирования используют очереди с приоритетом. В операционной системе UNIX все процессы имеют разные приоритеты. Когда процессор освобождается, выбирается готовый к исполнению процесс с максимальным приоритетом. Процессы с меньшим приоритетом должны ждать завершения или блокировки (например, внешнего события, такого как чтение данных с диска) процессов с более высокими приоритетами.
Порядок выборки элементов из таких очередей определяется приоритетами элементов. Приоритет в общем случае может быть представлен числовым значением, которое вычисляется либо на основании значений каких-либо полей элемента, либо на основании внешних факторов. FIFO-очереди могут трактоваться как приоритетные очереди, в которых приоритет элемента зависит от времени его включения в очередь. При выборке элемента всякий раз выбирается элемент с наибольшим приоритетом.
Очереди с приоритетами могут быть реализованы на линейных списковых структурах - в смежном или связном представлении.
Рисунок 1.1 - Очередь с приоритетами на основе связанного списка
Возможны два варианта учета приоритета:
1. Приоритетное включение. Последовательность элементов очереди все время поддерживается упорядоченной, т.е. каждый новый элемент включается на то место в последовательности, которое определяется его приоритетом, а при исключении всегда выбирается элемент из начала.
2. Приоритетное исключение. Новый элемент включается всегда в конец очереди, а при исключении в очереди ищется (этот поиск может быть только линейным) элемент с максимальным приоритетом и после выборки удаляется из последовательности. И в том, и в другом варианте требуется поиск, а если очередь размещается в статической памяти - еще и перемещение элементов.
Пример реализации очереди с приоритетом
Очередь с приоритетом является особым случаем обобщенной очереди. Поэтому в примере класс Очередь с приоритетом реализован как наследник класса Очередь.
Сначала надо переопределит тип Т, определяющий элемент очереди.
public class Prioritable<T>
{
public int Priority;
public T Value;
public override string ToString()
{
return Value.ToString()+": "+Priority.ToString();
}
}
Теперь элемент очереди представляет собой класс, состоящий из двух полей: Значение и Приоритет и перегруженного метода ToString() для преобразования элемента очереди в строку. Теперь Очередь с приоритетом будет представлять собой Очередь элементов типа Prioritable<T>.
Очередь с приоритетом отличается от Очереди реализацией методов Добавить элемент и Извлечь элемент.
В примере рассмотрен случай реализации упорядоченной очереди или приоритетного включения. Очередь реализована на массиве. Алгоритм добавления элемента в очередь следующий:
Для пустой очереди вставляемый элемент будет первым, вставка происходит в нулевой элемент массива.
Для непустой очереди ищется место для вставки нового элемента: сравнивается значение текущего приоритета в очереди и приоритета добавляемого элемента. Если приоритет добавляемого элемента больше, то текущий элемент сдвигается на следующую позицию. Затем производится вставка последнего элемента. В тексте программы прокомментировано, какие случаи возможны при вставке.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace WinQueue
{
public class Prioritable<T>
{
public int Priority;
public T Value;
public override string ToString()
{
return Value.ToString()+": "+Priority.ToString();
}
}
class MasQueuePR<T>: MasQuery<Prioritable<T>>
{
public override void Enqueue(Prioritable<T> item)
{
// переносим данные во вспомогательный массив
Prioritable<T>[] buf = new Prioritable<T>[arrayElem.Length];
for (int i = 0; i < buf.Length; i++)
buf[i] = arrayElem[i];
// увеличиваем длину исходного массива на 1
Array.Resize<Prioritable<T>>(ref arrayElem, arrayElem.Length + 1);
// вставка в пустую очередь
if (arrayElem.Length == 1) { arrayElem[0] = item; return; }
// вставка в непустую очередь
int counter = 0;
bool Finded = false;
// всех элементов, кроме последнего
for (int i = 0; i < buf.Length; i++)
{
if ((!Finded)&&(item.Priority >= buf[i].Priority))
{
arrayElem[counter] = item;
i--;
Finded = true;
}
else
arrayElem[counter] = buf[i];
counter++;
}
// вставка последнего элемента
if (!Finded)
arrayElem[counter] = item;
}
public override Prioritable<T> Dequeue()
{
if (IsEmpty) throw new Exception("Queue is empty.");
Prioritable<T> r = arrayElem[0];
Prioritable<T>[] buf = arrayElem;
arrayElem = new Prioritable<T>[arrayElem.Length - 1];
for (int i = 0; i < arrayElem.Length; i++)
arrayElem[i] = buf[i + 1];
return r;
}
}
}
В случае неупорядоченной очереди используется алгоритм приоритетного исключения. Для исключения выбирается элемент с максимальным приоритетом. Затем исходная очередь переписывается в новую очередь, длина которой на 1 меньше, первый элемент, приоритет которого равен найденному максимуму, извлекается.
Индивидуальные задания
1. Реализовать упорядоченную очередь на массиве с приоритетами "низкий", "средний" и "высокий". Каждые 5 тактов таймера выдавать первый элемент.
2. Реализовать неупорядоченную очередь на массиве с приоритетами "низкий", "средний" и "высокий".
3. Реализовать неупорядоченную очередь на массиве с приоритетами "низкий", "средний" и "высокий". Обеспечить частичное упорядочение очереди через каждые 10 такты таймера.
4. Реализовать упорядоченную очередь на массиве с приоритетами от 0(самый низкий) до 9(наивысший). Каждые 30 тактов таймера очищать очередь.
5. Реализовать упорядоченную очередь на массиве с приоритетами от 0(самый низкий) до 9(наивысший). Каждые 10 тактов таймера выдавать первый элемент.
6. Реализовать неупорядоченную очередь на массиве с приоритетами от 0(самый низкий) до 9(наивысший).
7. Реализовать упорядоченную очередь на списках с приоритетами False(низкий) и True(высокий).
8. Реализовать неупорядоченную очередь на списках с приоритетами False(низкий) и True(высокий). Прибавить метод сортировки очереди и кнопку его вызова.
9. Реализовать упорядоченную очередь на списках с приоритетами от 0(наивысший) до 15(самый низкий).
10. Реализовать неупорядоченную очередь на списках с приоритетами от 0(наивысший) до 15(самый низкий).
11. Реализовать упорядоченную очередь на двунаправленных списках с приоритетами от - 5(самый низкий) до +5(наивысший).
12. Реализовать неупорядоченную очередь на двунаправленных списках с приоритетами от - 5(самый низкий) до +5(наивысший).