отделить четное нечетное число с помощью двух стеков

Question

У меня есть два стека. Один стек пуст, а другой - список чисел. Нам нужно разделить четные нечетные числа таким образом, чтобы один стек содержал четные числа, а другой - только нечетные. Я не могу найти какое-либо оптимальное решение с O (n) или O (nlogn) - сложность времени и O (1) - сложность пространства. Пожалуйста помоги.

Answer 1

Квадрати c подход. Пусть стек A содержит значения, B пусто.

Псевдокод:

while not A.Empty:
   x = A.Pop
   if IsOdd(x):
       while not B.Empty and IsEven(B.Peek):
           A.Push(B.Pop)
   B.Push(x)
while not B.Empty and IsEven(B.Peek):
    A.Push(B.Pop)

Теперь A содержит четные элементы, B содержит нечетные.