Стек – специальный тип списка, в котором все вставки и удаления элемента выполняются с одного конца списка, называемого вершиной стека. Обозначается LIFO(Last int –First out). Для работы с типом данных стек обычно используют следующие операторы:
1) MAKENULL(S) - Создать пустой стек S.
2) PUSH(x,S) - Вставить элемент x в вершину стека S.
3) ELEM(S) – Возвратить значение элемента из вершины стека.
4) EMPTY(S) - Проверить, является ли стек S пустым.
5) POP(S) – Возвратить значение элемента из вершины стека и удалить его оттуда.
Стек может быть реализован, как частный случай списка. Для этого надо объявить переменную S как переменную типа «список». Тогда первый оператор будет реализован одноимённой функцией для списка.
Реализация стека с помощью массива.
Используется подход, в котором изменяется расположение первого (верхнего) элемента стека. Элемент вершины стека обозначается специальной переменной top. Реализацию стека с помощью массива можно представить след-м образом:
const
maxlen=100;
type
Stack=record;
element:array[1..maxlen] of el_type;
top:integer;
end;
Покажем реализацию некоторых операторов для переменных типа стек:
1) Создать пустой стек
procedure MAKENULL(var S: Stack);
begin
S.top:=0
еnd;
2) Запись элемента в стек
procedure PUSH(x:el_type; var S:Stack);
begin
if S.top=maxlen then ERROR(«Стек заполнен»)
else
begin
S.top:=S.top+1;
S.element[S.top]:=x;
end;
end;
3)Выбор элементов из стека
Function POP(var S:Stack):el_type;
Begin
If S.top=0 then ERROR(“Стек пустой”);
Else
Begin
POP:=S.element[S.top];
S.top:=S.top-1;
End;
End;
|
Главная
Каталог файлов
