Кільцева черга. Розробка шаблонного класу, що реалізує кільцеву чергу

Зміст

Пошук на інших ресурсах:

1. Кільцева черга. Загальні відомості

Кільцева черга працює за принципом FIFO (First – In – First – Out): першим прийшов першим вийшов. Відмінність між кільцевою чергою та звичайною чергою полягає в способі виходу з черги першого елементу. У кільцевій черзі перший елемент переміщується в кінець черги. Прикладами кільцевої черги можуть бути рух тролейбусів за кільцевим маршрутом, круговорот води в природі тощо.

Рисунок 1. Кільцева черга. Переміщення першого елементу в кінець черги

Кільцева черга працює за наступним принципом.

Спочатку в чергу додаються елементи до тих пір, поки не буде досягнуто якогось максимуму. Елементи додаються в кінець черги.
Після досягнення певної (максимальної) кількості елементів відбувається циклічна зміна першого елементу за наступним принципом: перший елемент черги переміщується в кінець черги, а всі інші елементи цієї черги зсуваються на одну позицію вперед. Таким чином, другий елемент черги стає першим, третій елемент стає другим і т.д.

Базовий перелік операції, що виконуються для кільцевої черги наступний:

додати новий елемент до черги;
перевірка, чи черга пуста;
перевірка, чи черга повна;
очищення черги (видалення усіх елементів черги);
витягнути перший елемент з черги і помістити в кінець черги.

⇑

2. Особливості програмної реалізації кільцевої черги

У програмній реалізації черга реалізована в класі QueueRing<T> у вигляді динамічного масиву.

У запропонованому класі QueueRing<T> реалізовано наступні внутрішні поля, що зберігають стан черги:

queue – останній елемент в черзі;
count – поточна кількість елементів у черзі (поточна довжина черги);
maxCount – максимальна кількість елементів у черзі (максимальна довжина черги).

Клас QueueRing<T> містить реалізацію наступних методів (функцій):

конструктор QueueRing(int) – створює чергу;
конструктор копіювання QueueRing(const QueueRing&) – викликається при присвоєнні однієї черги іншій під час оголошення;
оператор копіювання QueueRing(const QueueRing&) – викликається у випадку коли одній черзі присвоюється інша;
метод isEmpty() – перевірка, чи черга пуста;
метод Clear() – очищення черги;
метод isFull() – перевірка, чи черга повна;
Add(T) – додати новий елемент до черги;
Move() – витягнути перший елемент з черги і помістити в кінець черги;
метод Print() – вивести елементи черги.

За бажанням, клас QueueRing<T> може бути розширений шляхом додавання нових методів. Наприклад, отримати елемент черги за заданою позицією, додати групу елементів до черги, об’єднати дві черги тощо.

⇑

3. Програмний код шаблонного класу QueueRing<T>, що реалізує кільцеву чергу

#include <iostream>
using namespace std;

// Тема: Кільцева черга
template <typename T>
class QueueRing
{
private:
  T* queue; // останній елемент в черзі
  int count; // поточна довжина черги
  int maxCount; // максимальний розмір черги

  // Метод, що здійснює копіювання черги
  void Copy(const QueueRing<T>& obj)
  {
    // 1. Звільнити попередньо виділену пам'ять для черги
    if (maxCount > 0)
      delete[] queue;

    // 2. Скопіювати дані
    try
    {
      count = obj.count;
      maxCount = obj.maxCount;

      // виділити пам'ять для нової черги
      queue = new T[maxCount];

      // цикл копіювання даних
      for (int i = 0; i < maxCount; i++)
        queue[i] = obj.queue[i];
    }
    catch (bad_alloc e)
    {
      cout << e.what() << endl;
    }
  }

public:
  // Конструктор
  QueueRing(int _maxCount)
  {
    // Створити чергу розміром _maxCount
    try
    {
      maxCount = _maxCount;
      queue = new T[maxCount]; // виділити пам'ять для черги
      count = 0; // поки що черга пуста
    }
    catch (bad_alloc e)
    {
      cout << e.what() << endl;
    }
  }

