Программирование очередей кольцевой обработки данных.

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

Формулировка задания: Требуется разработать программу JOSEPH для моделирования порядка обслуживания конечного набора элементов в условиях задачи Иосифа. Задача Иосифа (Флавия) или считалка Джозефуса — известная математическая задача с историческим подтекстом. Основана на легенде, что отряд Иосифа Флавия, защищавший город , не пожелал сдаваться в плен блокировавшим пещеру превосходящими силам римлян. Воины, в составе сорока человек, стали по кругу и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. При этом двое воинов, оставшихся последними в живых, должны были убить друг друга. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно встать ему и его товарищу, чтобы остаться последними, но не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам. В уменьшенном до 10 варианте и выбывании каждого второго задача выглядит так:

Если производить отсчет от 1-го солдата в круге, то порядок удаления будет следующим: 2, 4, 6, 8, 10, 3, 7, 1, 9. Солдат под номером 5 – в конечном итоге остается в живых.

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

Организация очередей данных

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

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

Рассмотренный линейный вариант очереди с фиксированным линейным буфером имеет ограниченное применение, т. к. для корректной работы значение указателя головы очереди не должно превышать значения указателя на хвост очереди head<=tail. Это условие не позволяет добавлять новые элементы, когда хвост очереди исчерпан (tail=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 - извлечение (чтение) данных из очереди, соответственно. В очереди с кольцевым буфером они имеют реализацию рассмотренную ниже. 

Примитив ENQUEUE загружает новый элемент в хвост очереди и увеличивает на 1 значение указателя tail. Если значение tail при этом выходит за границу буфера очереди, то tail следует обнулить. Достигается это использованием операции взятия остатка от деления (%). Если в данный момент tail = 7 и мы вызываем функцию enqueue(3), в восьмой элемент массива (q[8]) заносится значение 3. Затем происходит увеличение tail на единицу, теперь оно равно 8. Получившееся значения делится на 8 и берётся остаток. 8 % 8 = 0, cоответственно теперь tail = 0.

Псевдокод примитива ENQUEUE выражают следующие операторы:

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

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

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

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

    tail = head; // – пустая очередь

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

   head = tail+1  mod  qsize; // переполненная очередь

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

class queue // http://docs.h1.ru/cidocs/vdv_14191/gl36.html

{

private:

int head, tail; // переменные хранящие начальный и конечный индексы

int q[10]; // очередь содержащая десять элементов

public:

queue() : head(0), tail(0) {}; // конструктор

void enqueue(int number) // добавление в очередь

{

q[tail] = number;

tail = (tail+1) % 10;

}

int dequeue () // удаление из очереди

{

int temp = q[head];

head = (head+1) % 10;

return temp;

}

}