14.2. Организация стека в динамической памяти

Стек – линейный односвязный список, для которого разрешено добавлять или исключать элементы только с одного конца списка – «вершины» стека.

Принцип работы стека: «последним пришел – первым вышел».

П р и м е р. Написать процедуры помещения элементов (целых чисел) в стек и извлечения их из стека.

Type pstack = ^element;

element = record

m: integer;

next: pstack

end;

Var p, st :pstack; {st - указатель на вершину стека}

I: integer;

k,n: integer;

Procedure put ( n: integer); {n- параметр- значение}

begin {Помещает значение в стек}

new(p); {выделение памяти под новый элемент}

p^.m:=n; {заносим в него информацию}

p^.next:=st; {указательная часть предшествующего

элемента указывает на вершину стека}

st:=p

end;

Procedure get( var n: integer); {извлекает элемент

из стека; n - параметр-переменная т.к. необходимо

изменить значение n в основной программе}

begin

p: =st; {запишем в р адрес вершины стека}

n: =p^.m; {в n - информационная часть верхнего

элемента стека}

st: =p^.next; {присваиваем вершине стека адрес

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

dispose (p);

end;

begin {основная программа }

st: nil; {вершина стека – «пустой» указатель,

стек пуст}

readln (k); {количество чисел}

for i:=1 to k

do begin {вводим числа и помещаем в стек}

readln(n);

put(n)

end;

…

while st<> nil

do begin {вывод элементов стека}

get(n);

writeln(n)

end;

end.

14.3. Очереди

Очередь – линейный односвязный список, для которого разрешены только два действия: извлечение элемента из начала очереди «головы» и добавление элемента в конец («хвост») очереди.

Другими словами, в очереди элементы всегда добавляются в конец, а удаляются из начала.

Принцип работы очереди: «первым пришел – первым вышел».

П р и м е р. Создать очередь из произвольного числа компонентов. Извлечь и напечатать все элементы очереди.

Type pocher= ^element;

element=record

m: integer;

next: poch;

end;

Var

no,ko,p:poch;{no –начало очереди, ko – конец очереди}

n,k,i: integer;

Procedure putoch(n:integer);{помещает значение в очередь}

begin

new(p); {выделение памяти под новый элемент}

p^.m:=n; {заносим в него информацию}

p^.next:=ko; {указательная часть ccылается

на начало очереди}

ko := p

end;

Procedure getoch(var n:integer);{извлек. эл-т из очереди}

begin

n: =p^.m; {в n - информационная часть 1-го элемента

очереди}

p: = no; {запишем в p адрес начала очереди}

no: =p^.next; { присваиваем началу очереди адрес

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

dispose (p);

end;

begin {основная программа}

readln (k);{создадим первый (он же последний) элемент}

new(p);

readln(n);

p^.m := n;

p^.next := nil;

no := p;

ko := p;

for i: =2 to k

do begin

readln(n);

putoch(n);

end;

while ko <> nil

do begin

getoch(n);

writeln(n)

end;

end.