Обратная очередь в O (1) сложности пространства

Question

Как можно повернуть очередь в O (1) сложности пространства?

Ответ здесь: Можно ли перевернуть очередь без использования стека? говорит, что это возможно со стеком. Но я не понимаю, как этот процесс представляет собой O (1) сложность пространства:

Шаг 1: поместите в очередь, а затем удалите все элементы очереди в стек

Шаг 2: Поставьте в очередь значение Front стека в очередь, затем вытолкните каждый элемент стека

Разве в стеке не будет использоваться O (n) сложность пространства для каждого элемента в очереди?

Answer 1

Когда вы добавляете элемент в стек, вы удаляете его из очереди. Сумма размера очереди и размера стека не изменяется, поэтому общий объем используемой памяти остается неизменным. Вот почему он занимает O (1) пробел.