Динамическая реализация стека на основе списка

Стек представляется как линейный список, в котором включение элементов всегда производятся в начала списка, а исключение - также из начала. Для представления его нам достаточно иметь один указатель - 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
Category:Алгоритмы
Category:Списки