Цель занятия: Практическое изучение способов объектно-ориентированной обработки очредей данных с использованием простого наследования классов в системе программирования С++ на примере моделирования процесса циклического обслуживания конечного множества элементов.

Формулировка задания:Требуется разработать программу JOSEPH для моделирования порядка обслуживания конечного набора элементов в условиях задачи Иосифа. В этой задаче предполагается, что заданное конечное число элемнтов N>1, подлежащих обслуживанию образуют круг, где каждый элемент идентифицируется уникальным порядковым номером от 1 до N. Для обслуживания элементов осуществляется обход круга, начиная с заданного номера.Контроль обхода по кругу осуществляется по счетчику шагов с начальным значением 1.
Когда значение счетчика достигает априори заданной пороговой отметки m>1, соответствующий текущему шагу элемент извлекается из круга, круг смыкается, счетчик инициализируется начальным значением 1 и продолжается обход оставшихся элементов. Обход круга должен продолжаться, пока не извлечены все элементы. Необходимо определить очередность извлечения элементов из круга. Исходными данными программы joseph являются: начальное число элементов круга обслуживания, пороговое значение счетчика шагов и номер стартового элемента обхода. Исходные данные должны передаваться программе joseph через параметры командной строки ее вызова. Для представления круга обслуживания элементов необходимо использовать структуру очереди с кольцевым буфером, размер и начальное наполнение которой определяется исходными данными. Результат работы программы joseph должен отображать очередность номеров исключения элементов. Номера исключаемых элементов должны отображаться через поток стандартного вывода (stdout). Программа joseph должна быть составлена в системе программирования С++ с использованием инкапсуляции данных и простого наследования классов.

Очередь (Queue) - это абстракная структура для работы с последовательностью данных, обслуживание которых происходит в соответствии с дисциплиной FIFO (FIRST IN, FIRST OUT - первым пришел, первым обслужен). Согласно принципу FIFO новые данные добавляются (записываются) в хвост очереди, а наличные данные извлекаются (считываются) из головы очереди. Извлекать данные из очереди и добавлять их в очередь можно неоднократно, пока очередь не пуста и не пререполнена, соответственно.
Состояние очереди характеризуется парой указателей: tail - указатель на хвост (конец) очереди и head - указатель на голову (начало) очереди. При изменении содержания очереди за счет чтения или записи данных меняется состояние очереди и соответственно, значение указателей на ее голову или хвост. Новые данные записываются в ячейку очереди, адрес которой определяет значение указателя tail. После этого значение tail изменяется так, чтобы указывать на следующую свободную ячейку очереди. Чтение существующих данных происходит из ячейки, адрес которой определяет указатель head. После этого указатель head изменяется таким образом, чтобы указывать на следующий занятый элемент очереди.
Для хранения данных в очереди выделяется специальный буфер qbuf (queue bufer). В простейшем случае буфер очереди реализуется одномерным массивом элементов, длина которого априори устанавливает предельный размер очереди qsize (queue size), задаваемый при создании очереди. Такая организация очереди называется очередью с линейным фиксированным буфером (Line queue).
Указатели на хвост и голову очереди интерпретируются в ней как целочисленные индексы массива, представляющего буфер очереди. В начальном состоянии очередь пуста и оба указателя имеют нулевое значение (tail=head=0).
Логическую структуру очереди с линейным фиксированным буфером, где размещены 5 элементов # иллюстрирует следующая диаграмма:

Рис. Логическая структура очереди с линейным фиксированным буфером

Рассмотренный линейный вариант очереди с фиксированным линейным буфером имеет ограниченное применение, т. к. для корректной работы значение указателя головы очереди не должно превышать значения указателя на хвост очереди (head<=tail). Это условие не позволяет добавлять новые элементы, когда хвост очереди исчерпан (tile=qsize), даже если в начале буфера очереди имеются свободные ячейки, после извлечения головных элементов (head>0). Это тупиковое состояние переполнения очереди с линейным фиксированным буфером показано на следующем рисунке, где 8 элементов # занимают конечные ячецки буфера очереди, а в его начале имеются 2 свободные ячейки:

Рис. Переполнение очереди с линейным фиксированным буфером

