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

Stack:= Stack^.mNext; { переключаем голову на следующий элемент }
Dispose(p);       { удаляем ненужный элемент }
end
end;
var F : text; S : string;
begin       {--- Главная программа ---}
Stack:= nil; { Инициализация стека пустым значением }
{ Открываем входной файл }
Assign(F, 'P_56_1.pas'); Reset(F);
{ Пока не конец файла, читаем строки и помещаем в стек }
while not Eof(F) do begin
      Readln(F, S); Push(S);
end;
Close(F);
{ Открываем выходной файл }
Assign(F, 'P_56_1.out'); Rewrite(F);
{ Пока стек не пуст, извлекаем и печатаем строки }
while Pop(S) do Writeln(F, S);
Close(F);
end.

Процедура Push повторяет процедуру вставки элемента в список. А в теле функции Pop гляньте на выделенные операторы. После извлечения строки ненужный теперь элемент стека уничтожается процедурой Dispose(p), – так освобождается память. Но перед этим указатель на следующий элемент надо сохранить в голове списка, иначе мы потеряем ссылку на цепочку оставшихся элементов.

Изваяв программу, Ник испытал её волшебное действие на её собственном тексте. Каково же было его удивление, когда результат совпал с абракадаброй, полученной от приятеля! Вот такое чудесное совпадение!

Танцуют все!

Ох уж эти танцы… Задачу о танцевальном кружке мы решили в 45-й главе. Освежите её в памяти, поскольку новый вариант решения будет похож на первый.

Только теперь мы изменим имена мальчиков и девочек. В том варианте, как вы помните, дети носили однобуквенные имена, и мы представили их символами. Теперь же мы дадим им настоящие человеческие имена, но для этого и очередь организуем иначе. Как? Вы уже догадались – посредством односвязного списка (рис. 128).

Рис.128 – Размещение в очереди трех строк

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

Это обстоятельство вынудит нас изменить процедуру удаления первого элемента очереди. Теперь перед удалением надо заполучить указатель на предпоследний элемент списка. В нём надлежит поставить заглушку NIL, чтобы отцепить первый элемент очереди (рис. 129). В этом состоит главная премудрость обращения с очередью строк.

Рис.129 – Отцепление первого элемента очереди

Так же как и для стека, для очереди надо запрограммировать, по меньшей мере, две операции: установку и извлечение из нее.

Процедуру установки в очередь PutInQue объявим так: