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

Материал из 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