#data-structures #queue
Вопрос:
Предположим, у нас есть круговая очередь. Более того, давайте также скажем, что он основан на массиве. У нас был бы передний индекс, задний индекс и размер. Однако, когда дается следующее уравнение для поиска заднего индекса, я довольно запутываюсь: rear_index = (rear_index 1) % arraySize; Может ли кто-нибудь, пожалуйста, объяснить мне, что именно происходит? Как это может работать для постановки в очередь?
Комментарии:
1. Пожалуйста, предоставьте достаточно кода, чтобы другие могли лучше понять или воспроизвести проблему.
Ответ №1:
Читайте об операции по модулю. Оператор % возвращает остаток после деления. Например, 10% 7 == 3 (7 делится на 10 один раз, осталось 3), 10 % 3 == 1 (3 делится на 10 3-кратный остаток 1) и т. Д.
Если size == 10 и rear_index == 9 (последний элемент в массиве), rear_index = (rear_index 1) % 10; присваивает rear_index = (9 1) % 10; // == 0 . rear_index имеет «петлю» от 9 до 0, следующее увеличение будет 1, затем 2, затем…9,0,1,2…
При реализации очереди с использованием циклического буфера (часто также называемого «кольцевым буфером») таким образом увеличиваются как начальный, так и конечный индексы, и код применяет правила, аналогичные следующим (комментарий из моего собственного старого кода)…
/* _head (presumably front_index) => index of oldest entry (next to be returned)
* _tail (presumably rear_index) => index of next entry to be inserted
* _head == _tail amp;amp; queue[tail] != null => queue full
* _head == _tail amp;amp; queue[tail] == null => queue empty