Срок выполнения задания:
до 17 апреля
Написать реализацию структуры данных "очередь с приоритетом" TPQueue
В лекции Очередь на массиве приводится описание структуры данных Queue, работающей на кольцевом буфере, представляющем собой массив фиксированной длины. Еще одна реализация очереди на кольцевом буфере разбиралась на практическом занятии.
В данной задаче необходимо написать реализацию разновидности очереди - Очередь с приоритетами, работа которой строится по следующей схеме:
Очередь обрабатывает символы, каждому из которых назначается приоритет, - целое число от 1 до 10. При поступлении в очередь элементов, они занимают места, в соответствии с приоритетом: чем он больше, тем ближе к началу очереди. При получении элемента из очереди, вперед идут элементы, чей приоритет больше.
Вставка элемента в очередь должна иметь вычислительную сложность O(n), выборка элемента из очереди, - O(1).
В качестве типа данных T, используемого очередью, возьмем структуру SYM:
struct SYM {
char ch;
int prior;
};
- На основе представленного типа TQueue разработать шаблон очереди с приоритетом TPQueue.
- Предполагается, что тип T внутри очереди будет структурой, состоящей из двух полей, приоритет задается полем prior.
- Поместить описание шаблона TPQueue в файл include/tpqueue.h
- Изучить файл с тестами test/tests.cpp чтобы увидеть примеры использования шаблона очереди с приоритетами.