Реверсирование стека.

При формировании стека из текстового файла информационные элементы стека будут расположены в обратном порядке по сравнению с их расположением в файле. Это может создавать определенные неудобства при обработке стека в программе. В связи с этим возникает задача реверсирования элементов стека.

По отношению к обычному массиву задача реверсирования стека аналогична перестановке элементов массива в обратном порядке. Существенная разница между ними заключается в том, что положение информационных элементов стека в памяти не должно изменяться, изменению подвергаются лишь связи между элементами, т.е. значения указателей.

Выполним два варианта реверсирования стека.

Вариант 1 :

Var BegBuf,RunBuf : PoinType;

Begin

BegBuf:=nil; Run:=Beg;

If(Run<>nil)and(Run^.Next<>nil)then{ в стеке }

Begin{ больше одного эл-та }

WhileRun<>nil do { перепись стека Beg }

Begin { в стек BegBuf }

k:=Run^.Inf; New(RunBuf);

RunBuf^.Inf:=k;

RunBuf^.Next:=BegBuf;

BegBuf:=RunBuf;

Run:=Run^.Next;

End;

While Beg<>nil do { удаление стека Beg }

Begin

Run:=Beg; Beg:=Beg^.Next;

Dispose(Run);

End;

Beg:=BegBuf; BegBuf:=nil; { переадресация }

End; { стека }

В варианте 1 исходный стек переписывается в буферный с начальным указателем BegBuf, при этом элементы исходного стека будут расположены в обратном порядке. После этого стек Beg удаляется, указателю Beg присваивается адрес входа в новый стек BegBuf, а буферный указатель принимает пустое значение. Если исходный стек пустой или в нем находится только один элемент, реверсирование не производится.

В программе варианта 1 следует обратить внимание на следующую деталь.

Если стек пустой, т.е. Beg = nil, то указатель Beg^.Next не существует. В этом случае запись условного оператора в виде

If(Run^.Next<>nil) and (Run<>nil) then

может привести к неправильной работе программы или к ее зацикливанию.

Вычисление логического выражения в Паскаль-программе производится по так называемой короткой схеме. Это означает, что вычисление выражения прекращается, как только становится очевидным его результат. В частности,

- если несколько операндов связаны между собой операцией логического умножения, то при получении значения false для одного из операндов, вычисляемых слева направо, остальные операнды не рассматриваются;

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

Поэтому в операторе

If(Run<>nil) and (Run^.Next<>nil) then

при обнаружении (Run <> nil) = false значение второго операнда не вычисляется.

Недостатки варианта 1 :

- в программе используется буферный стек, что требует выделения дополнительной памяти;

- при формировании буферного стека производится пересылка информационных элементов из исходного стека, что приводит к дополнительным затратам машинного времени (информационные элементы могут быть большого размера).

Вариант 2 :

VarP : PoinType;

Begin

If Beg<>nil then

Begin

Run:=Beg; Beg:=Beg^.Next;

Run^.Next:=nil;

While Beg<>nil do

Begin

P:=Beg; Beg:=Beg^.Next;

P^.Next:=Run; Run:=P;

End;

Beg:=Run;

End;

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

Примечание. Если в программе заранее известно, что последовательность элементов в линейном списке должна быть такой же, как и в исходном файле, то в этом случае целесообразно вместо стека использовать очередь.