Очередь. Реализация очереди на базе циклического массива

Очередь содержит элементы, как бы выстроенные друг за другом в цепочку. У очереди есть начало и конец. Добавлять новые элементы можно только в конец очереди, забирать элементы можно только из начала. В отличие от обычной очереди, которую всегда можно при желании покинуть, из середины программистской очереди удалять элементы нельзя.

1. Описание реализации очереди:

В качестве базы выступает массив Q фиксированной длины N, таким образом, очередь ограничена и не может содержать более N-1 элементов. Индексы элементов массива изменяются в пределах от 1 до N.

Кроме массива, реализация очереди хранит две простые переменные: индекс начала очереди (голова – head), индекс конца очереди (хвост – tail).

Идея реализации очереди состоит в том, что массив мысленно как бы зацикливается в кольцо, т.е. за последним элементом массива следует его первый элемент. Таким образом, непрерывный отрезок массива, занимаемый элементами очереди, может переходить через конец массива на его начало.

Рис. 5

Для эффективности алгоритмов обработки очереди между головой и хвостом должна быть пустая ячейка, т.е Tail указывает на первую свободную ячейку (см. Рис. 6).

Первоначально имеем head=0, tail=1, т.е. очередь пуста.

Так как массив циклический, то при процедурах вставки нового элемента в очередь и удаления элемента из очереди позиция хвоста (Tail) и головы (Head) определяется неоднозначно: если Tail=n, то следующая позиция Tail=1, в остальных случаях Tail=Tail+1. Определение следующей позиции для хвоста и головы оформим в виде функции:

Function Pos (P)

{определяет следующую позицию для переменной p}

If P=n then Pos=1

Else Pos=P+1

При вставке нового элемента в очередь, необходимо сначала определить, есть ли свободное место с помощью процедуры Pos (Tail). Если голова и хвост встретились, то очередь переполнена.

procedure ADD_ELEM (Q, Head, tail, X)

{вставка элемента X в хвост очереди Q}

if Pos(Tail)=Head then 'Переполнение'

else Q[tail]=X

Tail=Pos(Tail)

При удалении элемента из очереди, необходимо включить проверку удаления из уже пустого стека, а также случай удаления единственного элемента очереди.

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

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

Стеки, очереди, деки, которые допускают добавление и удаление элементов и сначала, и с конца, являются частными случаями линейных списков.