:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Структуры данных » Введение в абстрактные структуры »
  Динамическая реализация стека на основе списка



Стек представляется как линейный список, в котором включение элементов всегда производятся в начала списка, а исключение - также из начала. Для представления его нам достаточно иметь один указатель - top, который всегда указывает на последний записанный в стек элемент. В исходном состоянии (при пустом стеке) указатель top - пустой. Процедуры StackPush и StackPop сводятся к включению и исключению элемента в начало списка. Обратите внимание, что при включении элемента для него выделяется память, а при исключении - освобождается.

Перед включением элемента проверяется доступный объем памяти, и если он не позволяет выделить память для нового элемента, стек считается заполненным. При очистке стека последовательно просматривается весь список и уничтожаются его элементы. При списковом представлении стека оказывается непросто определить размер стека. Эта операция могла бы потребовать перебора всего списка с подсчета числа элементов. Чтобы избежать последовательного перебора всего списка мы ввели дополнительную переменную stsize, которая отражает текущее число элементов в стеке и корректируется при каждом включении/исключении.

 {==== Программный пример  ====}
 { Стек на 1-связном линейном списке }
 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; { StackInit }
 {** очистка - освобождение всей памяти }
 Procedure StackClr;
  var x : stptr;
   begin   { перебор эл-тов до конца списка и их уничтожение }
   while top<>nil do
     begin  x:=top; top:=top^.next; Dispose(x);  end;
   stsize:=0;
 end; { StackClr }
 Function StackPush(a: data) : boolean;   { занесение в стек }
  var x : stptr;
   begin      { если нет больше свободной памяти - отказ }
   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; { StackPush }
 Function StackPop(var a: data) : boolean; { выборка из стека }
  var x : stptr;
   begin
   { список пуст - стек пуст }
   if top=nil then StackPop:=false
   else begin
     a:=top^.inf; { выборка информации из 1-го эл-та списка }
     { 1-й эл-т исключается из списка, освобождается память }
     x:=top; top:=top^.next; Dispose(top);
     stsize:=stsize-1; { коррекция размера }
     StackPop:=true;
 end;  end; { StackPop }
 Function StackSize : integer;  { определение размера стека }
   begin   StackSize:=stsize;   end; { StackSize }
 END.