Алгоритмы и структуры данных (ADS-6)

Срок выполнения задания:

по 10.05.2026

Задание

Написать реализацию структуры данных "очередь с приоритетом" TPQueue на связанном списке

Пояснение

В данной задаче необходимо написать реализацию разновидности очереди - Очередь с приоритетами, работа которой строится по следующей схеме:

Очередь обрабатывает символы, каждому из которых назначается приоритет, - целое число от 1 до 10. При поступлении в очередь элементов, они занимают места, в соответствии с приоритетом: чем он больше, тем ближе к началу очереди. При получении элемента из очереди, вперед идут элементы, чей приоритет больше.

Вставка элемента в очередь должна иметь вычислительную сложность O(n), выборка элемента из очереди, - O(1).

В качестве типа данных T, используемого очередью, возьмем структуру SYM:

struct SYM {
  char ch;
  int prior;
};

Шаблон очереди должен обязательно включать в себя методы:

• push() - для помещения элемента в очередь
• pop() - для извлечения элемента из очереди

Программная реализация

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

Сам список должен быть односвязным.

Реализация представляет из себя шаблон, описание которого целиком располагается в include/tpqueue.h.

Вот пример того, как очередь может использоваться:

#include "tpqueue.h"

int main() {
    TPQueue<SYM> pqueue;
    pqueue.push(SYM{'a', 4});
    pqueue.push(SYM{'b', 7});
    SYM c1 = pqueue.pop();
    SYM c2 = pqueue.pop();
    return 0;
}

Выполнение работы

• Предполагается, что тип T внутри очереди будет структурой, состоящей из двух полей, приоритет задается полем prior.
• Поместить описание шаблона TPQueue в файл include/tpqueue.h
• Изучить файл с тестами test/tests.cpp чтобы увидеть примеры использования шаблона очереди с приоритетами.