Чтобы иметь возможность использовать свободные ячейки в начале буфера очереди, которые образовались после чтения головных элементов, нужно пременять более совершенную организацию очереди, известную как очередь с кольцевым фиксированным буфером (RingQueue). Кольцевой фиксированный буфер следует рассматривать как замкнутый линейный буфер qbuf, который после заполнения его до конца может заполняться сначала, если там имебтся свободные ячейки. Чтобы превратить лнейный буфер в колцевой достаточно интерпретировать указатели головы и хвоста очереди как целочисленные индексы массива qbuf, взятые по модулю размера очереди (qsize).

  head mod qsize и tail mod qsize,

соответственно.Операция mod здесь интерпретируется как вычисление остатка целочисленного деления head и tail на qsize. Таким образом,  любой из указателей обнуляется, когда его значение становится равным qsize, т. е. выходит за границы массива буфера очереди, например:

  IF head = qsize THEN head <- 0;
 и IF tail = qsize THEN tail <- 0.

Жесткое условие корректности непустой очереди с линейным фиксированным буфером (head<tail) в очереди с кольцевым буфером становится необязательным, т. е. состояние, когда указатель хвоста опережает указатель головы очереди (tail<head) также является разрешенным. Оба разрешенных состояния очереди с фиксированным кольцевым буфером показаны на следующем рисунке:

Рис. Состояния очереди с кольцевым буфером

Для работы с очередью используются 2 классических примитива: ENQUEUE и DEQUEUE, которые обеспечивают добавление (запись) данных в очередь и извлечение (чтение) данных из очереди, соответственно. В очереди с кольцевым буфером они имеют реализацию рассмотренную ниже.
Примитив DEQUEUE возвращает элемент из головы очереди и увеличивает на 1 значение указателя head. Если значение head при этом выходит за границу буфера очереди, то head следует обнулить. Псевдокод примитива DEQUEUE выражает следующие операторы:

  W <- qbuf [head];
  head <- head+1 mod qsize;
  return W;

где W обозначает элемент данных, извлекаемый из очереди.
Примитив ENQUEUE загружает новый элемент в хвост очереди и увеличивает на 1 значение указателя tail. Если значение tail при этом выходит за границу буфера очереди, то tail следует обнулить. Псевдокод примитива ENQUEUE выражает следующие операторы:

  qbuf [tail] <- V;
  tail <- tail+1 mod qsize;
  return;

где V обозначает элемент данных, извлекаемый из очереди.
Для очереди с фиксированным кольцевым буфером процедура извлечения (чтения) данных необязательно является деструктивной операцией, т. е. извлеченные элементы не уничтожаются в буфере очереди до записи на их место новых данных. Процедура добавления (записи) данных имеет деструктивный эффект, модифицируя содержание буфера очереди. Рассмотренные примитивы DEQUEUE и ENQUEUE обеспечивают корректную обработку очереди с фиксированным кольцевым буфером, когда он не пуст и не переполнен соответственно. Для корректной обработки этих критических ситуаций нужно установить соотношение указателей, при которых кольцевой буфер будет пуст или переполнен.
Критическим состоянием при чтении данных является пустая очередь, где все ячейки свободны. Формальным условием пустой очереди является равенство обоих указателей:

    tail = head

Проверку пустой очереди можно использовать в сочетании с примитивом DEQUEUE, чтобы избежать потери значимости при попытке извлечь данные, когда их нет. Критическим состоянием при записи данных является переполнение очереди, когда все ячейки заняты, формальным условием переполнения очереди с круговой организацией является следующее соотношение указателей:

   head = tail+1  mod  qsize

Усли выполняетсяэто соотношение, нельзя добавлять элементы в очередь, несмотря на то, что имеется 1 свободная ячейка, на которую указывает текущее значение tail. Иначе критериемпереполнения очереди было бы равенство tail=head, которое является истинным также для пустой очереди. Чтобы иметь возможность отличать оба критических состояния очереди с кольцевым буфером, в нем должно содержаться от 0 до (qsize-1) значащих элементов при неменее, чем одной свободной ячейке. Указанную проверку переполнения можно использовать в сочетании с примитивом ENQUEUE, чтобы избежать потери значимости при попытке запичи данных, когда исчерпан лимит свободных ячеек.

