Полное/пустое различие буфера в круговой очереди

Question

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

Для решения этой проблемы мы используем либо счетчик, либо пустое место в буфере.

Я думал о следующем подходе. Пожалуйста, поправьте меня, где я ошибаюсь, и если не сообщите мне, если это лучшее/худшее решение, чем выше.

1) Направьте фронт первого элемента & сзади к последнему элементу 2) имеют функцию, чтобы проверить, если очередь имеет левый 3) Если мы dequeing последний элемент, сделать только один элемент спереди и сзади - 1. 4) IsEmpty() будет справедливо, если оба передних & сзади находятся -1 5) isFull будет справедливо, если передняя = (задний + 1)% размер

Answer 1

Существует не так много плохого логически с этим подходом. Вы обрабатываете отрицательные значения в front и rear как вид флага, указывающий, что очередь пуста. Предполагая, что ваша логика для обновления front и rear сохраняет значения в диапазоне 0 .. size, вам нужно только установить один из них вне этого диапазона, чтобы указать, что очередь пуста.

Рассмотрите эту альтернативу. Многие круговые очереди работают с индексами front и rear как неподписанные значения, а size - как сила 2. Обновление их значений всегда увеличивается, и им разрешается обтекать. Это позволяет избежать сложной логики для корректировки этих индексов. Поскольку индексы без знака, даже если они обертываются, арифметика разностей работает правильно, чтобы определить количество элементов.

Трюк с модулем, работающим, даже если индексы обертываются при приращении, состоит в том, что size - это сила 2. Это гарантирует, что обертка вокруг не влияет на вычисление модуля.

unsigned front_ = 0, rear_ = 0; 
Type q_[SIZE]; 

unsigned getCount() { return rear_ - front_; } 
bool isEmpty() { return getCount() == 0; } 
bool isFull() { return getCount() == SIZE; } 
bool enQ (Type val) { 
    bool result = !isFull(); 
    if (result) q_[rear_++ % SIZE] = val; 
    return result; 
} 
bool deQ (Type *val) { 
    bool result = !isEmpty(); 
    if (result) *val = q_[front_++ % SIZE]; 
    return result; 
}