Очередь

Самыми распространенными случаями линейного односвязного списка

являются очередь и стек.

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

Очередь можно представить в виде трубы с двумя открытыми концами, куда помещаются «бочонки-элементы». Движение по трубе возможно лишь в одном направлении

начало конец

взять добавить

Очередь - динамическая структура или дисциплина обслуживания, организованная по принципу FIFO (first in-first out). "Первым пришел - первым ушел". Основные операции для работы с очередями: добавление нового элемента в конец очереди (занесение заказа на обслуживание); удаление элемента из начала очереди для его обслуживания, при этом выбранный элемент, естественно, исключается из очереди. Таким образом, в очереди доступны только ее начало и конец.

Для создания очереди и работы с ней необходимо иметь как минимум два указателя: на начало очереди (BegP) и на конец очереди EndQ. Кроме того, для освобождения памяти удаляемых элементов и удобства работы с очередью требуется дополнительный временный указатель (t).

Функции, которые могут быть использованы при работе с очередями:

1) ADDE1() [insert()] вставляет элемент (добавить в очередь элемент), отводит память под очередной элемент, заносит в него нужную информацию и ставит в конец очереди;

2) GetDELEl() [take_off()] удаляет из очереди ее первый элемент, свобождает память и перемещает указатель начала очереди на следующий элемент.

Пример. Создание очереди (односвязного списка) добавлением элементов в начало

Program queue0; {queue0.pas}

Uses crt;

Type

ptr=^elem;

elem=record

inf: integer;

next: ptr

end;

Var beg_p, t, end_q: ptr;

x: integer;

i: byte;

Procedure ADDEl(val:integer); {Добавление элемента}

Var pt:ptr;

Begin

new(pt);

pt^.inf:=val;

pt^.next:=nil;

if end_q = nil then Beg_p:=pt {если создается первый элемент}

else end_q^.next:=pt; {если создается очередной элемент}

End_q:=pt

End;

Procedure GetDelEl(Var Val:integer);

var pt:ptr;

begin

val:=beg_p^.inf;

pt:=beg_p;

beg_P:=pt^.next;

if Beg_p=nil then end_q:=nil; {если удаляется последний элемент}

dispose(pt)

end;

BEGIN

clrscr;

Beg_p:=nil;

end_q:=nil; {Начальная установка указателей}

for i:=1 to 10 do AddEl(i);{Создание очереди из 10 элементов}

{Удаление очереди с распечаткой значений ее элементов}

while Beg_p<>nil do

begin

GetDelEl(x);

writeln('x=',x:4)

end;

END.

Стек

Наиболее часто встречающаяся динамическая структура данных – стек (магазин) отличается от очереди тем, что она организована по принципу LIFO (last in - first out): «последним пришел - первым ушел».

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

Стек можно представить в ввиде трубы с одним запаяным концом, куда помещаются «бочонки» - элементы:

Вершина стека

Добавить

Взять

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

Если число элементов не может превышать некоторой величины, то стек называется ограниченным, максимальное число элементов в нем - это глубина стека. Стек, в котором нет ни одного элемента, называется пустым.

Стек можно представить в виде динамической цепочки звеньев. Вершиной является первое звено цепочки (или последнее), заглавное звено становится излишним. Поэтому значением указателя, представляющего стек как единый объект, является ссылка на вершину стека. Каждое звено содержит ссылку на следующее звено цепочки, причем "дно" стека имеет ссылку NIL:

Если стек пуст, то значением указателя р является ссылка NIL. К началу использования стека его необходимо сделать пустым (p=NIL).

Операции над стеком:

1) Занесение элемента в стек.

2) Выбор элемента из стека. При этом элемент, находящийся в вершине стека, должен быть присвоен в качестве значения некоторой переменной, а звено, в котором был представлен этот элемент, должно быть исключено из стека.

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

Program stack; stack.pas

Uses crt;

Type ptr = ^elem;

elem = record

inf: integer;

next: ptr

end;

Var

Результаты х = 10 х = 9 х = 8 х = 7 х = 6 х = 5 х = 4 х = 3 х = 2 х = 1    

Top: ptr;

x: integer;

i: byte;

Procedure Push(val:integer); {Добавление элемента}

Var pt: ptr;

Begin

new(pt);

pt^.inf:=val;

pt^.next:=Top;

Top:=pt

End;

Procedure Pop(Var Val:integer); {Извлечение }

Var pt: ptr;

begin

val:=Top^.inf;

pt:=Top;

Top:=pt^.next; dispose(pt)

end;

BEGIN

clrscr;

Top:=nil; {Начальная установка указателей}

for i:=1 to 10 do Push(i); {Создание стека из 10 элементов. Удаление стека с

распечаткой значений его элементов}

while Top<>nil do

begin

Pop(x);

writeln('x=',x:4)

end

END.

Дата добавления: 2015-09-05