Олег Деревенец - Песни о Паскале

Пусть наша новая программа повторит действия танцевального тренера, – инженеры называют это моделированием. Работать будем, конечно, не с живыми детьми, мы представим их как-то иначе. Условимся обозначать их латинскими буквами: девочек – строчными, а мальчиков – заглавными (только потому, что они выше ростом).

Теперь станьте на место учителя: к вам приходят то мальчик, то девочка, но вы не знаете, кто будет следующим, – это поток, и в нём доступен только первый его элемент. Организовать входной поток можно посимвольным вводом «мальчиков» и «девочек». Но мы сделаем ещё проще: представим поток детишек строкой, и будем считать, что к преподавателю они являются слева направо по одному. Например, строка

ZHJKqwertASDyuiopQWERTYUIOPasdf

означает, что первым явится мальчик по имени Z, а последней – девочка по имени f. Первая пара составится из мальчика Z и девочки q. Это упрощение не меняет сути нашей модели, но избавляет её от второстепенных деталей.

Итак, с учетом всех договоренностей, явим задачу в окончательном виде. Дана строка, состоящая из больших и маленьких букв латинского алфавита – «мальчиков» и «девочек». Мы должны сформировать другую строку, состоящую из тех же символов, но следующих попарно: сначала большая буква – «мальчик», затем маленькая – «девочка». Пары разделяются пробелом. Например, для указанной выше строки, пары должны быть составлены так:

Zq Hw Je Kr At Sy Du Qi Wo Ep Ra Ts Yd Uf

А напоследок программа должна напечатать имена тех, кто временно остался без пары. Здесь это будут пришедшие в числе последних мальчики I, O и P.

Если логика программы вам ясна, разрешим теперь главный вопрос: как организовать очередь символов? Ведь очередь – это не просто массив данных, а механизм, содержащий и хранилище данных и процедуры для работы с ними.

Сделаем так. Элементы очереди – символы – будем хранить в строковых переменных. К ним добавим ещё две процедуры: одну – для установки элемента в очередь, другую (это будет функция) – для извлечения из очереди первого элемента. Назовем их соответственно PutInQue – «поставить в очередь» и GetFromQue – «извлечь из очереди» (Queue – «очередь» или «хвост»). Всё это представлено в программе «P_45_1».

{ P_45_1 – Запись в танцевальный кружок }

{ Постановка символа arg в очередь Que }

procedure PutInQue(var Que: string; arg: char);

begin

Que:= Que + arg; { добавляем в конец строки }

end;

{ Выбор из очереди Que элемента в параметр arg }

function GetFromQue(var Que: string; var arg: char): boolean;

begin

if Length(Que) = 0 { если очередь пуста }

then GetFromQue:= false

else begin

GetFromQue:= true; { если не пуста }

arg:= Que[1]; { запоминаем первый элемент }

Delete (Que, 1, 1); { и удаляем его из очереди }

end

end;

{ Глобальные переменные }

var S_IN : string; { входной поток – символы }

S_OUT : string; { выходной поток (пары) }

Boys : string; { очередь мальчиков }

Girls : string; { очередь девочек }

c1,c2 : char; { очередная пара – символы строки }

i : integer; { индекс во входном потоке }

begin {--- Главная программа ---}

{ задаем (вводим) входной поток: A..Z – мальчики, a..z – девочки }

S_IN:='ZHJKqwertASDyuiopQWERTYUIOPasdf';

S_OUT:=''; { выходной поток пока пуст }

Boys:=''; Girls:=''; { Очищаем очереди мальчиков и девочек }

{ Цикл обработки входного потока }

for i:=1 to Length(S_IN) do begin

c1:= S_IN[i]; { выбираем из входного потока }

if c1 in ['A'..'Z']

then begin { если это мальчик…}

{ если в очереди есть девочка }

if GetFromQue(Girls, c2)

{ добавляем пару в выходной поток }

then S_OUT:= S_OUT+c1+c2+’ ’

{ а иначе помещаем мальчика в очередь }

else PutInQue(Boys, c1);

end

else begin { а если это девочка…}

{ если в очереди есть мальчик }

if GetFromQue(Boys, c2)

{ добавляем пару в выходной поток }

then S_OUT:= S_OUT+c2+c1+’ ’

{ а иначе помещаем девочку в очередь }

else PutInQue(Girls, c1);

end

end;

Writeln('Входной поток:' );

Writeln(S_IN);

Writeln('Выходной поток:' );

Writeln(S_OUT);

if Length(Boys)>0 then begin

Writeln('В очереди мальчиков остались:' );

Writeln(Boys);

end;

if Length(Girls)>0 then begin

Writeln('В очереди девочек остались:' );

Writeln(Girls);

end;

Readln;

end.

Процедура PutInQue просто добавляет символ в конец строки. Строго говоря, если длина строки достигнет 255, то новый символ не попадет в очередь. Но мы не станем усложнять программу дополнительными проверками, – считаем, что емкости очереди нам достаточно.

Но для функции GetFromQue, выбирающей из очереди первый символ, контроль строки на пустоту необходим, иначе работа модели нарушится. Функция возвращает состояние очереди, бывшее до извлечения символа (TRUE, если очередь не была пуста). А сам извлекаемый символ возвращается через параметр arg, – это ссылка на символьную переменную. Вот, пожалуй, и вся премудрость. Испытайте эту программу. Добавьте операторы печати для наблюдения за очередями.

Прежде, чем углубиться в стек, вникнем в работу железной дороги. Вы знаете, как железнодорожники доставляют товарный вагон из пункта «А» в пункт «Б»? «Очень просто, – скажете, – цепляют к составу и тащат!» Тогда взгляните на рис. 100.

Здесь показаны пять железнодорожных станций, четыре из которых обозначены цифрами, а пятая – узловая станция – буквой «У». Предположим, что со станции «1» надо доставить несколько десятков вагонов на другие станции (по направлению стрелок). С этих станций тоже везут вагоны, но соответствующие стрелки я не показал. Тащить вагоны поодиночке разорительно! Поэтому их собирают в составы по нескольку десятков вагонов. Накопив такой состав на станции «1», железнодорожники доставляют его на узловую станцию; сюда же стекаются составы с других направлений. На узловой творится самое интересное, – здесь из одних составов формируют другие с тем, чтобы тащить их далее в нужном направлении. Эта работа называется сортировкой состава. В нашей стране сотни товарных станций, многие из которых узловые. Прежде чем попасть по назначению, вагон кочует между узловыми станциями, проходя через несколько сортировок. А вы говорите: просто, просто!