Последние записи

Интенсив по Python: Работа с API и фреймворками 24-26 ИЮНЯ 2022. Знаете Python, но хотите расширить свои навыки?
Slurm подготовили для вас особенный продукт! Оставить заявку по ссылке - https://slurm.club/3MeqNEk

Online-курс Java с оплатой после трудоустройства. Каждый выпускник получает предложение о работе
И зарплату на 30% выше ожидаемой, подробнее на сайте академии, ссылка - ttps://clck.ru/fCrQw

27th
Фев

Шаблон класса односвязной очереди в библиотеке STL

Posted by Chas under Журнал, Статьи

В свое время, изучая все богатство возможностей библиотеки STL и, применяя эти возможности на практике, обнаружил, что основным необходимым мне контейнером является односвязная очередь типа FIFO: «первым зашел – первым вышел». В одной из своих программ насчитал 27 очередей под различные типы данных. Видимо это связано со спецификой разрабатываемых программ: взаимодействие с различными внешними устройствами, также разработанных нашей фирмой. Обмен ведется сообщениями через последовательные интерфейсы: COM, USB, протокол TCP/IP…

Вячеслав Мовила
http://movila.site11.com

Предпосылки реализации…

Такого контейнера – односвязной очереди, типа FIFO, в библиотеке STL не существует. Есть удобный адаптер под стандартные типы контейнеров STL. Но! Вот всегда это самое «Но» и в самых неожиданных местах! Практика научила, что использовать библиотеку STL следует с определенной долей осторожности. Реализации библиотеки отличаются в зависимости от компилятора. Например, некоторые реализации подразумевают потоковую безопасность, некоторые – нет. По мне, так потоковую безопасность легче организовать программисту на прикладном уровне. Тем более, если в ней нет необходимости, а в вашей реализации она существует, то это просто ведет к увеличению накладных расходов.

В моем случае пришла мысль о написании простого, компактного шаблона односвязной очереди, что называется «без всяких затей». Листинг шаблона приводится ниже:

/—————————————————————————
#ifndef PQueueH
#define PQueueH
//—————————————————————————
// Структура определяющая узел очереди.
template <class T>
struct QueueNode {
T data;
QueueNode * next;
QueueNode() { next = 0; }
};
 
//—————————————————————————
// Темплетный универсальный класс очереди.
template <class Q>
class TPQueue {
private:
QueueNode<Q> * BeginQ, * LastQ;
// Счетчик объектов в очереди.
long count;
public:
TPQueue();
~TPQueue();
bool PutQueue(Q data);
bool CheckQueue();
Q GetQueue();
bool ClearQueue();
long size() { return count; }
};
 
//—————————————————————————
// Конструктор.
template <class Q>
TPQueue<Q> :: TPQueue() {
BeginQ = 0;
LastQ = 0;
count = 0;
}
 
//—————————————————————————
// Деструктор — освобождаем очередь и память выделенную под объекты.
template <class Q>
TPQueue<Q> :: ~TPQueue() {
QueueNode<Q> * work;
 
while(BeginQ) {
work = BeginQ->next;
delete BeginQ;
BeginQ = work;
}
BeginQ = 0;
LastQ = 0;
count = 0;
}
 
//—————————————————————————
// Положить в очередь.
template <class Q>
bool TPQueue <Q> :: PutQueue(Q data) {
QueueNode<Q> * link = new QueueNode<Q>;
 
count++;
if(!BeginQ) {
link->data = data;
BeginQ = link;
LastQ = link;
}
else {
link->data = data;
LastQ->next = link;
LastQ = LastQ->next;
}
return true;
}
 
//—————————————————————————
// Проверить состояние очереди.
template <class Q>
bool TPQueue <Q> :: CheckQueue() {
if(BeginQ) return true;
else return false;
}
 
//—————————————————————————
// Изъять из очереди.
template <class Q>
Q TPQueue <Q> :: GetQueue() {
QueueNode<Q> * link;
Q p;
 
if(BeginQ) {
count—;
link = BeginQ;
BeginQ = BeginQ->next;
if(!BeginQ) LastQ = 0;
p = link->data;
delete link;
return p;
}
else return 0;
}
 
//—————————————————————————
// Очистить очередь.
template <class Q>
bool TPQueue <Q> :: ClearQueue() {
QueueNode<Q> * link;
 
while(BeginQ) {
link = BeginQ;
BeginQ = BeginQ->next;
if(!BeginQ) LastQ = 0;
delete link;
}
count = 0;
return true;
}
//—————————————————————————
#endif // PQueueHSyhi-подсветка кода

Посткриптум

Текст листинга достаточно прост и не требует комментариев. Пример использует две очереди (первая для типа int, вторая для AnsiString). Шаблон класса односвязной очереди содержится в файле <PQueue.h>.

Полные исходные тексты и компиляция проекта (файл myFIFO.rar) приложены к статье непосредственно в журнале.

Ресурсы

Пример использования шаблона класса односвязной очереди http://movila.site11.com/attachments/015_myFIFO.rar
Компилятор Builder C++ 6 http://www.brothersoft.com/borland-c++-builder-118249.html

Статья из десятого выпуска журнала «ПРОграммист».

Обсудить на форуме — Шаблон класса односвязной очереди в библиотеке STL