Очередь - это линейный список, в котором все включения производятся на одном конце списка, а исключения делаются на другом конце. Принцип организации очереди: "Первый пришел - первый вышел", что сокращенно обозначают также FIFO (‘First in – first out’).
Указатели R и L (рис.18) определяют правый (Right) и левый (Left) концы очереди. Указатели Next, входящие в состав каждого элемента, определяют адрес следующего справа элемента в очереди. Следовательно, с левого конца можно и добавить, и удалить элемент (как в стеке). Указатель Next крайнего правого элемента пустой. Этому элементу неизвестно, где находится предыдущий элемент. Поэтому справа можно только добавлять новые элементы. Следовательно, в очереди добавление элемента должно производиться справа, а удаление - слева.
В дальнейшем будем считать, что в каждом фрагменте программы, иллюстрирующей методы формирования и обработки очереди, действует следующее описание:
TypePoinType = ^DynType;
DynType = record
Inf : integer;
Next : PoinType;
end;
VarL, { указатели левого и правого }
R, { концов очереди }
Run : PoinType; { текущий указатель }
k : integer;
F : text;
