Шаблон для класса очереди фиксированного размера

Далее показан несложный шаблон класса-очереди ограниченной ёмкости (не более size элементов, 1≤size≤SIZE).

В очереди сохраняется не более size последних помещённых туда элементов, самые старые удаляются.

Наверное, самое простое решение, чтобы сделать шаблон для любых скалярных типов - предусмотреть дополнительный аргумент конструктора (назовём его NaN), принимающий значение, которым будут помечаться пустые элементы. Ведь просто (T)0 не обязано везде работать, а typeid(T).name() тоже не обязано возвращать одно и то же в разных средах.

Также мне было нужно, чтобы очередь потенциально не переполнялась по достижении счётчиками значения INT_MAX, поэтому "сквозной нумерации" элементов в коде нет.

Существенно и то, что методы set и get ничего не знают о порядке своего вызова, можно попытаться получить элемент до добавления, добавлять элементы бесконечно и т.п.

Лучший контроль за значением переменной i, которой мы разрешаем меняться в пределах от 0 до size-1 включительно, выглядит как i++; i %= size;

Ниже приводится исходник, проверенный в Dev C++ 4.9.X, Visual Studio 2015 и QT 5.10.X

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

template <class T> class queue {
 static const int SIZE = 100; //Максимальная размерность
 T q[SIZE]; //Данные
 T NaN; //Признак пустой очереди
 int from, to, size; //Начало, конец, реальная размерность
 int cnt; //Добавлено за последний цикл добавления
public:
 queue (int,T); //Конструктор
 void put (T); //Положить элемент
 T get (); //Забрать элемент
 void show (string); //Вывести с заголовком
};

template <class T> queue<T>::queue (int size, T NaN) {
 from = to = cnt = 0;
 if (size < 1) size = 1;
 if (size > SIZE) size = SIZE;
 this->size = size;
 for (int i=0; i<size; i++) q[i] = NaN;
 this->NaN = NaN;
}

template <class T> void queue<T>::put (T item) {
 if (!cnt) from = to = 0;
 q[to++] = item;
 to %= size;
 cnt++;
 if (cnt > size) {
  cnt = size;
  from++;
  from %= size;
 }
}

template <class T> T queue<T>::get () {
 if (!cnt) return NaN;
 T item = q[from];
 q[from++] = NaN;
 from %= size;
 cnt--;
 return item;
}

template <class T> void queue<T>::show (string msg) {
 cout << endl << msg << ": ";
 for (int i=0; i < size; i++) cout << q[i] << " ";
 cout << endl;
}

int main() {
 queue <int> q (2, 0);
 const int size = 3;
 for (int i=1; i <= size; i++) q.put (i);
 for (int i=1; i <= size; i++) {
  int n = q.get();
  cout << n << " ";
  //не выводить несколько выражений q.get() в одном операторе,
  //будет неверно определена точка следования!
 }
 cout << endl; //2 3 0
 q.put (4);
 cout << q.get() << endl; //4
 cout << q.get() << endl; //0

 const int size2 = 3;
 queue <string> s(size2,"(null)");
 cout << s.get() << endl; //(null)
 s.put("Lilu");
 s.put("Afty");
 for (int i=0; i<size2; i++) {
  string str = s.get();
  cout << str << " "; //Lilu Afty (null)
 }

 cin.get(); return 0;
}

03.09.2019, 16:08 [1273 просмотра]