35. Создание и обработка стеков.
Стек – такая структура динамических данных, которая состоит из переменного числа компонент одинакового типа. Компоненты извлекаются из стека таким образом, что первой выбирается та компонента, которая была помещена последней. Извлеченная компонента в стеке не сохраняется.
Если помещать в стек последовательность 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 меняется: переменная начинает указывать на следующий элемент.
36.Создание и обработка очередей.
Очередь– такая структура данных, при которой изъятие компонент происходит из начала цепочки, а запись – в конец цепочки.
В этом случае вводят два указателя: один на начало очереди, другой – на ее конец.
Описание типа для очереди:
type ptr=^rec;
rec=record
str:string;
next:ptr;
end;
var r,q:ptr; {указатели на начало и конец очереди}
Добавление элемента в очередь:
Procedure Add(var r,q:ptr);
var
cur : ptr;{текущий указатель}
x:какой-то тип;спокойно
begin
Write ('Dobavit element: ');
Readln (x);
Cur:=nil;
New (cur);
cur^.str:=x;
cur^.next:=Nil;
If r = nil then r:=cur
else q^.next:=cur;
q:=cur;
end;
Удаление первого элемента из очереди:
Procedure Delete (var r:ptr);
Var cur:ptr;
begin
if r=nil then writeln ('Ochered not create')
else
if Sizeoflist (r)=1 then
begin
cur:=r;
dispose (cur);
r:=nil;
end
else
begin
cur:=r;
r:=cur^.next;
dispose (cur);
end;
end.