Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Листинг 17.8. Программа use q.c

754 Глава 17

Ниже показаны результаты пробного запуска. Вы должны также протестировать корректность работы реализации в случае, когда очередь полна.

Тестирование интерфейса Queue. Введите а, чтобы добавить значение,

введите d, чтобы удалить значение, или введите q для выхода из программы.

а

Целое число для добавления: 40 Помещение 40 в очередь

1 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: а

Целое число для добавления: 20 Помещение 20 в очередь

2 элемент(ов) в очереди

Расширенное представление данных 755

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: а

Целое число для добавления: 55 Помещение 55 в очередь 3 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: d

Удаление 40 из очереди 2 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: d

Удаление 20 из очереди 1 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: d

Удаление 55 из очереди 0 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: d

Элементы для удаления отсутствуют!

0 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы:

q

Программа завершена.

Моделирование реальной очереди

Итак, тип очереди работает! Давайте теперь с его помощью решим какую-то более интересную задачу. Очереди встречаются во многих реальных ситуациях. Это могут быть, к примеру, очереди клиентов в банках и универсамах, очереди самолетов в аэропортах и очереди задач в многозадачных компьютерных системах. Пакет очереди можно применять для моделирования ситуаций подобного рода.

Предположим, что некий Зигмунд Ландер установил консультационный киоск в торговом центре. Клиенты могут заплатить за одну, две или три мицугы консультаций. Для обеспечения свободного прохода действующие в торговом центре правила ограничивают количество клиентов в очереди до 10 (что легко определяет максимальный размер очереди в программе). Представим, что люди подходят к киоску случайным образом, а время, которое они тратят на получение консультации, произвольно распределяется между тремя возможными вариантами (одна, две или три минуты). Сколько в среднем клиентов придется обслужить Зигмунду в течение часа? Сколько в среднем каждому клиенту придется дожидаться своей очереди? Какой будет средняя длина очереди? Моделирование может дать ответы на вопросы такого рода.

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

typedef struct item

{

long arrive; /* время присоединения клиента к очереди */

int processtime; /* желаемое количество минут консультации */

} Item;

Для преобразования пакета очереди, чтобы он обрабатывал эту структуру, а не тип int, использованный в последнем примере, достаточно заменить предыдущее опрсде-

756 Глава 17 лсиие typedef типа Item приведенным выше. После этого вам не придется беспокоиться о деталях функционирования очереди. Вместо этого вы сможете сосредоточить все внимание на реальной задаче — моделировании очереди к киоску Зигмунда.

Рассмотрим один из возможных подходов. Пусть отсчет времени осуществляется одноминутными интервалами. Тогда каждую минуту необходимо проверять, не появился ли новый клиент. Если клиент подошел, и очередь не переполнена, клиента необходимо добавить в очередь. Это предусматривает запись в структуру Item времени прибытия клиента и длительности консультации, которую клиент желает оплатить, с последующим добавлением элемента в очередь. Однако если очередь полна, клиента нужно отправить. В целях учета мы будем отслеживать общее число клиентов и общее количество “отказов” (людей, которые не могут стать в очередь, поскольку она переполнена).

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

Основной код может выглядеть похожим на показанный далее, при этом каждый цикл соответствует одной минуте активности:

Обратите внимание, что разрешение времени является относительно грубым (одна мииуга), так что максимальное количество клиентов в час составляет всего 60.

Расширенное представление данных 757

Ниже представлены краткие описания некоторых переменных и функций.

• min per cust — среднее количество минут между прибытиями клиентов.

• newcustomer() использует функцию rand() языка С для определения, появляется ли клиент в течение этой конкретной минуты.

• turnaways — количество прибывших клиентов, которым было отказано в обслуживании.

• customers — количество прибывающих клиентов, которые становятся в очередь.

• temp — переменная типа Item, описывающая нового клиента.

• customertime() устанавливает члены arrive и processtime структуры temp.

• wait time — количество минут, остающееся до того момента, когда Зигмунд завершит консультирование текущего клиента.

• line wait — накапливаемое значение времени, потраченное в очереди всеми клиентами на текущий момент.

• served — количество действительно обслуженных клиентов.

• sum line — накапливаемое значение длины очереди на текущий момент.

Только подумайте, насколько более запутанным и непонятным выглядел бы код, если бы он оказался усыпанным вызовами функций malloc() и free() и указателями на узлы. Наличие пакета очереди позволяет сосредоточиться на задаче моделирования, не отвлекаясь на детали программирования.