Динамическая реализация стека на основе списка
Материал из DRKB
Стек представляется как линейный список, в котором включение элементов всегда производятся в начала списка, а исключение - также из начала. Для представления его нам достаточно иметь один указатель - top, который всегда указывает на последний записанный в стек элемент. В исходном состоянии (при пустом стеке) указатель top - пустой. Процедуры StackPush и StackPop сводятся к включению и исключению элемента в начало списка. Обратите внимание, что при включении элемента для него выделяется память, а при исключении - освобождается.
Перед включением элемента проверяется доступный объем памяти, и если он не позволяет выделить память для нового элемента, стек считается заполненным. При очистке стека последовательно просматривается весь список и уничтожаются его элементы. При списковом представлении стека оказывается непросто определить размер стека. Эта операция могла бы потребовать перебора всего списка с подсчета числа элементов. Чтобы избежать последовательного перебора всего списка мы ввели дополнительную переменную stsize, которая отражает текущее число элементов в стеке и корректируется при каждом включении/исключении.
{==== Программный пример ====}
{ Стек на 1-связном линейном списке }
unit Stack;
interface
type
TData = ...; { элементы могут иметь любой тип }
{ инициализация - список пустой }
procedure StackInit;
{ очистка - освобождение всей памяти }
procedure StackClr;
{ занесение в стек }
function StackPush(a: TData): Boolean;
{ выборка из стека }
function StackPop(var a: TData): Boolean;
{ определение размера стека }
function StackSize: Integer;
implementation
type
PStRec = ^TStRec; { указатель на элемент списка }
TStRec = record { элемент списка }
Inf: TData; { данные }
Next: PStRec; { указатель на следующий элемент }
end;
var
Top: PStRec; { указатель на вершину стека }
StSize: LongInt; { размер стека }
{ инициализация - список пустой }
procedure StackInit;
begin
Top := nil;
StSize := 0;
end;
{ очистка - освобождение всей памяти }
procedure StackClr;
var
x: PStRec;
begin { перебор элементов до конца списка и их уничтожение }
while Top <> nil do
begin
x := Top;
top := Top^.Next;
Dispose(x);
end;
StSize := 0;
end;
{ занесение в стек }
function StackPush(a: TData): Boolean;
var
x: PStRec;
begin
{ если нет больше свободной памяти - отказ }
if MaxAvail < SizeOf(TStRec) then
Result := False
else
begin
{ выделение памяти для элемента и заполнение инф. части }
New(x);
x^.Inf := a;
{ новый элемент помещается в голову списка }
x^.Next := Top;
Top := x;
StSize := StSize + 1; { коррекция размера }
Result := True;
end;
end;
{ выборка из стека }
function StackPop(var a: TData): Boolean;
var
x: PStRec;
begin
{ список пуст - стек пуст }
if Top = nil then
Result := False
else
begin
a := Ttop^.Inf; { выборка информации из 1-го элемента списка }
{ 1-й элемент исключается из списка, освобождается память }
x := Top;
Top := Top^.Next;
Dispose(Top);
StSize := StSize - 1; { коррекция размера }
Result := True;
end;
end;
{ определение размера стека }
function StackSize: Integer;
begin
Result := StSize;
end;
end.
Source: http://algolist.manual.ru
ID: 03962