Очередь с круговым буфером является удобной и естественной абстрактной структурой данных для моделирования обхода элементов пао кругу в условиях задачи Иосифа по алгоритму, который можно условно назвать алгоритмом кругового обслуживания. Алгоритм кругового обслуживания составляет следующая последовательность шагов:

1. Заготовить пустую очередь с размером колцевого буфера на 1 больше, чем число обслуживаемых элементов.
2. Применяя примитив ENQUEUE соответствующее число раз, разместить номера всех обслуживаемых элементов в кольцевом буфере очереди, что эквивалентно расположению элементов по кругу.
3. Чередуя вызовы примитивов DEQUEUE и ENQUEUE необходимое число раз, добиться чтобы в голове очереди оказался элемент с желаемым номером.
4. Инициализировать счетчик шагов по кругу значением 1.
5. Чередовать вызовы примитивов DEQUEUE и ENQUEUE при квеличении значения счетчика шагов, пока оно не достигнет заданного порогового значения. Эти действия эквивалентны обходу круга, чтобы достигнуть элемента, который нужно удалить их очереди. Исключаемый элемент будет находиться в голове очереди.
6. Используя процедуру DEQUEUE удалить эелемент из головы очереди и распечатать его номер.
7. Проверить выполнение условия пустой очереди (tail=head). Если в очереди еще остались элементы, перейти на шаг 4 для продолжения анализа очередности удаления элементов. Иначе, если очередь пуста, завершить выполнение алгоритма.

Для программирования очереди с кольцевым буфером целесообразно применить принцип инкапсуляции объектно-ориентированного программирования, сосредоточив описание структуры очереди и примитивов ее обработки в отдельном классе RingQueue. Организация класса RingQueue должна быть ориентирована на применение его в качестве базового класса для построения производных классов, обладающих спецификой обработки кольцевой очереди в различных приложениях.
Класс RingQueue должен содержать защищенные (protected) компоненты-данные и общедоступные (public) компонентные методы их обработки. Это обеспечит доступ к данным класса только собственным компонентным методам производного класса, но исключит возможность непосредственного несанкционированного обращения к ним из любых внешних функций программы.
Чтобы исключить зависимость компонентов класса RingQueue от типа элементов очереди, при его проектировании удобно восполдьзоваться средствами параметризации классов и функций, поддержка которых обеспечена в любых версиях системы программирования С++, начиная с USL 3.0. Параметризация класса осуществляется с помощью шаблона (template), который декларирует абстрактные типы данных как параметры класса. Они могут быть использованы для абстрактной типизации компонент-данных или кодов возврата и аргументов компонентных методов класса. В данном случае в шаблоне класса RingQueue может быть объявлен абстрактный тип <class QType>, обозначающий тип элементов очереди. Учитывая синтаксические особенности шаблонов классов в системе программирования С++, декларация логической структуры класса RingQueue может иметь следующий формат:

  template <class QType> class RingQueue
  {
  protected:
   /*спецификация компонент-данных*/
  public:
   /*спецификация прототипов компонентных методов*/
  };

Конкретизайия типа параметризованных компонент шаблонного класса должна быть выполнена либо в производном нешаблонном классе или при определении объекта класса, когда он предназначается для непосредственного использования.
В защищенную (protected) часть декларации класса RingQueue целесообразно включить спецификацию следующих компонент-данных*

QType* qbuf:  /*адрес буфера очереди*/
 int qsize;    /*размер очереди*/
 int head;     /*указатель головы очереди*/
 int tail;     /*указатель на хвост очереди*/

где абстрактный тип QType является параметрром из шаблона класса.
Для доступа к защищенным компонентам-данным в классе RingQueue рекомендуется предусмотреть общедоступные компонентные методы, реализующие примитивы обработки очереди. Декларация их прототипов в общедоступной части декларации класса RingQueue должна иметь следующий формат:

 template <class QType> void
  RingQueue <QType> :: enqueue (QType) {.....}

