|
Страница 23 из 60
Стеки Организация стека в определенном смысле противоположна орга-
низации очереди, поскольку здесь используется доступ по принципу
"последней пошел, первый вышел" /такой метод доступа иногда назы-
вают методом 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" в оператор деления для чисел с плаваю-
щей запятой /наклонная черта/.
|