Хорошо ли оставлять одну пустую в массиве реализацию циклической очереди? - PullRequest
0 голосов
/ 27 июня 2019

В чем разница между тем, чтобы оставить пустыми данные, а не в реализации массива циклической очереди? Не будет ли эффективнее использовать все реализованные мероприятия? Я не знаю, почему оставить одно поле данных пустым считается эффективным.

1 Ответ

0 голосов
/ 28 июня 2019

Две причины.

Во-первых, если этот элемент имеет значение, то ваша очередь всегда заполнена. Это, вероятно, должно быть больше. Кроме того, если ваша очередь даже среднего размера, например, 1000 элементов, один элемент представляет 0,1% вашей очереди. Не то, что я бы назвал особенно бесполезной тратой памяти.

Что еще более важно, если вы не оставляете лишний элемент, то реализация становится проблемой. Если у вас есть индексы head и tail, то что это значит, когда head == tail? Значит ли это, что очередь заполнена или пуста? Без дополнительной информации невозможно сказать.

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

Так вы хотите тратить циклы процессора на каждую операцию очереди? Или вы бы предпочли «потратить» тривиальный объем памяти, чтобы сделать ваш код проще?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...