Очередь

Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются заказы на то или иное обслуживание. В программировании имеется структура данных, кото­рая называется очередью. Эта структура данных использует­ся например, для моделирования реальных очередей с целью определения их характеристик при данном законе поступле­ния заказов и дисциплине их обслуживания. По своему суще­ству очередь является полустатической структурой - с течени­ем времени и длина очереди, и состав могут изменяться.

На рис. 2. 13 приведена очередь, содержащая четыре элемента — А, В, С и D. Элемент А расположен в начале очереди, а элемент D — в ее конце. Элементы могут удалять­ся только из начала очереди, то есть первый помещаемый в очередь элемент удаляется первым. По этой причине очередь часто называют списком, организованным по принципу «пер­вый размещенный первым удаляется» в противоположность принципу стековой организации — «последний размещенный первым удаляется».

Дисциплину обслуживания, в которой заказ, поступив­ший в очередь первым, выбирается первым для обслужива­ния (и удаляется из очереди), называется FIFO (First In First Out - Первым пришел, первым ушел). Очередь открыта с обеих сторон.

Таким образом, изъятие компонент происходит из нача­ла очереди, а запись - в конец. В этом случае вводят два ука­зателя: один - на начало очереди, второй - на ее конец.

Реальная очередь создается в памяти ЭВМ в виде одно­мерного массива с конечным числом элементов, при этом не­обходимо указать тип элементов очереди, а также необходи­ма переменная в работе с очередью.

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

Операции, производимые над очередью:

Операция insert (q,x) - помещает элемент х в конец очереди q.

Операция remove (q) удаляет элемент из начала очереди q и присваивает его значение переменной х.

Операция, empty (q) - вводится с целью предотвращения возможности выборки из пустой очереди.

Операция full (q) - вводится с целью предотвращения возможности переполнения одномерного массива, на котором реализуется полустатическая очередь.

Алгоритмы основных операций с очередью

Full (q)

if R = maxQ then full = true

else full = false

endif

return

Empty (q)

if R < F then empty = true

else empty = false

endif

return

Insert (q, x)

Full (q)

if full = true then ‘переполнение’

stop

return

endif

R = R + 1

q(R) = x

return

Remove (q)

Empty (q)

if empty = true then ‘пусто’

stop

return

endif

x = q(F)

F = F + 1

return