Создание и обработка стеков.

Стек – такая структура динамических данных, которая состоит из переменного числа компонент одинакового типа. Компоненты извлекаются из стека таким образом, что первой выбирается та компонента, которая была помещена последней. Извлеченная компонента в стеке не сохраняется.

Если помещать в стек последовательность 1, 2, 3, то получится следующий вид:

Опишем стек, в который можно помещать цепочку динамических переменных:

top – указатель на конец стека;
p – указатель на обслуживаемую в текущий момент область памяти.

Type

pitem = ^item;

item = record

data: integer;

prev: pitem

end;

Var

top, p: pitem;

Процедура добавления элемента в стек:

procedure add(x:integer,var top: pitem);

begin

p:=nil;

new(p);

p^.data := x;

p^.prev := top;

top := p

end;

Процедура add принимает в качестве фактического параметра число x, которое будет записано в содержательную часть элемента стека.

Выделяется память под указатель p, в содержательную часть которого записывается x, а в указатель – адрес, хранимый в top. Переменная top, в свою очередь, начинает ссылаться на выделенную под p область памяти.

Процедура удаления элемента из стека (удаляется с последнего):

procedure del (var top:pitem);

begin

if top<>nil then begin

p := top^.prev;

dispose(top);

top := p

end;

end;

В процедуре del в переменную p записывается адрес предпоследнего элемента стека. Последний элемент, ссылка на который хранится в top, удаляется. Далее top присваивается адрес элемента, на участок памяти, который указан p. К этому времени он стал уже не предпоследним, а последним элементом.

Удаление не происходит, если стек пустой (top указывает на nil).

Процедура вывода стека на экран:

procedure Print (top:pitem);

begin

writeln('Содержимое стека: ');

p := top;

while p <> nil do begin

write(p^.data, ' ');

p := p^.prev;

end;

writeln;

end;

Сначала p указывает на последний элемент. Выражения цикла whileбудут выполняться до тех пор, пока в p не запишется nil; это будет означать то, что перед этим был обработан первый элемент стека (который обрабатывается последним). В цикле сначала на экран выводится содержательная часть динамической переменной, на которую указывает p. Затем значение p меняется: переменная начинает указывать на следующий элемент.