Очередь на двух стеках

Очередь на двух стеках
Входные данные: Последовательность запросов popFront(), pushBack(), max().
Выходные данные: Для каждого запроса max() выводить максимальный элемент, а для каждого запроса popFront() выводить элемент из начала очереди.
Подробное условие задачи.
Заведём два стека: s1 и s2; разумеется, имеются в виду стеки с поддержкой минимума (максимума). Добавлять новые элементы будем всегда в стек s1, а извлекать элементы - только из стека s2. При этом, если при попытке извлечения элемента из стека s2 он оказался пустым, просто перенесём все элементы из стека s1 в стек s2 (при этом элементы в стеке s2 получатся уже в обратном порядке, что нам и нужно для извлечения элементов; стек s1 же станет пустым). Наконец, нахождение минимума в очереди будет фактически заключаться в нахождении минимума из минимума в стеке s1 и минимума в стеке s2.
Тем самым, мы выполняем все операции по-прежнему за O (1) (по той простой причине, что каждый элемент в худшем случае 1 раз добавляется в стек s1, 1 раз переносится в стек s2 и 1 раз извлекается из стека s2).

Примеры.
Входные данные
3
pushBack 1
pushBack 7
popFront
Выходные данные
1
Входные данные
5
pushBack 4
pushBack 35
max
popFront
max
Выходные данные
35
35
35

0