реализация очереди с использованием кругового массива

Question

Я нашел эти алгоритмы в интернете, но не могу понять, почему в методе enqueue мы сравниваем размер с N-1 ???пожалуйста, помогите мне спасибо !!

Algorithm size():
return (N-f+r)mod N



Algorithm enqueue(e):
if size()=N-1 then
   throw a FullQueueException
Q[r]<---e
r<----(r+1)mod N

Answer 1

Причина, по которой очередь заполнена при размере N-1, заключается в том, что в этой простой реализации 'r' представляет индекс следующего свободного элемента, а 'f' представляет следующий элемент для извлечения. Если «f» и «r» равны, очередь пуста, поэтому очередь заполнена, если при увеличении «r» она будет равна «f».

В этой реализации хотя бы один элемент всегда пуст. Это обычно более эффективно, чем добавление дополнительной логики, чтобы дифференцировать случай, когда 'f' и 'r' равны, и очередь заполнена по сравнению со случаем, когда она пуста.

Кстати, в большинстве процессоров функция мода намного дороже, чем при использовании такой логики:

Algorithm enqueue(e):
rNext<---r + 1
if rNext = N
    rNext<---0
if rNext = r then
    throw a FullQueueException
r<---rNext
Q[r]<---e

Answer 2

Я согласен с комментарием @Matthew Flaschen, но я сделаю предположение. Я подозреваю, что очередь N длинная, и один элемент зарезервирован для дозорного для поиска. Но я бы так не поступил.

Answer 3

Учитывая реализацию циклических очередей, в которых начало и конец хранятся как индикаторы по модулю размера выделенного базового массива, скажем N, необходимо, чтобы фактическая емкость очереди (не массива) была меньше N в противном случае показатели начала и конца будут равны, и между пустым и полным будет двусмысленность.

Таким образом, когда выделенный базовый массив имеет размер N, истинная емкость очереди равна N-1. Вот почему теста.

Существуют способы обойти это, которые фактически позволяют использовать все N слотов И устраняют неявное деление при взятии индекса по модулю n.

Answer 4

Вы предоставили очень неправильную (и неправильную) реализацию.

При этом круговая очередь в массиве обычно начинается с данного индекса и заканчивается другим данным индексом (таким образом, f и r). Однако, что бы вы ни делали, в очереди не может быть больше элементов, чем в базовом массиве.

Предполагается, что функция size рассчитывает количество элементов в очереди. Если число становится опасно близким к общему размеру массива, то очередь заполнена.