Кольцевая очередь. Разработка шаблонного класса, реализующего кольцевую очередь

Содержание

Поиск на других ресурсах:

1. Кольцевая очередь. Общие сведения

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

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

Кольцевая очередь работает по следующему принципу.

Сначала в очередь добавляются элементы до тех пор, пока не будет достигнут какой-то максимум. Элементы добавляются в конец очереди.
После достижения определенного (максимального) количества элементов происходит циклическое изменение первого элемента по следующему принципу: первый элемент очереди перемещается в конец очереди, а остальные элементы этой очереди сдвигаются на одну позицию вперед. Таким образом второй элемент очереди становится первым, третий элемент становится вторым и т.д.

Базовый перечень выполняемых операций для кольцевой очереди следующий:

добавить новый элемент в очередь;
проверка, есть ли очередь пустой;
проверка, есть ли очередь полной;
очистка очереди (удаление всех элементов очереди);
вытянуть первый элемент из очереди и поместить в конец очереди.

⇑

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

В программной реализации очередь реализована в классе QueueRing<T> в виде динамического массива.

В предложенном классе QueueRing<T> реализованы следующие внутренние поля, сохраняющие состояние очереди:

queue – последний элемент в очереди;
count – текущее количество элементов в очереди (текущая длина очереди);
maxCount – максимальное количество элементов в очереди (максимальная длина очереди).

Класс QueueRing содержит реализацию следующих методов (функций):

конструктор 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++. Кольцевая очередь. Разработка шаблонного класса, реализующего кольцевую очередь