Очередь с помощью двух стеков

Реализовать очередь с помощью двух стеков

Главное отличие очереди от стека — FIFO против LIFO (магические аббревиатуры, которые я вечно путаю :-). По методу FIFO первым выдаётся самый старый из пришедших элементов, по методу LIFO — самый новый.

FIFO — очередь, а LIFO — стек.

Вопрос в том, как обновлять второй стек при добавлении элементов? Можно копировать все элементы из первого стека во второй каждый раз при добавлении элемента, но здесь есть лишняя работа: лучше реализовать «отложенный» подход. Второй стек нужен только при попытке получить элемент — тогда и надо инвертировать первый стек.


Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.