C++. Пример реализации очереди с приоритетами для шаблонного класса. Реализация в виде динамического массива

Пример реализации очереди с приоритетами для шаблонного класса. Реализация в виде динамического массива

Перед изучением данной темы рекомендуется ознакомиться со следующей темой:


Содержание


1. Способы реализации очереди с приоритетами

Очередь с приоритетами может быть реализована одним из двух способов:

  • как очередь с приоритетным включением (рисунок 1). При этом способе элемент добавляется в очередь в соответствии с его приоритетом. Вытягивается элемент обычным способом – от начала очереди;
  • как очередь с приоритетным исключением (рисунок 2). При этом способе элемент добавляется в конец очереди а вытягивается в соответствии с его приоритетом. В случае равенства приоритетов, первым вытягивается тот элемент, который был первым размещен в очереди (элемент, более близкий к началу очереди).

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

Рисунок 1. Очередь с приоритетным включением

Динамическая структура данных очередь с приоритетным исключением

Рисунок 2. Очередь с приоритетным исключением

 

2. Пример реализации очереди с приоритетами для шаблонного класса в виде динамического массива
2.1. Общее описание работы программы

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

В классе QueueP объявляются:

  • A – динамический массив элементов типа T. Эти элементы образовывают очередь;
  • P – динамический массив приоритетов каждого элемента из массива A. Элементу A[0] соответствует приоритет P[0], элементу A[1] соответствует приоритет P[1] и т.д. Количество элементов в массивах A и P одинаково;
  • count – текущее количество элементов в очереди;
  • конструктор по умолчанию QueueP();
  • конструктор копирования QueueP(const QueueP&);
  • деструктор ~QueueP();
  • оператор копирования operator=(const QueueP&);
  • функция Push(), добавляющая новый элемент в очередь;
  • функция Pop(), вытягивающая элемент из очереди;
  • функция Clear() – реализующая очистку очереди;
  • функция Count() – возвращает количество элементов в очереди.

По желанию можно добавить другие дополнительные функции для работы очереди.

 

2.2. Исходный код программы

Исходный код программы, которая реализует класс QueueP следующий.

#include <iostream>
#include <new>
using namespace std;

// Очередь с приоритетами для типа T
template <typename T>
class QueueP
{
private:
  T* A; // динамический массив элементов типа T
  int* P; // массив приоритетов
  int count; // количество элементов в очереди

public:
  // конструктора
  // конструктор без параметров
  QueueP() { count = 0; }

  // конструктор копирования
  QueueP(const QueueP& _Q)
  {
    try {
      // попытка выделить память
      A = new T[_Q.count];
      P = new int[_Q.count];
    }
    catch (bad_alloc e)
    {
      // если память не выделилась то обработать ошибку
      cout << e.what() << endl;
      count = 0;
      return;
    }

    // скопировать _Q => *this
    count = _Q.count;

    // поэлементное копирование данных
    for (int i = 0; i < count; i++)
      A[i] = _Q.A[i];

    for (int i = 0; i < count; i++)
      P[i] = _Q.P[i];
  }

  // деструктор
  ~QueueP()
  {
    if (count > 0)
    {
      delete[] A;
      delete[] P;
    }
  }

  // оператор копирования - чтобы избежать побитового копирования
  QueueP operator=(const QueueP& _Q);

  // функция, добавляющая в очередь новый элемент
  void Push(T item, int priority);

  // функция, витягивающая из очереди первый элемент
  T Pop();

  // очистка очереди
  void Clear()
  {
    if (count > 0)
    {
      delete[] A;
      delete[] P;
      count = 0;
    }
  }

  // возвращает количество элементов в очереди
  int Count()
  {
    return count;
  }

  // функция, выводящая очередь
  void Print(const char* objName);
};

// оператор копирования
template <typename T>
QueueP<T> QueueP<T>::operator=(const QueueP& _Q)
{
  // 1. Освободить память, которая была перед этим выделена для текущего объекта
  if (count > 0)
  {
    delete[] A;
    delete[] P;
    count = 0;
  }

  // 2. Попытка выделить новый фрагмент памяти
  try {
    A = new T[_Q.count];
    P = new int[_Q.count];
  }
  catch (bad_alloc e)
  {
    // если память не выделена, то выход
    cout << e.what() << endl;
    return *this; // вернуть пустую очередь
  }

  // 3. Если память выделена, то копирование *this <= _Q
  count = _Q.count;

  // 4. Цикл копирования данных
  for (int i = 0; i < count; i++)
  {
    A[i] = _Q.A[i];
    P[i] = _Q.P[i];
  }
  return *this;
}

