СТЕКИ
Организация стека в определенном смысле противоположна орга- низации очереди, поскольку здесь используется доступ по принципу "последней пошел, первый вышел" /такой метод доступа иногда назы- вают методом LIFO/. Представим себе стопку тарелок. Нижняя тарел- ка из этой стопки будет использована последней, а верхняя тарелка /которая была установлена в стопку последней/ будет использована первой. Стеки широко используются в системном программном обеспе- чении, включая компиляторы и интерпретаторы.
Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека - получили название соответственно "затолкнуть" и "вытолкнуть". Поэтому для реализа- ции стека необходимо создать две функции: "posh" /затолкнуть/, которая помещает элемент в вершину стека, и "pop" / вытолкнуть/, которая выбирает из вершины стека значение. Необходимо также пре- дусмотреть определенную область в памяти, где фактически будет храниться стек. Для этого можно использовать массив или можно вы- делить область памяти, используя средство динамического распреде- ления памяти, предусмотренное в языке Турбо Паскаль. Как и при работе с очередью при выборке значения из стека элемент будет по- терян, если его не сохранить гденибудь в памяти. Ниже приводится общая форма процедур установки в стек и выборки из стека.
constMAX = 100;
var
stack:array[1..100] of integer;
tos:integer; {points to top of stask}
{ помещение объекта в стек }
procedure Push(i:integer);
begin
if tos>=MAX then WriteLn('Stask full')
else
begin
stack[tos]:=i;
tos:=tos+1;
end;
end; { конец процедуры помещения объекта в стек}
{ выборка объекта из стека }
function Pop:integer;
begin
tos:=tos-1;
if tos<1 then
begin
WriteLn('Stack underflow');
tos:=tos+1;
Pop:=0;
end
else Pop := stack[tos];
end; { конец функции выборки объекта из стека }
Переменная "tos" содержит значение индекса для следующего помещаемого в стек элемента. При реализации этих процедур никогда нельзя забывать о проверке ситуаций переполнения стека и выборки из пустого стека. В приведенных процедурах нулевое значение ука- зателя "tos" означает, что стек пуст, а значение этого указателя, равное или превышающее адрес последней ячейки памяти, где содер- жится стек, означает заполнение стека. Рис.7 иллюстрирует работу стека.
Операция Содержимое стекаPush(A) A
Push(B) B A
Push(C) C B A
Pop, выбирается С В А
Push(F) F B A
Pop, выбирается F B A
Pop, выбирается В А
Рор, выбирается А пусто
Рис.7. Работа стека.
Хорошим примером применения стека является калькулятор, ко- торый может выполнять четыре действия. Большинство калькуляторов используют стандартную форму выражений, которая носит название инфиксной формы. В общем виде ее можно представить в виде "опе- ранд-оператор-операнд". Например, для прибавления 100 к 200 вы должны ввести число 100, набрать символ сложения, ввести число 200 и нажать клавишу со знаком равенства. Однако, некоторые каль- куляторы применяют другую форму выражений, получившую название постфиксной формы. В этом случае оба операнда вводятся перед вво- дом оператора. Например, для добавления 100 к 200 при использова- нии постфиксной формы сначала вводится число 100, затем вводится число 200 и после этого нажимается клавиша со знаком плюс. Вве- денные операнды помещаются в стек. При вводе оператора из стека выбираются два операнда и результат помещается в стек. При ис- пользовании постфиксной формы очень сложные выражения могут легко вычисляться на калькуляторе. Ниже показана программа для такого калькулятора. { калькулятор с четырьмя операциями, иллюстрирующий работу }
program four_function_calc;const MAX = 100;
var
stack:array [1..100] of integer;
tos:integer; { указатель вершины стека }
a, b:integer;
s:string[80];
{ поместить объект в стек }
procedure Push(i:integer);
begin
if tos >= MAX then Writeln('Stack full')
else
begin
stack[tos] :=1;
tos := tos+1;
end;
end;{Push}
{ выборка объекта из стека }
function Pop:integer;
begin
tos := tos-1;
if tos < 1 then
begin
Writeln('Stack underflow')
tos := tos+1;
Pop := 0;
end
else Pop := stack[tos];
end;{ Pop }
begin { калькулятор }
tos := 1;
Writeln('For Function Calculator');
repeat Write(': '); { вывод приглашения }
Readln(s);
Val(s, a, b) { преобразование строки символов в целое число }
{ считается, что при успешном преобразовании пользователь ввел число, а в противном случае пользователь ввел оператор}
if (b=0) and ((Length(s)>1) or (s[1]<>'-')) then
Push(a)
else
case s[1] of
'+' begin
a := Pop
b := Pop
Writeln(a+b);
Push(a+b);
end;
'-' begin
a := Pop
b := Pop
Writeln(b+a);
Push(b+a);
end;
'*' begin
a := Pop
b := Pop
Writeln(a*b);
'/' begin
a := Pop
b := Pop
if a=0 then Writeln('divide by zero');
else
begin
Writeln(b div a);
Push(b div a);
end;
end;
'.' begin
a := Pop
Writeln(a);
Push(a);
end;
end;
until UpCase(s[1])='G'
end.
Для того, чтобы посмотреть, что находится в вершине стека, достаточно ввести точку. Хотя данная программа выполняет арифме- тические действия только с целыми числами, ее легко можно приспо- собить для чисел с плавающей запятой, изменяя тип данных стека и преобразуя оператор "div" в оператор деления для чисел с плаваю- щей запятой /наклонная черта/.