  // Конструктор копіювання
  QueueRing(const QueueRing& obj)
  {
    Copy(obj);
  }

  // Оператор копіювання
  QueueRing<T> operator=(const QueueRing& obj)
  {
    Copy(obj);
    return *this;
  }

  // Очищення черги
  void Clear()
  {
    count = 0;
  }

  // Деструктор
  ~QueueRing()
  {
    if (maxCount > 0)
      delete[] queue; // звільнити пам'ять, виділену під чергу
  }

  // Перевірка, чи черга пуста?
  bool isEmpty()
  {
    return count == 0;
  }

  // Отримати кількість елементів черги
  int Count()
  {
    return count;
  }

  // Перевірка, чи черга повна?
  bool isFull()
  {
    return count == maxCount;
  }

  // Додати новий елемент до черги
  void Add(T item)
  {
    if (!isFull()) // якщо черга не заповнена
      queue[count++] = item;
  }

  // Витягнути перший елемент з черги і помістити в кінець черги
  bool Move()
  {
    if (!isEmpty()) // Якщо черга заповнена
    {
      // запам'ятати перший елемент
      T item = queue[0];

      // зсув елементів
      for (int i = 1; i < count; i++)
        queue[i - 1] = queue[i];

      // перший елемент записати в кінець черги
      queue[count - 1] = item;
      return true;
    }
    else
      return false;
  }

  // Метод, що виводить чергу
  void Print(string msg)
  {
    cout << msg + " ";
    for (int i = 0; i < count; i++)
      cout << queue[i] << " ";
    cout << endl;
  }
};

void main()
{
  // Створити чергу максимум з 4 елементів типу int
  QueueRing<int> Q(4);
  Q.Print("Q(4): ");

  // Додати до черги елементи
  Q.Add(25);
  Q.Add(30);
  Q.Add(70);
  Q.Add(10);
  Q.Add(7);
  Q.Print("Q.Add(...): ");

  // Зсунути елементи 1 раз
  Q.Move();
  Q.Print("Q.Move(): ");

  // Зсунути елементи ще 1 раз
  Q.Move();
  Q.Print("Q.Move(): ");

  QueueRing<int> Q2 = Q;
  Q2.Print("Q2: ");

  QueueRing<int> Q3 = Q;
  Q3.Print("Q3: ");
}

⇑

4. Пояснення до програмного коду деяких методів класу QueueRing<T>

На початку створюється пуста черга, яка не містить жодного елементу. Конструктор класу QueueRing(int) отримує один параметр: це є максимальний розмір черги. У конструкторі виділяється пам’ять для всього максимально-допустимого розміру черги.

Додавання елементу в кінець черги реалізовано в методі Add(). Елемент додається у випадку, якщо черга ще не заповнена до максимуму. Відбувається порівняння поточної довжини черги count з максимальною довжиною черги maxCount. Якщо черга заповнена (count==maxCount), то елемент в кінець черги не додається.

Після того, як черга досягає свого максимуму, можна реалізовувати циклічне переміщення елементів черги. Це здійснюється в методі Move(), який:

переміщає перший елемент в кінець черги;
здійснює циклічний зсув усіх наступних елементів на одну позицію вперед.

Метод Move() актуальний тільки якщо черга повна (count==maxCount).

Очищення черги здійснюється в методі Clear(). Для реалізації очищення онулюється значення поточної довжини черги. Пам’ять тут звільняти не потрібно.

Оскільки в класі присутній покажчик, то клас містить реалізацію конструктора копіювання та оператора копіювання. Конструктор копіювання та оператор копіювання реалізують коректне використання операції присвоєння (=) однієї черги іншій. Ці методи викликають внутрішній метод Copy(), який робить копію з черги. Конструктор копіювання та оператор копіювання необхідні для уникнення недоліків побітового копіювання. Більш детально про особливості побітового копіювання описується тут.

Деструктор ~QueueRing() звільняє пам’ять, виділену для черги.

BestProg

C++. Кільцева черга. Розробка шаблонного класу, що реалізує кільцеву чергу