Как реализовать FIFO с использованием стека (LIFO) с равными сложностями для операций push и pop в FIFO

Question

Я понял традиционный способ сделать либо операцию Push, либо операцию pop.

Как сделать push и pop одинаковой сложности?

Answer 1

Это стандартный вопрос интервью. Общая идея: минус х минус = плюс. Вы используете 2 последовательных стека:

• PUT развертывает данные в стек 1.
• GET извлекает данные из стека 2.
• Если stack2 пуст - скопируйте все существующие данные из стека 1 в стек 2, элемент за элементом, сверху 1 вверх 2.