Для реализации компонент-данных при определении объектов класса RingQueue или роизводных классов, в Классе RingQueue необходимо предусмотреть конструктор с целочисленным аргументом, определяющим размер буфера очереди.
Таким образом, декларация конструктора в классе RingQueue должна иметь следующий формат:

 RingQueue (int);   /*конструктор класса*/

Конструктор класса RingQueue должен обнулять указатели очереди, фиксировать размер очереди и динамически выделять памать из кучи для буфера очереди, используя операцию new системы программирования С++. Все перечисленные инициализации, кроме опрации new, удобно перечислить в списке инициализаций, чтобы упростить исходный код в блоке конструктора.
Для корректного удаления объектов класса RingQueue в нем рекомендуется предусмотреть деструктор ~RingQueue(). Его задача - освобождение памяти, распределенной конструктором для буфера очереди, с помощью операции delete системы программирования С++.
Учитывая простоту исходного кода конструктора и деструктора класса RingQueue, их определение может быть дано неопсредственно в теле класса.
Например, дефиниция конструктора может иметь следующий формат в разделе

public класса RingQueue:
 RingQueue (int S) : Qsize(s), head(0), tail(0)   {...};

В этом случае конструктор и деструкторь по умолчанию будут рассматриваться компилятором С++ как подставляемые (inline) функции. В объектном коде компилятор С++ заменит каждую ссылку на inline-функцию непосредственно ее кодом, увеличивая быстродействие программы.

В целях построения объектно-ориентированной программной реализации алгоритма кругового обслуживания для задачи Иосифа с помощью кольцевой очереди элементов, целесообразно сформировать класс JoeRing, производный от базового класса RingQueue. Производный класс JoeRing должен наследовать компоненты базового класса RingQueue, содержать собственные частные (private) компоненты-данные и общедоступные (public) компонентные методы, учитывающие специфику обраьотки круговой очереди в задаче Иосифа, а также определить конкретный тип данных для параметра базового класса, указанный в шаблоне его декларации для абстрактной типизации элементов очереди. В соответствии с правилами реализации принципа наследования в системе программирования С++, декларацию производного класса JoeRing можно специфицировать следующим образом:

 class JoeRing : public RingQueue <unsigned>
 {
 private:/*спецификация компонент-данных класса JoeRing*/
 public :/*спецификация прототипов собственных компонентных методов*/
 };

В заголовке приведенной декларации класса JoeRing указано имя базового класса (RingQueue), категория наследования public и конкретизация шаблона базового класса <unsigned>.
Целочисленная (unsigned) конкретизация параметра шаблона базового класса RingQueue соответствует характеру обработки данных рассматриваемой реализации задачи Иосифа, где элементы обслуживания идентифицируются целочисленными номерами, поэтому естественно определить тип элементов наследованной очереди как unsigned (беззнаковые целые). Соответствующее расширение наследованных компонент шаблонного базового класса до их полного определения автоматически осуществляется компилятором С++.
Категория наследования public, указанная в заголовке декларации класса JoeRing разрешает обращаться к наследованным защищенным компонентам базового класса в компонентных методах производного класса. К наследованным общедоступным компонентам можно обращаться также во внешних функциях программы, вызывая их через объекты производного класса. Защищенные наследованные компоненты во внешних функциях программы недоступны. При использовании более строгой категории наследования private,дсотуп к наследованным защищенным и общедоступным компонентам базового класса сохраняется только в методах производного класса. Таким образом, public-производные классы сохраняют привилегии доступа базового класса, private-производные классы изменяют привелегии доступа на private. Для любой категории наследования непостредственный доступ к частным компонентам базового класса в производном классе запрещен и реализуетя через общедоступные наследованные методы базового класса. Учитывая приведенные соображения в базовом классе рекомендуется применять защищенные компонентны вместо приватных, чтобы обеспечитть доступ к ним в методах производного класса, когда это необходимо.
В спецификацию собственных частных компонент роизводного класса JoeRing рекомендутся включить объявление 3-х целочисленных (int) полей count, thresold и leader. Компонентны count и thresold следует использовать для хранения текущего и предельного значений, соответственно, счетчика шагов по кругу обслуживания, leader должна указывать номер ведущего элемента, с которого начинается круговой отсчет в задаче Иосифа.
В общедоступную часть объявления класса JoeRing целесообразно включить декларацию прототипов следующих собственных компонентных методов:

 void load(), int busy(), unsigned find() и void round(),