// добавляет в очередь новый элемент item с приоритетом priority
template <typename T>
void QueueP<T>::Push(T item, int priority)
{
  // 1. Создать новый массив-очередь и массив-приоритет
  T* A2;
  int* P2;

  try {
    // попытка выделить память для нового массива
    A2 = (T*)new T[count + 1];
    P2 = (int*)new int[count + 1];
  }
  catch (bad_alloc e)
  {
    // если память не выделена, то выход
    cout << e.what() << endl;
    return;
  }

  // 2. Поиск позиции pos в массиве P согласно с приоритетом priority
  int pos;

  if (count == 0)
    pos = 0;
  else
  {
    pos = 0;
    while (pos < count)
    {
      if (P[pos] < priority) break;
        pos++;
    }
  }

  // 3. Копирование данных A2<=A; P2<=P
  // по формуле P = [0,1,...] + pos+1 + [pos+2,pos+3,...]
  // 3.1. Индексы массива с номерами 0..pos
  for (int i = 0; i < pos; i++)
  {
    A2[i] = A[i];
    P2[i] = P[i];
  }

  // 3.2. Добавить элемент в позиции pos
  A2[pos] = item;
  P2[pos] = priority;

  // 3.3. Элементы после позиции pos
  for (int i = pos + 1; i < count + 1; i++)
  {
    A2[i] = A[i - 1];
    P2[i] = P[i - 1];
  }

  // 4. Освободить память, предварительно выделенную для A и P
  if (count > 0)
  {
    delete[] A;
    delete[] P;
  }

  // 5. Перенаправить указатели A->A2, P->P2
  A = A2;
  P = P2;

  // 6. Увеличить количество элементов в очереди на 1
  count++;
}

// Функция, вытягивающая из очереди первый элемент
template <typename T>
T QueueP<T>::Pop()
{
  // 1. Проверка
  if (count == 0)
    return 0;

  // 2. Объявить временные массивы
  T* A2;
  int* P2;

  // 3. Попытка выделить память для A2, P2
  try {
    A2 = new T[count - 1]; // на 1 элемент меньше
    P2 = new int[count - 1];
  }
  catch (bad_alloc e)
  {
    // если память не выделена, то вернуть 0 и выход
    cout << e.what() << endl;
    return 0;
  }

  // 4. Запомнить первый элемент
  T item;
  item = A[0];

  // 5. Скопировать данные из массивов A=>A2, P=>P2 без первого элемента
  for (int i = 0; i < count - 1; i++)
  {
    A2[i] = A[i + 1];
    P2[i] = P[i + 1];
  }

  // 6. Освободить предварительно выделенную память для A, P
  if (count > 0)
  {
    delete[] A;
    delete[] P;
  }

  // 7. Поправить количество элементов в очереди
  count--;

  // 8. Перенаправить указатели A->A2, P->P2
  A = A2;
  P = P2;

  // 9. Вернуть первый элемент очереди
  return item;
}

// Функция, выводящая очередь на экран
template <typename T>
void QueueP<T>::Print(const char* objName)
{
  cout << "Object: " << objName << endl;
  for (int i = 0; i < count; i++)
    cout << A[i] << ":" << P[i] << "\t" << endl;
  cout << endl;
  cout << "---------------" << endl;
}

void main()
{
  QueueP<int> Q1;
  QueueP<int> Q2 = Q1;

  Q1.Push(15, 7);
  Q1.Push(18, 9);
  Q1.Push(18, 9);
  Q1.Push(18, 9);
  Q1.Push(1, 3);
  Q1.Push(8, 6);
  Q1.Push(11, 6);
  Q1.Push(4, 6);
  Q1.Print("Q1");

  int d;
  d = Q1.Pop();
  d = Q1.Pop();
  d = Q1.Pop();
  d = Q1.Pop();
  Q1.Print("Q1");
  cout << "d = " << d << endl;

  QueueP<int> Q3 = Q1; // конструктор копирования
  Q3.Print("Q3");

  QueueP<int> Q4;
  Q4 = Q3 = Q1; // оператор присваивания копированием
  Q4.Print("Q4");

  cout << "count = " << Q4.Count() << endl;
  Q4.Clear();
  Q4.Print("Q4");
  cout << "count = " << Q4.Count() << endl;
}

 

3. Результат выполнения программы

Результат работы программи приведен ниже

Object: Q1
18:9
18:9
18:9
15:7
8:6
11:6
4:6
1:3

---------------
Object: Q1
8:6
11:6
4:6
1:3

---------------
d = 15
Object: Q3
8:6
11:6
4:6
1:3

---------------
Object: Q4
8:6
11:6
4:6
1:3

---------------
count = 4
Object: Q4

---------------
count = 0

 


Связанные темы