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

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

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

Рис.127 – Порядок следования в стеке первых трех строк

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

Работу начнем, как обычно, с конструирования элемента списка. Этим элементом будет запись, включающая строку и указатель на следующую запись.

type PRec = ^TRec;       { Тип указатель на запись }

      TRec = record       { Тип запись для хранения связанных строк }

      mStr : string; { хранимая строка }

      mNext : PRec; { указатель на следующую запись }

      end;

Напомню, что со стеком выполняются, по меньшей мере, две операции: помещение в стек PUSH, и извлечение из стека POP. В нашем случае процедура записи в стек будет объявлена так:

procedure Push(const arg : string);

Аргументом процедуры является ссылка на строку, прочитанную из файла.

Теперь об извлечении из стека. Здесь надо получить не только строку, но и сигнал о состоянии стека: пуст он, или в нём ещё валяется что-то. Поэтому операцию извлечения из стека оформим булевой функцией.

function Pop(var arg : string): boolean;

Строка будет возвращаться через параметр arg, – это ссылка на переменную. Но, если функция вернет FALSE, это будет сигналом того, что стек пуст и строка не возвращена.

На этом закончим рассуждения и обратимся к программе «P_56_1».

{ P_56_1 – перестановка строк файла }

type PRec = ^TRec;       { Тип указатель на запись }

      TRec = record       { Тип запись для хранения связанных строк }

      mStr : string; { хранимая строка }

      mNext : PRec; { указатель на следующую запись }

      end;

var Stack : PRec; { Голова (вершина) стека }

      { Процедура размещения строки в стеке }

procedure Push(const arg : string);

var p : PRec;

begin

New(p);       { создаем новую переменную-запись }

p^.mStr:= arg;       { размещаем строку }

{ размещаем в голове стека }

p^.mNext:= Stack; { указатель на предыдущую запись }

Stack:=p;       { текущая запись в голове стека }

end;

      { Процедура извлечения строки из стека }

function Pop(var arg : string): boolean;

var p : PRec;

begin

Pop:= Assigned(Stack); { Если стек не пуст, то TRUE }

if Assigned(Stack) then begin { Если стек не пуст… }

arg:= Stack^.mStr;       { извлекаем данные из головы стека }

p:= Stack;       { временно копируем указатель на голову }

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);

{ Пока стек не пуст, извлекаем и печатаем строки }