а также для спецификации конструктора и деструктора класса.
Компонентный метод void JoeRing ::load() следует применять для загрузки кольцевого буфера наследованной очереди последовательными номерами элементов обслуживания в диапазоне от 1 до (qsize-1). Для записи номеров элементов в очередь следует использовать наследованный от базового класса RingQueue компонентный метод enqueue(unsigned). Кроме того, компонентный метод load должен обеспечивать циклический сдвиг всех элементов обслуживания в очереди на число позиций заданное компонентой leader. Сдвиг располагается с целью расположить в голове очереди элемент, с которого должен начинаться обход круга. Для реализации каждой итерации циклического сдвига рекомендуется применять последовательно наследованные от базового класса RingQueue компонентные методы dequeue и enqueue.
Компонентный метод JoeRing ::find() должен обеспечивать поиск очередного удаляемого элемента и возвращать его номер. Для организации поиска рекомендуется инициализировать счетчик шагов (count=1) и поочередно вызывать наследованные методы базового класса RingQueue dequeue и enqueue, пока показания счетчика шагов меньше порогового значения (count<tresold). В результате выполнения этого цикла элемент кандидат для удаления из круга окажется в голове очереди и может быть исключен наследованным от базового класса RingQueue методом dequeue.
Компонентный метод JoeRing ::busy() рекомендуется предусмотреть для оценки текушего заполнения очереди, т. е. число элементов, находящихся в круге обслуживания. Число элементов очереди определяется соотношением значений ее указателей head и tail, наследованных от базового класса RingQueue. Доступ к ним в наследованном классе разрешен, т. к. они декларированы в базовом классе с модификатором доступа protected. Полученная оценка заполнения передается через код возврата этого компонентного метода.
Компонентный метод JoeRing ::find() должен объединять в своем блоке вызовы остальных компонентных методов класса JoeRing, чтобы реализовать алгоритмкругового обслуживания в задаче Иосифа. Для выполнения подготовительных шагов этого алгоритма следует вызвать компонентный метод load. Чтобы обеспечить круговой обход элементов обслуживания с целью поиска кандидатов для удаления, нужно организовать циклический вызовметода find, который возвращает номер исключаемого элемента. Для его отображения в потоке стандартного вывода (stdout) можно использовать библиотечную функцию printf системы программирования С++. Этот цикл должен продолжаться, пока очередь обслуживания не пуста. Для оценки заполнения очереди элементов следует применять компонентный метод busy.
Обращение к компонентному методу round может быть реализовано в основной функции main программы joseph через предварительно определенный объект класса JoeRing, например, следующим образом:

   joe.round();

где joe - объект класса JoeRing, обладающий желаемыми значениями параметров задачи Иосифа (число элементов обслуживания, номер ведущего элемента, пороговое значение счетчика шагов).
Для создания объектов класса JoeRing с требуемыми значениями параметров задачи Иосифа в нем необходимо предусмотреть конструктор с тремя цеочисленными аргументами. Конструктор класса JoeRing должен инициализировать собственные приватные компоненты leader и thresold желаемыми значениями и вызывать конструктор базового класса RingQueue <unsigned> для инициализации очереди с наследованным кольцевым буфером достаточного размера, чтобы разместить требуемое число номеров элементов обслуживания. Всвязи с кольцевой организацией буфера очереди, его размер должен на 1 превышать число размещаемыз в нем элементов. Конструктор базового класса RingQueue имеет один целочисленный аргумент, устанавливающий размер очереди данных. Поэтому конструктолр производного класса JoeRing также должен иметь соответствующий целочисленный аргумент для передачи конструктору базового класса. Кроме того, конструктор класса JoeRing должен иметь еще два целочисленных аргумента, которые принимают требуемые значения номера ведущего элемента и порогового значения счетчика шагов для инициализации собственных приватных компонент leader и thresold, соответственно.
Все перечисленные инициализирующие действия можно реализовать через список инициализаций, перечислив их после имени в сторке дефиниции конструктора класса JoeRing. Поскольку все инициализирующие действия выполняет список инициализаций, тело конструктора класса JoeRing может быть пустым {}.
Учитывая особенности программной реализации конструктора класса JoeRing, его определение целесообразно включить в раздел publlic декларации класса, например, следующим образом:

  class JoeRing : public RingQueue <unsigned>
  {
  ................................
  public:
 JoeRing (int n, int l, int m) : RingQueue <unsigned> (n+1),
     leader (l), thresold (m) {};
  ................................
  };

