Комбинаторные алгоритмы для программистов

         

Очереди


Очередь - одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения (head) и конца (tail) очереди в соответствии с правилом FIFO ("first-in, first-out" - "первым введен, первым выведен").

  1. Начальная установка:

Head:=1; tail:=1;

  1. Добавление элемента x:

Queue[tail]:=x; tail:=tail+1; If tail>qd then tail:=1; Здесь qd - размерность очереди.

  1. Исключение элемента x:

x:=queue[head]; head:=head+1; if head>qd then head:=1;

  1. Проверка переполнения очереди и включение в нее элемента:

Temp:=tail+1; If temp>qd then temp:=1; If temp=head then \{переполнение\} Else btgin queue[tail]:=x; tail:=temp end;

  1. Проверка элементов и исключение элемента:

If head:=tail then \{очередь пуста\} else begin x:=queue[head]; head:=head+1; if yead>qd then head:=1; end;

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



Содержание раздела