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

Теперь вам не составит труда разобраться в показанной ниже программе «P_45_2». Обратите внимание на отцепку вагонов от исходного состава: она тоже выполняется функцией выталкивания Pop, поскольку исходный состав трактуется как непустой стек.

{ P_45_2 – Сортировочная станция }

{ Помещение элемента в стек }

procedure Push(var aStack: string; arg: char);

begin

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

end;

{ Извлечение элемента из стека }

function Pop(var aStack: string; var arg: char): boolean;

begin

if Length(aStack) = 0 { если стек пуст }

then Pop:= false { сообщаем об этом }

else begin

{ возвращаем последний элемент }

arg:= aStack[Length(aStack)];

{ и удаляем его из стека }

Delete(aStack, Length(aStack), 1);

Pop:= true; { признак того, что стек не был пуст }

end;

end;

var S : string; { исходный состав }

SA, SB, SC : string; { три сортировочных тупика A,B,C}

c : char; { очередной вагон }

begin

S:= 'HEjd31kDJK62px912se3BKdwL9'; { Исходный состав }

Writeln('Исходный состав: '+S);

SA:=’’; SB:=’’; SC:=’’; { очистка тупиков }

{ Отцепляем вагоны от исходного состава и заталкиваем в тупики }

while Pop(S, c) do begin

if c in ['A'..'Z'] then Push(SA, c);

if c in ['a'..'z'] then Push(SB, c);

if c in ['0'..'9'] then Push(SC, c);

end;

{ Теперь исходный состав пуст, то есть S='' }

{ Выкатываем вагоны из тупика A и цепляем к первому составу }

while Pop(SA, c) do Push(S, c);

Writeln('На станцию A : '+S);

S:=''; { Освобождаем пути }

{ Выкатываем вагоны из тупика B и цепляем ко второму составу }

while Pop(SB, c) do Push(S, c);

Writeln('На станцию B : '+S);

S:=''; { Освобождаем пути }

{ Выкатываем вагоны из тупика C и цепляем к третьему составу }

while Pop(SC, c) do Push(S, c);

Writeln('На станцию C : '+S);

Readln;

end.

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

• Очереди и стеки – это механизмы, применяемые в системных программах. Элементами очередей и стеков могут быть любые объекты.

• Очередь обслуживает элементы по принципу «первый пришел – первый ушел» или сокращенно FIFO (First-In, First-Out).

• Стек обслуживает элементы по принципу «последний пришел – первый ушел» или сокращенно LIFO (Last-In, First-Out).

А) Исследуя модель танцевального кружка, можно заметить, что в любой момент одна из двух очередей обязательно пуста. В самом деле, если приходит больше мальчиков, то будет пуста девчоночья очередь и наоборот. Можно ли обойтись одной очередью? Придумайте, как это сделать.

Подсказка: добавьте функцию для тестирования очереди с тем, чтобы выяснить, не пуста ли она. И, если не пуста, то кто томится в ней – мальчик или девочка? Эта функция не должна изменять состояние очереди.

Б) На реальных станциях на горку последовательно загоняют несколько составов, а уж потом освобождают тупики. Добавьте в модель сортировочной горки возможность такой обработки. Исходные составы (строки) должны вводиться с клавиатуры, признак окончания ввода – пустая строка. Совет: выделите действия по сортировке одного состава в отдельную процедуру.

В) Постройте механизмы очереди и стека на базе массива символов, а не на базе строки. Какие дополнительные переменные здесь понадобятся?

Давно минули времена, когда для счета всем хватало своих пальцев – первого «калькулятора» человечества, а наши потребности в счете все растут и растут…

Некий король – любитель науки, порядка и немножко чудак – распорядился пересчитать все, что ни есть, в своих владениях. Ладно бы, его интересовали крупные предметы вроде домов, машин и всего такого… Но нет, король велел пересчитать и капли в морях, и песчинки на берегах, и травинки в степях! Пока ученые придумывали способы подсчета, программисты возились с другой задачей – обработкой всего этого на компьютере. Они искали подходящий тип данных для хранения тех огромных чисел, что нужны ученым! Обратившись к описанию языка Паскаль, программисты заинтересовались двумя числовыми типами, которые на первый взгляд подходили для такого случая.