Есть ли лучший алгоритм, чем смещение элементов влево в реализации очереди ниже массива

Question

Я пытаюсь придумать дизайн, который реализует блокирующую очередь массивов в C ++, похожую на Java.Я заметил, что если я всегда буду держать фронт всегда в нулевом индексе массива, то мне придется сместить элементы с индекса 1 на тыловой влево в массиве [дорогостоящая операция], чтобы освободить место для очереди для вставки снова всзади.

Существует ли лучшая реализация для этого?Я видел, как у некоторых людей есть видео на YouTube, где реализация заключается в том, чтобы продолжать перемещать передний указатель очереди, пока элементы не работают.но тогда как вы освободите место для вставки при выходе из очереди, когда она заполнится до отказа?

Укажите, есть ли еще какие-то неясные вопросы.Я пытаюсь определить, есть ли лучший способ, чем сдвиг элементов влево, который кажется неизбежным, но неэффективным.

Answer 1

Оптимальный способ для производственного кода - использовать std :: deque.

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

Когда вы ставите в очередь и вам нужно дополнительное пространство, вам нужно перераспределить больший буфер.Если вы сделаете это, удвоив размер, в среднем вы будете нести постоянные затраты (это называется линейной амортизацией).