Здравствуйте, TailWind, Вы писали:

TW>Это связный список или он на основе вектора

В основе std::queue может лежать любой контейнер, удовлетворяющий требованиям SequenceContainer и имеющий функции-члены front, back, push_back, pop_front. Из стандартных контейнеров под эти требования подходят std::list и std::deque. По умолчанию используется std::deque, но она может быть заменена по желанию любым подходящим по требованиям контейнером, в т.ч. и самописным. (А самописный, в свою очередь, может быть реализован поверх какого-то из стандарных). Короче говоря, варианты есть.

TW>Вопрос: когда добавляю или удаляю элемент в queue, остальные элементы лежат на месте или копируются?

А это как раз и зависит от того, какой используется underlying container. Когда по умолчанию используется std::deque, то при добавлении (но не при удалении) элемента могут происходить релокации и элементы очереди могут перемещаться или копироваться, все итераторы инвалидируются (подробнее здесь: std::deque::push_back). Но можно вместо std::deque использовать std::list, тогда все элементы будут лежать на месте и итераторы не будут инвалидироваться.