Очереди и их применение

Вторым распространенным типом линейных списков являются очереди. Это список типа FIFO (первым пришел – первым вышел) с двумя точками входа: начало и конец. Очередь пополняется с конца и продвигается с начала.

В жизни все мы сталкиваемся с очередями (за билетами, на дежурство и т.п.). В программировании часто приходится иметь дело с очередями на получение различных системных ресурсов.

Аналогично стекам очереди могут быть организованы на основе массивов или динамических структур. При использовании массива начало очереди находится в первом элементе, а конец задается индексом и меняется при изменении очереди. Впрочем, возможно расположить очередь в массиве и в противоположном направлении.

Пусть очередь описана Var Och[1..N] of T, где T – тип элементов очереди. Конец очереди задан индексом Endo.

Постановка в очередь производится командами

Endo:= Endo+1;

Och[Endo]:=NewElement;

Продвижение очереди выполняется команками

For I:=1 to Endo-1 do Och[I]:= Och[I+1];

Endo:= Endo-1;

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

При организации очереди на основе указателей используется следующее описание

Type

Ukaz=^Och;

Och=record

Info: …;

{ поля информационной части элемента }

Next: ukaz

end;

Var

Bego, Endo: ukaz; { начало и конец очереди }

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

New(Kon);

Endo^.Next:=Kon;

Kon^.Next:=Nil;

и далее присвоение значений информационным полям.