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

Question

Я изучаю структуры данных из "Основы структур данных в C" Сахни. В теме «Круговая очередь с использованием динамического массива» автор упомянул ниже пункт

Пусть Capacity будет начальной емкостью круговой очереди. Мы должны сначала увеличьте размер массива с помощью realloc, это скопирует максимальная емкость элементов на новый массив. Чтобы получить правильный Круговая конфигурация очереди, мы должны сдвинуть элементы справа сегмент (то есть элементы A и B) к правому концу массива (см. диаграмма 3.7.d). Массив удваивается и сдвигается вправо вместе максимум копировать 2 * емкость -2 элемента .

Я понимаю копии удвоения массива на большинстве элементов емкости. Но как получается удвоение массива и скольжение к правой копии максимум 2 * емкость -2 элемента ??

Answer 1

Попробуем обосновать наихудший сценарий:

Для очереди с capacity = N в очереди присутствует максимум N-1 elements.

Итаккогда мы удваиваем размер очереди, нам нужно скопировать все эти N-1 элементы в новую очередь, и при максимуме может быть N-1 сдвигов (для элементов).

Таким образом, всего 2 * (N-1) = 2 * N-2