Песни о Паскале

Вовочка обрабатывал события по принципу стека, – скажет об этом системный программист. Другое название стека – дисциплина обслуживания LIFO, что значит «Last-In, First-Out», или по-русски: «последним пришел – первым ушел». Мы соприкоснулись со стеком, разбирая рекурсивную процедуру быстрой сортировки. Помните пример с укладкой рюкзака? А вот ещё пример: магазин для патронов. Патрон, вставленный в магазин последним, выстрелит первым, и наоборот.

Итак, пример с Вовочкой показал, что важные события мы обслуживаем по принципу стека.

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

Или другой пример – печатание документов на сетевом принтере. Когда принтер занят, операционная система ставит запросы на печать в очередь. А затем – по мере готовности принтера – выбирает файлы из этой очереди и отправляет принтеру.

За очередью тоже закрепилось свое сокращение – FIFO, что значит «First-In, First-Out» – «первым пришел, первым ушел». В отличие от стека, в очередь попадают маловажные события.

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

Танцевальный кружок

В городе набирали детей в кружок бального танца. Запись в кружок вела преподающая в нём дама. Приходящих мальчишек и девчонок она стремилась объединять в пары при первой возможности с тем, чтобы они сразу приступали к занятиям. Однако на запись дети приходили поодиночке в разное время и в случайном порядке, – то несколько мальчиков подряд, то несколько девочек. Дама не слыхала о системном программировании, а потому прибегла к здравому смыслу. Взяв пару записных книжек, она поступала так.

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

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

Рис. 99 – Запись в танцевальный кружок

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

      ZHJKqwertASDyuiopQWERTYUIOPasdf

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

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

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

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

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

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