Очередь

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

Класс queue, как и stack, принадлежит к категории контейнерных адаптеров, то есть строится на базе других последовательных контейнеров. Как нетрудно предположить, идеальная реализация очереди создается на базе дека, поэтому по умолчанию queue использует аргумент шаблона deque. Необходимость в выборе другой реализации встречается редко.

Очереди часто требуются при моделировании систем, в которых отдельные элементы ожидают обслуживания со стороны других элементов. Классическим примером такого рода является задача кассира . Клиенты приходят в банк, становятся в очередь и обслуживаются несколькими кассирами. Поскольку клиенты появляются со случайными интервалами, а продолжительность их обслуживания неизвестна заранее, предсказать длину очереди в конкретный момент времени невозможно. Тем не менее, можно смоделировать ситуацию и посмотреть, что получится.

В реалистичной модели каждый юхиент и кассир должны быть представлены отдельными программными потоками. К сожалению, в стандарте С++ поддержка многопоточных приложений не предусмотрена. С другой стороны, небольшие изменения в программе позволяют имитировать многопоточность на приемлемом уровне.

В многопоточной программе одновременно работают несколько программных потоков, совместно использующих общее адресное пространство. На практике ко-

Мы вернемся к теме многопоточности в главе 11.

using namespace std;

int maInO { ifstream in( Stack3.cpp ): vector<string> textlines: string line;

while(getline(in, line))

textl1nes.push back(line + \n ); whi led textl i nes. emptyO) {

cout textlines.back():

textlines.pop back();

1 III:-

Программа выводит те же результаты, что и Stackl.срр, но теперь в ней могут выполняться векторные операции. Список также поддерживает включение элементов с начала контейнера, но обычно этот вариант уступает по эффективности функции push back() вектора (кроме того, включение элементов в начало контейнера более эффективно выполняется в деках, чем в списках).

class Teller { queue<Customer>& customers: Customer current: enum { SLICE = 5 }:

int ttime: Остаток времени в кванте bool busy: Кассир обслуживает клиента? public:

Teller(queue<Customer>& cq)

: customers(cq). ttime(O). busy(false) {] Tellers operator=(const Tellers rv) {

customers = rv.customers:

current = rv.current:

ttime = rv.ttime:

busy = rv.busy:

личество процессоров обычно меньше количества программных потоков (а в большинстве систем установлен только один процессор). Чтобы создать иллюзию того, что каждый программный поток работает на отдельном процессоре,механизм квантования периодически прерывает текущий программный поток и передает управление другому. Модель с автоматическим прерыванием и запуском программных потоков называется моделью с вытесняющей многопоточностью; она избавляет программиста от необходимости самостоятельно обеспечивать передачу управления между программными потоками.

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

: С07:ВапкТе11ег.срр {RunByHand}

Моделирование банковского обслуживания

на базе очереди и имитации многопоточности

linclude <cstdlib>

linclude <ctime>

linclude <iostream>

linclude <iterator>

linclude <list>

linclude <queue>

using namespace std:

class Customer {

int serviceTime: public:

CustomerO : serviceTime(O) {}

Customer(int tm) : serviceTime(tm) {}

int getTimeO { return serviceTime: }

void setTime(int newtime) { serviceTime = newtime: }

friend ostream&

operator (ostream& os, const Customers c) { return OS [ c.serviceTime ]:

return *this;

bool isBusyO { return busy; } void run(bool recursion = false) { if(!recursion)

ttime = SLICE: int servtime = current.getTime(); if(servtime > ttime) { servtime -= ttime: current.setTime(servtime):

busy = true: Продолжать обслуживание текущего клиента return:

ifCservtime < ttime) { ttime -= servtime: if(Icustomers.emptyO) {

current = customers.front():

customers.pop(): Удаление из очереди

busy = true:

run(true); Рекурсия

return;

if(servtime == ttime) ( Клиент обслужен: current = Customer(O): busy = false;

return: Завершение текущего кванта

Наследование для обращения к защищенной реализации: class CustomerQ : public queue<Customer> { public: friend ostream&

operator (ostream& os. const CustomerQS cd) { copy(cd.c.beginO. cd.c.endO,

ostream iterator<Customer>(os. )); return os;

int mainO { CustomerQ customers; list<Teller> tellers; typedef list<Teller>::iterator Tel lit: tel 1 ers.push back(Tel1er(customers)): srand(time(0)): Раскрутка генератора случайных чисел clock t ticks = clockO: Запуск имитации минимум на 5 секунд: while(clock() < ticks + 5 * CLOCKS PER SEC) {

Заполнение очереди случайным количеством клиентов

со случайным временем обслуживания:

for(int i = 0: i < randO % 5: i++) customers, push (Customer (rand О 15 + 1)):

cout { tell ers. SizeO } customers endl:

Обслуживание клиентов: