Двусторонняя очередь.(Дек)

Question

Изучаю структуры данных и попалась мне статья под названием Deque Data Structure.
В данной статье приложена реализация дека и теория.
Я ,в основном ,пишу на плюсах и в не понятен один момент, а именно функция getRear();

int Deque::getRear() {
  if (isEmpty() || rear < 0) {
    cout << " Deque is Empty"<< endl;
    return -1;
  }
  return *(arr+rear);
}

И в чем же, собственно, вопрос!?
1.Не понимаю почему в данной функции при проверке на пустоту, приписывается rear<0.Можно ли без него?
В принципе, приблизительно ,я понимаю почему так, но если посмотреть с другой стороны, почему бы не приписать в конструкторе сразу rear=-1,а не 0?
Могу еще сослаться на функцию DeleteRear();,где при удалении последнего элемента,rear=-1 и front=-1. Но я путаюсь, порой, в своих суждениях, лучше послушать мнения других.

Answer 1

Не понимаю почему в данной функции при проверке на пустоту, приписывается rear<0.Можно ли без него?

Вопрос || rear < 0 невыполним, так как если он не пустой, то индекс rear всегда >=0. Это часто встречается, как избыток контроля. Значение rear == -1 встречается только в состоянии пустой очереди. То-есть спокойно можно удалить эту проверку, так как она не изменит логику.

if (isEmpty() || rear < 0)
 // v
if (isEmpty())

почему бы не приписать в конструкторе сразу rear=-1,а не 0?

Флаг пустоты играет только проверка индекса front == -1. Значение rear может быть неопределено. И в конструкторе прописали значение rear = 0 просто-так. Это присвоение не меняет логику программы.

Как сказал avp, неудачно выбран комплект переменных. Так как пустую очередь невозможно определить с индексами из области [0 .. size-1]. Придумали первому индексу ключевое значение -1, что не очень сказывается на читаемость и исполняемость программы.

Удобнее было-бы использовать индекс первого и количество. Проверка на пустоту была-бы count == 0, а индекс последней записи могла бы быть вычислена так : rear = (front + count - 1) % size ;

БЛОГ НА HUSL

Двусторонняя очередь.(Дек)

Ответы (1 шт):