Очереди

Очередьюназывается упорядоченный набор элементов, которые могут удаляться с начала очереди и помещаться в конец очереди (рис. 2.9). Очередь организована в отличие от стека по принципу FIFO (first input — first output; первым вошел — первым вышел) [1, 3, 8, 11].

Для очереди определены три простейшие операции:

• insert(g, х) — помещает элемент х в конец очереди q, где q — указатель на очередь;

• х = remove(g) — удаляет элемент х из очереди q;

• empty(g) — возвращает true или false в зависимости от того, является ли очередь пустой или нет.

Реализация очереди на базе массива

Рассмотрим реализацию очереди на базе массива. Используем, например, массив и две переменные frnt и rear, которые запоминают позиции первого и последнего элементов. Изначально fmt=\ и геаг=0. Очередь пуста, если rear <frnt. Число элементов в очереди rear -frnt + 1.