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

Задание

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

Пояснение

В лекции Очередь на массиве приводится описание структуры данных Queue, работающей на кольцевом буфере, представляющем собой массив фиксированной длины.

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

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

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

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

В качестве основы для работы очереди мы возьмем шаблон класса TQueue:

#include <cassert>
 
template<typename T>
class TQueue
{
private:
    T *arr;          // массив с данными
    int size;        // максимальное количество элементов в очереди (размер массива)
    int begin,       // начало очереди
        end;         // конец очереди
    int count;       // счетчик элементов
public:
    TQueue(int =100);          // конструктор по умолчанию
    ~TQueue();                 // деструктор
 
    void push(const T &); // добавить элемент в очередь
    T pop();              // удалить элемент из очереди
    T get() const;        // прочитать первый элемент
    bool isEmpty() const;      // пустая ли очередь?
    bool isFull() const;       // заполнен ли массив?
};

// конструктор по умолчанию
template<typename T>
TQueue<T>::TQueue(int sizeQueue) :
    size(sizeQueue), 
    begin(0), end(0), count(0)
{
    // дополнительный элемент поможет нам различать конец и начало очереди
    arr = new T[size + 1];
}

// деструктор класса Queue
template<typename T>
TQueue<T>::~TQueue()
{
    delete [] arr;
}


// функция добавления элемента в очередь
template<typename T>
void TQueue<T>::push(const T & item)
{
    // проверяем, ести ли свободное место в очереди
    assert( count < size );
 
    arr[end++] = item;
    count++;
 
    // проверка кругового заполнения очереди
    if (end > size)
        end -= size + 1; // возвращаем end на начало очереди
}

// функция удаления элемента из очереди
template<typename T>
T TQueue<T>::pop()
{
    // проверяем, есть ли в очереди элементы
    assert( count > 0 );
 
    T item = arr[begin++];
    count--;
 
    // проверка кругового заполнения очереди
    if (begin > size)
        begin -= size + 1; // возвращаем begin на начало очереди
 
    return item;
}

// функция чтения элемента на первой позиции
template<typename T>
T TQueue<T>::get() const 
{
    // проверяем, есть ли в очереди элементы
    assert( count > 0 );
    return arr[begin];
}

// функция проверки очереди на пустоту
template<typename T>
bool TQueue<T>::isEmpty() const
{
  return count==0;
}

// функция проверки очереди на заполненность
template<typename T>
bool TQueue<T>::isFull() const
{
  return count==size;
}

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

struct SYM
{
	char ch;
	int prior;
}

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

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

Внимание! Сортировка элементов в очереди недопустима из-за вычислительной сложности!