X, y, verh : pstack;

a, b, i, n : integer;

begin

verh : = nil; {стек пуст}

writeln (‘n=’);

readln (n);

for I := 1 to n do

begin

new (y); {создание нового элемента стека – у получает адрес

свободной ячейки}

writeln (‘a=’); readln (a); {ввод с клавиатуры числа}

y^. data: = a; {информационная часть получает значение а, т.е. по

этому адресу в поле data записывается а}

y^. next : = verh; {адресная часть принимает значение указателя

вершины стека}

verh := y; {указатель вершины принимает значение

адреса нового элемента}

end;

writeln (‘элементы стека :’);

for i : = 1 to n do

begin

b : = verh ^ . data; { b принимает значение информационного поля

верхнего элемента}

writeln (‘b =’, b);

x : = verh; {указателю х присвоено значение указателя вершины

стека}

verh : = verh ^. next; {указатель вершины принимает значение

адреса следующего элемента стека}

dispose (x); {уничтожение указателя х, после чего ячейки,

содержавшие значение х ^ становятся свободными}

end;

readln;

End.

При выполнении программы указатель verh вначале получает значение nil – стек пуст. Затем в цикле вводятся значения а: 1, 2, 3, 4. Эти значения заносятся в поле data элементов стека. Поле next при этом получает значение, на которое указывает verh.

1

verh

verh

) 2)

nil

nil

1

2

1

verh

3)

При занесении новых элементов в стек указатель verh меняет свое значение и указывает каждый раз на только что введенный элемент.

Во второй части программы удаления элементов из стека указатель verh меняет свое значение в обратном порядке.

Очередь

Очередь – структура переменной длины, в которой добавление новых элементов производится в конец, а удаление существующих – из начала структуры.

FIFO

Для описания элемента типа очередь нужны две переменные-указатели начала и конца очереди. Определим их как х1 и х2, тогда описание имеет вид:

Type poc = ^ oc;

Oc = record

Data : integer;

Next : poc;

End;

Var x1, x2 : poc;

Над очередью определены 2 операции:

1. занесение элемента в конец очереди;

2. извлечение элемента из начала очереди.

Так как очередь может быть представлена списком, то занесение элемента в очередь соответствует занесению элемента в конец списка.

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

Procedure Write0 (var x1, x2 : poc; c : integer); {здесь х1 и х2 – формальные параметры-переменные-указатели начала и конца очереди, с – новое значение}.

Var u : poc;

Begin

New(u); {указатель u получает адрес свободной ячейки

динамической памяти }

u ^ . data : = c; {информационное поле получает значение с}

u ^ . next : = nil; {адресная часть получает значение указателя

конца очереди}

If x1 = nil

then x1 : = u {если очередь пуста, то указатель начала

х1 принимает значение нового адреса u}

else

x2 ^ . next : = u; {иначе элемент заносится в конец очереди по

адресу указателя х2 конца, далее х2 получает

значение адреса последнего элемента u}

x2 : = u;

End;

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

Т.к. извлечение элемента из пустой очереди осуществить нельзя, то сначала проверяем, есть ли элементы в очереди, т.е. задаем вопрос х1 = nil ?

Procedure ReadO (var x1, x2 : poc; var c : integer);

Var u : poc;

Begin

If x1 = nil then writeln (‘oсhered pusta’)