Энциклопедия Turbo Pascal. Главы 1-4 - Стеки
ОГЛАВЛЕНИЕ
Стеки
Организация стека в определенном смысле противоположна организации очереди, поскольку здесь используется доступ по принципу "последней пошел, первый вышел" /такой метод доступа иногда называют методом LIFO/. Представим себе стопку тарелок. Нижняя тарелка из этой стопки будет использована последней, а верхняя тарелка
/которая была установлена в стопку последней/ будет использована первой. Стеки широко используются в системном программном обеспечении, включая компиляторы и интерпретаторы.
Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека - получили название соответственно "затолкнуть" и "вытолкнуть". Поэтому для реализации стека необходимо создать две функции: "posh" /затолкнуть/, которая помещает элемент в вершину стека, и "pop" / вытолкнуть/, которая выбирает из вершины стека значение. Необходимо также предусмотреть определенную область в памяти, где фактически будет храниться стек. Для этого можно использовать массив или можно выделить область памяти, используя средство динамического распределения памяти, предусмотренное в языке Турбо Паскаль. Как и при работе с очередью при выборке значения из стека элемент будет потерян, если его не сохранить гденибудь в памяти. Ниже приводится общая форма процедур установки в стек и выборки из стека.
const
MAX = 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);
Push(a*b);
end;
'/' 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" в оператор деления для чисел с плавающей запятой /наклонная черта/.