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

Входные данные: Последовательность запросов 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