Структуры и алгоритмы обработки данных


Очередь - часть 4


В этом случае, поскольку R содержит индекс последнего элемента очереди, условие F = R подразумевает, что очередь пуста.

Отметим, что перед началом работы с очередью, в F и R устанавливается значение последнего индекса массива, а не 0 и 1, поскольку при таком представлении очереди последний элемент массива немедлен­но предшествует первому элементу. Поскольку R = F, то очередь изначально пуста.

Основные операции с кольцевой очередью:

1. Вставка элемента q в очередь x.

Insert(q,x)

2. Извлечение элемента из очереди x.

Remove(q)

3. Проверка очереди на пустоту.

Empty(q)

Операция empty (q) может быть записана следующим образом:

if F = R

then empty = true

else empty = false

endif

return

Операция remove (q) может быть записана следующим образом:

empty (q)

if empty = true

then print «выборка из пустой очереди»

stop

endif

if F =maxQ

then F =1

else F = F+1

endif

x = q(F)

return

 

Отметим, что значение F должно быть модифицировано до момента извлечения элемента.

Операция вставки insert (q,x).

Для того чтобы запрограммировать операцию вставки, должна быть проанализирована ситуация, при которой возникает переполнение. Переполнение происходит в том случае, если весь массив уже занят элементами очереди и при этом делается попытка разместить в ней еще один элемент. Рассмотрим, например, очередь на рис. 2. 17. В ней находятся три элемента — С, D и Е, соответственно расположенные в Q (3), Q (4) и Q (5). Поскольку последний элемент в очереди занимает позицию Q (5), значение R равно 5. Так как первый элемент в очереди находится в Q (3), значение F равно 2. На рис. 2. 17 в очередь помещается элемент G, что приводит к соответствующему изменению значения R. Если произвести следующую вставку, то массив становится целиком заполненным, и попытка произвести еще одну вставку приводит к переполнению. Это регистрируется тем фактом, что F = R, а это как раз и указывает на переполнение. Очевидно, что при такой реализации нет возможности сделать различие между пустой и заполненной очередью Разумеется, такая ситуация удовлетворить нас не может

Одно из решений состоит в том, чтобы пожертвовать одним элементом массива и позволить очереди расти до объема на единицу меньшего максимального. Так, если  массив из 100 элементов объявлен как очередь, то очередь может содержать до 99 элементов. Попытка разместить в очереди 100-й элемент приведет к переполнению. Подпрограмма insert может быть записана следующим образом:

if R = max(q)

then R = 1

else R = R+1

endif

'проверка на переполнение

if R = F

then print «переполнение очереди»

stop

        endif

q (r) =x

return

 

Проверка на переполнение в подпрограмме insert производится после установления нового значения для R, в то время как проверка на потерю значимости в подпрограмме remove производится сразу же после входа в подпрограмму до момента обновления значения F.




- Начало -  - Назад -  - Вперед -



Книжный магазин