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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

Причина, по которой очередь заполнена, когда размер 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