ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Реализация очередей с помощью циклических массивов

Алгоритмы структуры данных

Реализация очередей с помощью циклических массивов

Реализацию списков посредством массивов, которая рассматривалась в разделе 2.2, можно применить для очередей, но в данном случае это не рационально. Действительно, с помощью указателя на последний элемент очереди можно выполнить оператор DEQUEUE за фиксированное число шагов (независимое от длины очереди), но оператор ENQUEUE, который удаляет первый элемент, требует перемещения всех элементов очереди на одну позицию в массиве. Таким образом, ENQUEUE имеет время выполнения Ω(n), где n — длина очереди.

Чтобы избежать этих вычислительных затрат, воспользуемся другим подходом. Представим массив в виде циклической структуры, где первая ячейка массива следует за последней, как показано на рис. 2.11. Элементы очереди располагаются в "круге" ячеек в последовательных позициях(отметим, что "последовательность" (непрерывность) позиций здесь понимается как "циклическая непрерывность". Например, очередь из четырех элементов может последовательно занимать две последние и две первые ячейки массива.), конец очереди находится по часовой стрелке на определенном расстоянии от начала. Теперь для вставки нового элемента в очередь достаточно переместить указатель Q.rear (указатель на конец очереди) на одну позицию по часовой стрелке и записать элемент в эту позицию. При удалении элемента из очереди надо просто переместить указатель Q.front (указатель на начало очереди) по часовой стрелке на одну позицию. Отметим, что при таком представлении очереди операторы ENQUEUE и DEQUEUE выполняются за фиксированное время, независимое от длины очереди.

Есть одна сложность представления очередей с помощью циклических массивов и в любых вариациях этого представления (например, когда указатель Q.rear указывает по часовой стрелке на позицию, следующую за последним элементом, а не на сам последний элемент). Проблема заключается в том, что только по формальному признаку взаимного расположения указателей Q.rear и Q.front нельзя сказать, когда очередь пуста, а когда заполнила весь массив. (Конечно, можно ввести специальную переменную, которая будет принимать значение true тогда и только тогда, когда очередь пуста, но если мы не собираемся вводить такую переменную, то необходимо предусмотреть иные средства, предотвращающие переполнение массива.)

 

 

 

 

 

Чтобы разобраться в этой проблеме, предположим, что очередь состоит из maxlength элементов (рис. 2.11), т.е. полностью заполнила массив. Тогда указатель Q.rear указывает на позицию рядом с Q.front, но находящуюся против часовой стрелки. Что будет, если очередь пуста? Чтобы увидеть представление пустой очереди, сначала положим, что очередь состоит из одного элемента. Тогда указатели Q.rear и Q.front указывают на одну и ту же позицию. Если мы удалим из очереди этот элемент, то указатель Q.front переместится на одну позицию по часовой стрелке, оформляя пустую очередь. Таким образом, в случае пустой очереди указатель Q.rear указывает на позицию рядом с Q.front, находящуюся против часовой стрелки, т.е. точно так же, как и при полном заполнении массива. Отсюда следует вывод, что без введения каких-либо механизмов определения пустых очередей при максимальной длине массива maxlength мы не можем позволить очереди иметь более maxlength — 1 элементов.

Теперь представим пять команд, выполняемых над очередями, использующими описанную реализацию. Формально очереди здесь определяются следующим образом:

type

QUEUE  =  record

elements:   array[1..maxlength]   of elementtype;

front,   rear:   integer

end;

Соответствующие процедуры показаны в листинге 2.11. Функция addone(i) добавляет единицу к позиции і в "циклическом" смысле.

 

25