Membalik daftar menggunakan dua antrian

Pertanyaan ini terinspirasi oleh pertanyaan yang ada tentang apakah stack dapat disimulasikan menggunakan dua antrian dalam waktu diamortisasi per operasi stack. Jawabannya sepertinya tidak diketahui. Berikut adalah pertanyaan yang lebih spesifik, terkait dengan kasus khusus di mana semua operasi PUSH dilakukan terlebih dahulu, diikuti oleh semua operasi POP. Seberapa efisien daftar elemen dapat dibalik menggunakan dua antrian yang awalnya kosong? Operasi hukum adalah:$O(1)$$N$

1. Enqueue elemen berikutnya dari daftar input (ke ujung salah satu antrian).
2. Dequeue elemen di kepala antrian baik dan enqueue lagi (ke ekor antrian baik).
3. Dequeue elemen di kepala salah satu antrian dan tambahkan ke daftar output.

Jika daftar input terdiri dari elemen , bagaimana jumlah minimum operasi yang diperlukan untuk menghasilkan daftar output terbalik berperilaku? Sebuah bukti bahwa itu tumbuh lebih cepat daripada akan sangat menarik, karena itu akan menyelesaikan pertanyaan aslinya dalam negatif.[ N , N - 1 , . . . , 2 , 1 ] O ( N $[1,2,...,N-1,N]$$[N,N-1,...,2,1]$$O(N)$

Pembaruan (15 Jan 2011): Masalahnya dapat diselesaikan di , seperti yang ditunjukkan dalam jawaban yang diajukan dan komentar mereka; dan batas bawah sepele. Bisakah salah satu dari batasan ini diperbaiki?Ω ( N $O(N \log N)$$\Omega(N)$

Jika N adalah kekuatan dua, saya percaya operasi O (N log N) sudah cukup, bahkan untuk masalah yang agak lebih terbatas di mana semua item dimulai pada salah satu antrian dan harus berakhir dalam urutan terbalik pada salah satu antrian (tanpa daftar input dan output).

Dalam langkah-langkah O (N) dimungkinkan untuk memulai dengan semua elemen pada satu antrian, bermain "satu untukmu satu untukku" untuk membaginya menjadi subset bergantian pada antrian lainnya, dan kemudian menggabungkan semuanya kembali menjadi satu antrian. Dalam hal representasi biner dari posisi item, ini mengimplementasikan operasi rotasi.

Dalam langkah-langkah O (N) juga dimungkinkan untuk menarik pasangan elemen dari satu antrian, menukar mereka, lalu memasangnya kembali, membalikkan semua pasangan. Dalam hal representasi biner dari posisi item, ini melengkapi bit order posisi rendah.

Dengan mengulangi O (log N) kali unshuffle dan swap berpasangan, kita dapat melengkapi semua bit dari representasi biner dari posisi - yang sama dengan membalikkan daftar.

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

Beri nama dua antrian yang tersedia sebagai kiri dan kanan. Berikut adalah ide dasar dari algoritma ini dengan asumsi bahwa N adalah genap:

1. Baca nilai dari daftar awal elemen dan dorong semua angka ganjil ke antrian kiri dan bahkan angka ke antrian kanan
2. Salah satu langkah pertama cara tercepat untuk menghasilkan nilai maksimum adalah dengan mentransfer elemen N / 2-1 dari antrian kanan ke antrian kiri dan memasukkan nilai teratas dari antrian kanan ke daftar keluaran
3. Sekarang kita harus melakukan hal yang sama untuk antrian lain - mentransfer elemen N / 2-1 dari antrian kiri ke antrian kanan dan memasukkan elemen atas dari antrian kiri ke daftar output
4. Tukar antrian dan ulangi langkah 2 dan 3 untuk N = N-2

Sangat mudah untuk melihat bagaimana algoritma seharusnya bekerja untuk N. aneh