Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




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

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

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

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

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

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

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

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

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


Поделиться:

Дата добавления: 2015-08-05; просмотров: 47; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты