Сторнирование списка с использованием двух очередей

Этот вопрос основан на существующем вопросе о том, можно ли моделировать стек с использованием двух очередей с амортизированным раз на операцию стека. Ответ кажется неизвестным. Вот более конкретный вопрос, соответствующий особому случаю, когда сначала выполняются все операции PUSH, а затем все операции POP. Насколько эффективно можно изменить список из N элементов, используя две изначально пустые очереди? Юридические операции:$O(1)$$N$

1. Поставьте в очередь следующий элемент из списка ввода (в конец любой очереди).
2. Удалите элемент из заголовка любой из очередей и поставьте его снова (в конец любой очереди).
3. Удалите элемент из заголовка любой очереди и добавьте его в список вывода.

Если список ввода состоит из элементов , как делает минимальное количество операций , необходимым для генерации списка перевернутого выходного [ N , N - 1 , . , , , 2 , 1 ] вести себя? Доказательство того, что он растет быстрее, чем O ( N ), было бы особенно интересно, так как это решило бы исходный вопрос в отрицательной форме.$[1,2,...,N-1,N]$$[N,N-1,...,2,1]$$O(N)$

Обновление (15 января 2011 г.): проблема может быть решена в , как показано в представленных ответах и ​​их комментариях; и нижняя оценка Ω ( N ) тривиальна. Можно ли улучшить эти границы?$O(N \log N)$$\Omega(N)$

Если N является степенью двойки, я полагаю, что операций O (N log N) достаточно даже для несколько более ограниченной проблемы, когда все элементы начинаются в одной из очередей и должны заканчиваться в обратном порядке в одной из очередей (без списки ввода и вывода).

В O (N) шагах можно начать со всех элементов в одной очереди, сыграть «один для вас, один для меня», чтобы разбить их на чередующиеся подмножества в другой очереди, а затем объединить их все обратно в одну очередь. С точки зрения двоичных представлений положений элементов, это реализует операцию поворота.

В O (N) шагах также можно извлечь пары элементов из одной очереди, поменять их местами, затем вернуть обратно, переворачивая все пары. В терминах двоичных представлений позиций элементов это дополняет младший бит позиции.

Повторяя O (log N) раз в случайном порядке и попарно меняем местами, мы можем дополнить все биты двоичных представлений позиций - это то же самое, что инвертировать список.

$\sum_{i=0}^{N/2-1}(N-2i-2)$

Позволяет назвать две доступные очереди слева и справа. Вот основная идея этого алгоритма с предположением, что N четно:

1. Считать значения из начального списка элементов и поместить все нечетные числа в левую очередь, а четные - в правую.
2. На первом этапе самый быстрый способ вывести максимальное значение - это перенести N / 2-1 элементов из правой очереди в левую и вытолкнуть верхнее значение из правой очереди в список вывода.
3. Теперь мы должны сделать то же самое для другой очереди - перенести элементы N / 2-1 из левой очереди в правую и вытолкнуть верхний элемент из левой очереди в список вывода.
4. Поменяйте местами очереди и повторите шаги 2 и 3 для N = N-2

Легко понять, как алгоритм должен работать для нечетных N.