Теоретические сведения. Очередь (Queue) – это структура данных, представленная в виде списка элементов, обеспечивающая доступ к ним для чтения только с начала списка

Очередь (Queue) – это структура данных, представленная в виде списка элементов, обеспечивающая доступ к ним для чтения только с начала списка, а для записи – только с конца.

Позиция первого элемента в списке называется началом очереди (Front), а позиция последнего – концом очереди (Rear). Первоначально, начало и конец очереди совпадают, т.е. очередь является пустой.

Число элементов в списке определяет длину очереди (Length), которая находится по формуле: Length= Rear- Front+1.

При добавлении элемента в очередь (Операция Insert) позиция последнего элемента увеличивается на единицу, и новый элемент вставляется в конец списка.

При удалении элемента из очереди (Операция Delete) извлекается элемент, который находится в начале списка, а все остальные передвигаются на одну позицию вперед, уменьшая на единицу указатель Rear.

Таким образом, элементы удаляются из очереди в том же порядке, в котором они были там и сохранены, т.е. первый вставленный элемент будет и первым удаляемым. Такой режим доступа к данным получил название FIFO – первым пришел – первым вышел (First In – First Out).

Кроме операции добавления и удаления в очереди предусмотрена операция чтения (Front). Она возвращается значение первого элемента, который будет удален следующим, причем структура самой очереди не изменяется.

Определение очереди допускает возможность существования неограниченно большого списка элементов. Реально построение такой структуры данных практически невозможно. Поэтому очередь всегда имеет ограниченный размер (QueueSize). По мере заполнения очереди ее размер может достичь максимального значения, и добавление следующего элемента станет невозможным. Условием возникновения такой ошибки (QueueOverflow) является следующее равенство: Rear = QueueSize – 1.

Аналогичная ошибка (QueueEmpty) происходит при попытке удаления элемента из пустой очереди: Rear = –1.