Очередь содержит элементы, как бы выстроенные друг за другом в цепочку. У очереди есть начало и конец. Добавлять новые элементы можно только в конец очереди, забирать элементы можно только из начала. В отличие от обычной очереди, которую всегда можно при желании покинуть, из середины программистской очереди удалять элементы нельзя.
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)
При удалении элемента из очереди, необходимо включить проверку удаления из уже пустого стека, а также случай удаления единственного элемента очереди.
Во многих важных приложениях требуется выбрать среди динамически изменяемого множества элемент с наивысшим приоритетом. Часто для решения подобной задачи применяют структуру данных, которая называется очередью с приоритетами. Эта очередь представляет собой совокупность элементов данных, частично упорядоченных по какому-либо правилу. К основным операциям над очередью с приоритетами относятся: поиск максимального элемента, извлечение максимального элемента и добавление нового элемента. Само собой разумеется, что последние две операции должны быть реализованы так, чтобы в результате их выполнения получалась новая очередь с приоритетами.
|
|
Проще всего реализовать такую структуру данных на базе массива или упорядоченного массива, однако ни одно из них не является оптимальным. В более удачных реализациях используется такая древовидная структура как, пирамида (куча).
Стеки, очереди, деки, которые допускают добавление и удаление элементов и сначала, и с конца, являются частными случаями линейных списков.