Рассмотренный конструктор следует использовать для создания объекта класса JoeRing в основной функции main программы Joseph. Необходимые 3 аргумента могут быть получены путем преобразования соответствующих параметров командной строки вызова программы Joseph в целочисленный формат с помощью библиотечной функции atoi системы программирования С++.
Чтобы всегда иметь возможность корректно завершить обработку объектов класса JoeRing в нем рекомендуется предусмотреть деструктор ~JoeRing(). В данном случае деструктор производного класса слдует специфицировать, чтобы обеспечить неявный вызов деструктора базового класса RingQueue для корректной выходной обработки наследованных компонент базового класса, в частности, для освобождения памяти, динамически выделенной под буфер очереди. Какая-либо выходная обработка собственных компонент-данных класса JoeRing не является необходимой, поэтому тело деструктора ~JoeRing() целесообразно оставить пустым {}, а его определение включить в декларацию класса.
Определение конструктора и деструктора внутри декларации класса JoeRing принуждает компилятор С++ рассматривать их по умолчанию как подставляемые (inline) функции, обеспечивая автоматическую подстановкуобъектного кода по адресамих вызовов в выполняемом модуле программы Joseph. Компонентные методы класса JoeRing могут иметь достаточно представительный исходный и, следовательно, объектный код. Поэтому их целесообразно специфицироватьвне декларации класса, не превращая в inline-подстановки. Например, определение компонентного метода round вне декларации класса может иметь следующий формат:

 void JoeRing :: round() {/*Исходный код метода*/}

Исключением может быть компонентный метод busy, который достаточно прост, чтобы определить его внутри декларации класса JoeRing.

1.  Рассмотреть вариант задачи Иосифа, где пороговое значение счетчика шаговпо кругу обслуживания не является постоянным, а изменяется случайным образом после удаления каждого элемента или является известной функцией его номера.
2.  Изменить программу Joseph таким образом, чтобы вместо целочисленных номеров для обозначения элементов в круге обслуживанрия задачи Иосифа использовались буквы латинского алфавита. В этом случае исходный набор элементов может быть задан соответствующей строкой символов.
3.  Модифицировать программу Joseph таким образом, чтобы для хранения элементолв обслуживания применялась очередь с линейным фиксированным буфером минимально возможного размера.
4.  Разпработать класс очередь с файлофым буфером (FileQueue), где для хранения элементов очереди используется регулярный файл, обслуживаемый операциями чтения-записи по 2-м файловым указателям (типа File*) или дескриптонрам к контексте процесса, один из которых можно получить, если открыть файл по чтению, другой - в режиме добавления в конец файла. При разработке методов класса FileQueue рекоментдуется использовать библиотечные функции ввода-вывода системы программирования С или соответствующие вызовы OSUNIX.
5.  Разработать класс сдвиговой очереди (ShiftQueue), организация которой быдет напоминать работу сдвигового регистра: после исключения головного элемента все остальные сдвигаются на 1 шаг в направлении головы очереди.
6.  Рассмотреть возможность применения программных каналов OSUNIX для моделирования кругового обслуживания элементов в условиях задачи Иосифа.

1.  Д. Кнут
    Искусство программирования для ЭВМ - т. 1, Основные алгоритмы,
    М., Мир, 1976.
2.  Б. Мейер, К. Бодуэн
    Методы программирования, т. 1, М., Мир,1989.
4.  П. Лукас
    С++ под рукой, Киев, НИПФ "Диа-Софт", 1993.
5.  Т. Чан
    Системное программирование на С++ для UNIX-BHV, Киев, 1997.