Главная » Java, Структуры данных и алгоритмы » Реализация очереди на основе массива

0

В этом разделе рассмотрим, каким образом осуществляется реализация очереди с помощью массива Q, длина которого для хранения элементов очереди, например, N = 1000. Так как основной характеристикой АТД «очередь» является добавление и удаление объектов по принципу FIFO, необходимо определить способ наблюдения за началом и концом очереди.

Одним из возможных решений является подход, примененный при реализации стека, а именно — допущение, что Q[0] является первым элементом очереди и с него начинается рост очереди. Однако такое решение не является эффективным, так как в этом случае придется перемещать все элементы массива на одну ячейку вперед при выполнении операции dequeue. В силу этого для выполнения метода dequeue данная реализация потребует 0 (п) времени, где п — текущее значение количества объектов в очереди: Поэтому, если необходимо установить некоторое постоянное время выполнения каждого метода очереди, требуется найти другое решение.

Для того чтобы избежать перемещения объектов в Q, применим две переменные,/и г:

•          /является индексом ячейки Q, в которой хранится первый элемент очереди (кандидат на удаление при выполнении метода dequeue) при условии, что очередь не является пустой (в этом случае/= г).

•     г является индексом следующей доступной ячейки массива Q.

Изначально присваиваем f—r — 0, что означает пустую очередь. Теперь, после удаления элемента из начала очереди, просто увеличиваем значение /на 1 для получения индекса следующей ячейки массива. Если добавляем новый элемент, то увеличиваем значение г на 1 для получения индекса следующей доступной ячейки массива Q. Прй таком подходе можно выполнить методы enqueue и dequeue за фиксированный промежуток времени, равный 0(1). Тем не менее при этом возникают определенные проблемы.

Рассмотрим пример, когда многократно удаляется и добавляется единственный элемент N. В данном случае/= г= N. Попытка добавления этЬго элемента еще раз приведет к ошибке превышения пределов массива (так как допустимые значения N в Q находятся в интервале от Q[0] до Q[N- 1]), даже несмотря на наличие в очереди свободного места. Во избежание подобных проблем, а также для обеспечения возможности использования всего массива Q предположим, что индексы / и г «охватывают» конечные точки массива Q. В этом случае Q рассматривается как «круговой» массив, который продолжается от Q[0] до Q[N- 1], а затем снова возвращается к Q[0] (см. рис. 4.4).

Рис. 4.4. Представление массива в виде «окружности»: (а) обычная конфигурация, где / < г; (Ь) «круговая» конфигурация, где r<f. Ячейки, в которых хранятся элементы очереди, заштрихованы

Реализация подобного представления Q довольно проста. При каждом увеличении значения / и г на 1 необходимо записать эту операцию в виде «(/ + 1) mod N» или «(г + 1) mod TV» соответственно, где mod обозначает операцию деления по модулю, которая вычисляется путем получения остатка от деления, то есть у не равно 0:

В Java для обозначения операции деления по модулю используется знак «%». Используя эту операцию, можно рассматривать Q как круговой массив и реализовывать каждый метод очереди определенный период времени, равный 0(1). Таким образом, с помощью операции деления по модулю разрешается проблема превышения пределов массива, однако еще одна небольшая проблема остается.

Рассмотрим ситуацию добавления N новых объектов в Q, не удаляя ни один из них. В этом случае/= г, что является условием пустой очереди, то есть в данном случае невозможно определить различие между пустой и полной очередью. К счастью, существует целый ряд способов решения данной задачи. В предлагаемом авторами решении необходимо установить, что Q не может содержать более N— 1 объектов (в упражнениях предлагается к рассмотрению еще один способ решения этой задачи).

Теперь, после разработки простых правил работы с полной очередью и решения всех проблем реализации АТД, можно создать псевдокод методов очереди (фрагмент кода 4.9). Обратите внимание на особый тип исключения QueueFullException, который обрабатывает ситуацию невозможности добавления элементов в очередь. Кроме того, подчеркнем, что размер очереди вычисляется с помощью выражения (N —/ + г) mod N, которое позволяет получить правильный результат как в случае «нормальной» конфигурации, где /<г, так и при «круговой» конфигурации, где r<f. аналогична реализации стека и предлагается для решения в упражнениях.

Алгоритм size():

return (N – f+ r) mod N Алгоритм isEmpty():

return (f = r) Алгоритм front():

if isEmpty() then

вызов QueueEmptyException return Off] Алгоритм dequeue(): if isEmpty() then

вызов QueueEmptyException temp <- Q[f\ Oft null f <r- (f + 1) mod N return temp

Алгоритм enqueuе(о):

if size() = Л/ – 1 then

вызов QueueFullException ОИ о

г (г + 1) mod N

Фрагмент кода 4.9. Реализация очереди с помощью кругового массива. При этом применяется операция деления по модулю, что позволяет индексировать границы Массива, а также используются две переменные экземпляра класса (/иг), которые являются соответственно индексом начала очереди и индексом первой свободной ячейки за концом очереди

В табл. 4.1 показано время выполнения методов при реализации очереди с помощью массива. Каждый из методов очереди, реализованной на основе массива, выполняет определенное число операций, в том числе арифметические операции-, операции сравнения и операции присваивания.. Таким образом, при данной реализации время выполнения каждого метода есть 0(1).

Метод

Время

size

0(1)

isEmpty

0(1)

front

0(1)

enqueue

0(1)

dequeue

0(1)

Таблица 4.1. Выполнение очереди, реализованной на основе массива. Размер используемого пространства составляет 0(N), где N — длина массива, определенная на этапе создания очереди. Обратите внимание, что размер используемого пространства не зависит от числа п < N элементов, содержащихся в очереди

Как и в случае реализации стека на основе массива, единственным недостатком подобной же реализации очереди является необходимость искусственно устанавливать ее размер N. В ходе выполнения программы может потребоваться разный объем памяти. Однако при возможности точно определить число элементов, которые одновременно находятся в очереди, реализация очереди на основе массива вполне эффективна. Один из возможных способов применения очереди в Java — процесс динамического распределения памяти.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии