Машинное представление стека и реализация операций

При представлении стека в статической памяти для стека выде-

ляется память, как для вектора. В дескрипторе этого вектора кроме

обычных для вектора параметров должен находиться также указатель

стека - адрес вершины стека. Указатель стека может указывать либо

на первый свободный элемент стека, либо на последний записанный в

стек элемент. (Все равно, какой из этих двух вариантов выбрать,

важно в последствии строго придерживаться его при обработке сте-

ка.) В дальнейшем мы будем всегда считать, что указатель стека

адресует первый свободный элемент и стек растет в сторону увели-

чения адресов.

При занесении элемента в стек элемент записывается на место,

определяемое указателем стека, затем указатель модифицируется та-

ким образом, чтобы он указывал на следующий свободный элемент

(если указатель указывает на последний записанный элемент, то

сначала модифицируется указатель, а затем производится запись

элемента). Модификация указателя состоит в прибавлении к нему или

в вычитании из него единицы (помните, что наш стек растет в сто-

рону увеличения адресов.

Операция исключения элемента состоит в модификации указателя

стека (в направлении, обратном модификации при включении) и вы-

борке значения, на которое указывает указатель стека. После вы-

борки слот, в котором размещался выбранный элемент, считается

свободным.

Операция очистки стека сводится к записи в указатель стека

начального значения - адреса начала выделенной области памяти.

Определение размера стека сводится к вычислению разности

указателей: указателя стека и адреса начала области.

Программный модуль, представленный в примере 4.1, иллюстри-

рует операции над стеком, расширяющимся в сторону уменьшения ад-

ресов. Указатель стека всегда указывает на первый свободный эле-

мент.

В примерах 4.1 и 4.3 предполагается, что в модуле будут

уточнены определения предельного размера структуры и типа данных

для элемента структуры:

const SIZE = ...;

type data = ...;

{==== Программный пример 4.1 ====}

{ Стек }

unit Stack;

Interface

const SIZE=...; { предельный размер стека }

type data = ...; { эл-ты могут иметь любой тип }

Procedure StackInit;

Procedure StackClr;

Function StackPush(a : data) : boolean;

Function StackPop(Var a : data) : boolean;

Function StackSize : integer;

Implementation

Var StA : array[1..SIZE] of data; { Стек - данные }

{ Указатель на вершину стека, работает на префиксное вычитание }

top : integer;

Procedure StackInit; {** инициализация - на начало }

begin top:=SIZE; end; {** очистка = инициализация }

Procedure StackClr;

begin top:=SIZE; end;

{ ** занесение элемента в стек }

Function StackPush(a: data) : boolean;

begin

if top=0 then StackPush:=false

else begin { занесение, затем - увеличение указателя }

StA[top]:=a; top:=top-1; StackPush:=true;

end; end; { StackPush }

{ ** выборка элемента из стека }

Function StackPop(var a: data) : boolean;

begin

if top=SIZE then StackPop:=false

else begin { указатель увеличивается, затем - выборка }

top:=top+1; a:=StA[top]; StackPop:=true;

end; end; { StackPop }

Function StackSize : integer; {** определение размера }

begin StackSize:=SIZE-top; end;

END.