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

Материал из DRKB


При представлении стека в статической памяти для стека выделяется память, как для вектора. В дескрипторе этого вектора кроме обычных для вектора параметров должен находиться также указатель стека - адрес вершины стека. Указатель стека может указывать либо на первый свободный элемент стека, либо на последний записанный в стек элемент. (Все равно, какой из этих двух вариантов выбрать, важно в последствии строго придерживаться его при обработке стека.) В дальнейшем мы будем всегда считать, что указатель стека адресует первый свободный элемент и стек растет в сторону увеличения адресов.

При занесении элемента в стек элемент записывается на место, определяемое указателем стека, затем указатель модифицируется таким образом, чтобы он указывал на следующий свободный элемент (если указатель указывает на последний записанный элемент, то сначала модифицируется указатель, а затем производится запись элемента). Модификация указателя состоит в прибавлении к нему или в вычитании из него единицы (помните, что наш стек растет в сторону увеличения адресов.

Операция исключения элемента состоит в модификации указателя стека (в направлении, обратном модификации при включении) и выборке значения, на которое указывает указатель стека. После выборки слот, в котором размещался выбранный элемент, считается свободным. Операция очистки стека сводится к записи в указатель стека начального значения - адреса начала выделенной области памяти. Определение размера стека сводится к вычислению разности указателей: указателя стека и адреса начала области.

Программный модуль, представленный в примере, иллюстрирует операции над стеком, расширяющимся в сторону уменьшения адресов. Указатель стека всегда указывает на первый свободный элемент.

Предполагается, что в модуле будут уточнены определения предельного размера структуры и типа данных для элемента структуры:


{==== Программный пример ====}
{ Стек }
unit Stack;

interface

const
  SIZE = ...;     { предельный размер стека }
type
  TData = ...;    { элементы могут иметь любой тип }

{ инициализация - на начало }
procedure StackInit;
{ очистка = инициализация }
procedure StackClr;
{ занесение элемента в стек }
function StackPush(a: TData): Boolean;
{ выборка элемента из стека }
function StackPop(var a: TData): Boolean;
{ определение размера }
function StackSize: Integer;

implementation

var
  StA: array [1..SIZE] of TData;   { Стек - данные }
  { Указатель на вершину стека, работает на префиксное вычитание }
  top: Integer;

procedure StackInit;
begin
  top := SIZE;
end;

procedure StackClr;
begin
  top := SIZE;
end;

function StackPush(a: TData): Boolean;
begin
  if top = 0 then
    Result := False
  else
  begin { занесение, затем - увеличение указателя }
     StA[top] := a;
     top := top - 1;
     StackPush := True;
  end;
end;

function StackPop(var a: TData): Boolean;
 begin
   if top = SIZE then
     StackPop := False
   else
   begin { указатель увеличивается, затем - выборка }
     top := top + 1;
     a := StA[top];
     StackPop := True;
  end;
end;

function StackSize: Integer;
begin
  StackSize := SIZE - top;
end;

end.


Source: http://algolist.manual.ru
ID: 03961