Моделирование работы стека
Модуль содержит вариант реализации стека на структуре данных «вектор». Стек расширяется в сторону уменьшения адресов. Указатель стека всегда указывает на первый свободный элемент. Перед использованием модуля должен быть определен предельный размер стека и структура элемента данных стека.
unit Stack;
Interface
const stsize = 10; { предельный размер стека }
type data = ...; { элементы могут иметь любой тип }
procedure StackInit;
procedure StackClr;
function StackPush(a: data): Boolean;
function StackPop(var a: data): Boolean;
function StackSize: Integer;
Implementation
var sta: array[1..stsize] of data; { данные стека }
{ Указатель на вершину стека,
работает на префиксное вычитание }
top: Integer;
{ инициализация - на начало }
procedure StackInit;
Begin
top:=stsize;
end;
{ очистка = инициализация }
procedure StackClr;
Begin
top:=stsize;
end;
{ занесение элемента в стек }
function StackPush(a: data): Boolean;
Begin
if top = 0 then
StackPush:=False else
Begin
{ занесение, затем - коррекция указателя }
sta[top]:=a;
top:=top-1;
StackPush:=True;
end;
end;
{ выборка элемента из стека }
function StackPop(var a: data): Boolean;
Begin
if top = stsizethen
StackPop:=False else
Begin
{ коррекция указатель, затем - выборка }
top:=top+1;
a:=sta[top];
StackPop:=True;
end;
end;
function StackSize: Integer; { определение размера }
Begin
StackSize:=stsize-top;
end;
end.
Модуль содержит вариант реализации стека на односвязном линейном списке.
unit stack;
Interface
type data = ...; { элементы могут иметь любой тип }
procedure StackInit;
procedure StackClr;
function StackPush(a: data): Boolean;
function StackPop(var a: data): Boolean;
function StackSize: Integer;
Implementation
Type
stptr = ^stit; { указатель на элемент списка }
stit = record{ элемент списка }
inf : data; { данные }
next: stptr; { указатель на следующий элемент }
end;
Var
top: stptr; { указатель на вершину стека }
stsize: LongInt; { размер стека }
{ инициализация - список пустой }
procedure StackInit;
Begin
top:=nil;
stsize:=0;
end;
{ очистка - освобождение всей памяти }
procedure StackClr;
var x: stptr;
Begin
{ перебор элементов до конца списка и их уничтожение }
while top <> nil do
Begin
x:=top;
top:=top^.next;
Dispose(x);
end;
stsize:=0;
end;
function StackPush(a: data): Boolean; { занесение в стек }
var x: stptr;
Begin
{ если нет больше свободной памяти –
отказ; использовать только для BP 7.0 }
if MaxAvail < SizeOf(stit) then
StackPush:=False else
{ выделение памяти для элемента и заполнение информационной части }
Begin
New(x);
x^.inf:=a;
{ новый элемент помещается в голову списка }
x^.next:=top;
top:=x;
stsize:=stsize+1; { коррекция размера }
StackPush:=True;
end;
end;
function StackPop(var a: data): Boolean; { выборка элемента из стека }
var x: stptr;
Begin
{ список пуст - стек пуст }
if top = nil then
StackPop:=False else
Begin
{ выборка информации из первого элемента списка }
a:=top^.inf;
{ первый элемент исключается из списка, освобождается память }
x:=top;
top:=top^.next;
Dispose(x);
stsize:=stsize-1; { коррекция размера }
StackPop:=True;
end;
end;
function StackSize: Integer; { определение размера стека }
Begin
StackSize:=stsize;
end;
end.
Дата добавления: 2021-12-14; просмотров: 297;