Кольцевая полустатическая очередь. Операции над кольцевой очередью. Деки, операции над ними.

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

Предположим, что очередь содержит три элемента - в позициях 3, 4 и 5 пятиэлементного массива. Хотя массив и не заполнен, последний элемент очереди занят.

Если теперь делается попытка поместить в очередь элемент G, то он будет записан в первую позицию массива. Первый элемент очереди есть q(3), за которым следуют элементы q (4), q(5) и q(1).

К сожалению, условие R<F больше не годится для проверки очереди на пустоту.

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

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

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

Поскольку R = F, то очередь изначально пуста.

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

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

2. Извлечение элемента из очереди x
Remove(q);

3. Проверка очереди на пустоту
Empty(q);

4. Проверка очереди на переполнение
Full(q).

Операция Empty(q)

if F = R

then empty = true

else empty = false

endif

return

 

Операция Remove(q)

empty (q)

if empty = true

then “пусто”

stop

endif

if F = maxQ

then F =1

else F = F+1

endif

x = q(F)

return

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

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

Исходное состояние очереди

Поместим в очередь элемент G.

Если произвести следующую вставку, то массив становится целиком заполненным, и попытка произвести еще одну вставку приводит к переполнению. Это регистрируется тем фактом, что F = R, то есть это соотношение как раз и указывает на переполнение. Очевидно, что при такой реализации нет возможности сделать различие между пустой и заполненной очередью.

Одно из решений состоит в том, чтобы пожертвовать одним элементом массива и позволить очереди расти до объема, на единицу меньшего максимального. Предыдущий рисунок иллюстрирует именно это соглашение. Попытка разместить в очереди еще один элемент приведет к переполнению. Проверка на переполнение в функции insert производится после установления нового значения для R, в то время как проверка на потерю значимости в функции remove производится сразу же после входа в подпрограмму до момента обновления значения F.

Функция Insert(q,x) может быть записана следующим образом:

if R = maxQ

then R = 1

else R = R+1

endif

‘проверка на переполнение’

if R = F

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

stop

endif

q (R) =x

return

 

Деки

Происхождение слова от английского DEQ - Double Ended Queue (очередь с двумя концами).

Дек можно рассматривать как два стека, соединенных нижними границами.

Операции над деками:

Insert(d, x) - вставка элемента.

Remove(d) - извлечение элемента из дека.

Empty(d) - проверка на пустоту.

Full(d) - проверка на переполнение.