Satu Tumpukan, Dua Antrian

Latar Belakang

Beberapa tahun yang lalu, ketika saya masih sarjana, kami diberi pekerjaan rumah tentang analisis diamortisasi. Saya tidak dapat menyelesaikan salah satu masalah. Saya telah menanyakannya dalam teori comp.the , tetapi tidak ada hasil yang memuaskan muncul. Saya ingat kursus TA bersikeras pada sesuatu yang tidak bisa dia buktikan, dan mengatakan dia lupa buktinya, dan ... [Anda tahu apa].

Hari ini, saya mengingat masalahnya. Saya masih ingin tahu, jadi ini dia ...

Pertanyaan

Apakah mungkin untuk mengimplementasikan stack menggunakan dua antrian , sehingga operasi PUSH dan POP berjalan dalam waktu diamortisasi O (1) ? Jika ya, bisakah Anda memberi tahu saya caranya?

Catatan: Situasinya cukup mudah jika kita ingin mengimplementasikan antrian dengan dua tumpukan (dengan operasi yang sesuai ENQUEUE & DEQUEUE ). Mohon perhatikan perbedaannya.

PS: Masalah di atas bukan pekerjaan rumah itu sendiri. Pekerjaan rumah tidak membutuhkan batas bawah; hanya implementasi dan analisis waktu berjalan.

Saya tidak memiliki jawaban yang sebenarnya, tetapi inilah beberapa bukti bahwa masalahnya terbuka:

• Ini tidak disebutkan dalam Ming Li, Luc Longpré dan Paul MB Vitányi, "Kekuatan antrian", Structures 1986, yang mempertimbangkan beberapa simulasi terkait erat lainnya

• Tidak disebutkan dalam Martin Huhne, "Pada kekuatan beberapa antrian", Theor. Comp. Sci. 1993, makalah lanjutan.

• Tidak disebutkan dalam Holger Petersen, "Stacks versus Deques", COCOON 2001.

• Burton Rosenberg, "Pengakuan cepat nondeterministik bahasa bebas konteks menggunakan dua antrian", Inform. Proc Lett. 1998, memberikan O (n log n) algoritma dua-antrian untuk mengenali CFL menggunakan dua antrian. Tetapi automaton pushdown nondeterministic dapat mengenali CFL dalam waktu linier. Jadi, jika ada simulasi tumpukan dengan dua antrian lebih cepat dari O (log n) per operasi, Rosenberg dan wasitnya seharusnya tahu tentang hal itu.

Jawaban di bawah ini adalah 'curang', karena walaupun tidak menggunakan ruang antara operasi, operasi itu sendiri dapat menggunakan lebih dari ruang. Lihat tempat lain di utas ini untuk jawaban yang tidak memiliki masalah ini.$O(1)$

Meskipun saya tidak punya jawaban untuk pertanyaan Anda, saya menemukan sebuah algoritma yang berfungsi di waktu alih-alihO(n). Saya percaya ini ketat, meskipun saya tidak punya bukti. Jika ada, algoritme menunjukkan bahwa mencoba membuktikan batas bawahO(n)adalah sia-sia, sehingga mungkin membantu dalam menjawab pertanyaan Anda.$O(\sqrt{n})$$O(n)$$O(n)$

Saya menyajikan dua algoritma, yang pertama adalah algoritma sederhana dengan waktu berjalan untuk Pop dan yang kedua dengan O ( $O(n)$waktu berjalan untuk Pop. Saya menggambarkan yang pertama terutama karena kesederhanaannya sehingga yang kedua lebih mudah dimengerti.$O(\sqrt{n})$

Untuk memberikan rincian lebih lanjut: yang pertama tidak menggunakan ruang tambahan, memiliki kasus terburuk (dan diamortisasi) Push dan O ( n ) kasus terburuk (dan diamortisasi) Pop, tetapi perilaku kasus terburuk tidak selalu dipicu. Karena tidak menggunakan ruang tambahan di luar dua antrian, itu sedikit 'lebih baik' daripada solusi yang ditawarkan oleh Ross Snider.$O(1)$$O(n)$

Yang kedua menggunakan bidang bilangan bulat tunggal (jadi ruang ekstra), memiliki O ( 1 ) kasus terburuk (dan diamortisasi) Push dan O ( $O(1)$$O(1)$Pop diamortisasi. Karenanya waktu berjalan jauh lebih baik daripada pendekatan 'sederhana', namun ia menggunakan ruang ekstra.$O(\sqrt{n})$

Algoritma pertama

Kami memiliki dua antrian: antrian dan antrian s e c o n d . f i r s t akan menjadi 'push queue' kami, sementara s e c o n d akan menjadi antrian yang sudah ada di 'susun urutan'.$first$$second$$first$$second$

• Mendorong dilakukan dengan hanya memberikan parameter ke .$first$
• Popping dilakukan sebagai berikut. Jika kosong, kita hanya dequeue s e c o n d dan mengembalikan hasil. Kalau tidak, kita membalikkan f i r s t , menambahkan semua s e c o n d ke f i r s t dan bertukar f i r s t dan s e c o n d . Kami kemudian dequeue s e c $first$$second$$first$$second$$first$$first$$second$ dan mengembalikan hasil dari dequeue tersebut.$second$

Kode C # untuk algoritma pertama

Ini seharusnya cukup mudah dibaca, bahkan jika Anda belum pernah melihat C # sebelumnya. Jika Anda tidak tahu apa itu generik, cukup ganti semua contoh 'T' dengan 'string' di pikiran Anda, untuk setumpuk string.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            // Reverse first
            for (int i = 0; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();    
            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            // Append second to first
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());

            // Swap first and second
            Queue<T> temp = first; first = second; second = temp;

            return second.Dequeue();
        }
    }
}

Analisis

Jelas Push bekerja dalam waktu. Pop dapat menyentuh segala sesuatu di dalam f i r s t dan s e c o n d jumlah konstan kali, jadi kita harus O ( n ) dalam kasus terburuk. Algoritme menunjukkan perilaku ini (misalnya) jika seseorang mendorong n elemen ke stack dan kemudian berulang kali melakukan Push menghanguskan dan operasi Pop tunggal berturut-turut.$O(1)$$first$$second$$O(n)$$n$

Algoritma kedua

Kami memiliki dua antrian: antrian dan antrian s e c o n d . f i r s t akan menjadi 'push queue' kami, sementara s e c o n d akan menjadi antrian yang sudah ada di 'susun urutan'.$first$$second$$first$$second$

Ini adalah versi adaptasi dari algoritma pertama, di mana kita tidak langsung 'mengacak' isi dari menjadi s e c o n $first$$second$ . Sebaliknya, jika berisi sejumlah cukup kecil elemen dibandingkan dengan s e c o n d (yaitu akar kuadrat dari jumlah elemen di s e c o n d ), kita hanya menata f i r s t ke dalam susunan tumpukan dan jangan bergabung dengan$first$$second$$second$$first$ .$second$

• Mendorong masih dilakukan dengan hanya memberikan parameter ke .$first$
• Popping dilakukan sebagai berikut. Jika $first$ kosong, kita hanya dequeue dan mengembalikan hasil. Jika tidak, kami reorganisasi isi f i r s t sehingga mereka berada di urutan stack. Jika | f i r s t | < $second$$first$kita hanya dequeuefirstdan mengembalikan hasilnya. Kalau tidak, kita menambahkansecondkefirst, bertukarfirstdansecond, dequeueseconddan mengembalikan hasilnya.$|first| < \sqrt{|second|}$$first$$second$$first$$first$$second$$second$

Kode C # untuk algoritma pertama

Ini seharusnya cukup mudah dibaca, bahkan jika Anda belum pernah melihat C # sebelumnya. Jika Anda tidak tahu apa itu generik, cukup ganti semua contoh 'T' dengan 'string' di pikiran Anda, untuk setumpuk string.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    int unsortedPart = 0;
    public void Push(T value) {
        unsortedPart++;
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            for (int i = nrOfItemsInFirst - unsortedPart - 1; i >= 0; i--)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - unsortedPart; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            unsortedPart = 0;
            if (first.Count * first.Count < second.Count)
                return first.Dequeue();
            else {
                while (second.Count > 0)
                    first.Enqueue(second.Dequeue());

                Queue<T> temp = first; first = second; second = temp;

                return second.Dequeue();
            }
        }
    }
}

Analisis

Jelas Push bekerja dalam waktu.$O(1)$

Pop bekerja di waktu diamortisasi. Ada dua kasus: jika| first| <$O(\sqrt{n})$$|first| < \sqrt{|second|}$, Maka kita mengocok ke dalam urutan tumpukan di O ( | f i r s t | ) = O ( $first$waktu. Jika| first| ≥$O(|first|) = O(\sqrt{n})$, maka kita harus memiliki setidaknya$|first| \geq \sqrt{|second|}$ panggilan untuk Push. Karenanya, kami hanya dapat menemukan kasus ini setiap$\sqrt{n}$ panggilan ke Push dan Pop. Waktu berjalan aktual untuk kasus ini adalahO(n), jadi waktu diamortisasi adalahO($\sqrt{n}$$O(n)$.$O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$

Catatan akhir

Dimungkinkan untuk menghilangkan variabel tambahan dengan biaya membuat Pop an operasi, dengan memiliki Pop mereorganisasifirstdi setiap panggilan daripada harus push melakukan semua pekerjaan.$O(\sqrt{n})$$first$

Mengikuti beberapa komentar pada jawaban saya sebelumnya, menjadi jelas bagi saya bahwa saya kurang lebih curang: Saya menggunakan ruang ekstra ( ruang ekstra dalam algoritma kedua) selama pelaksanaan metode Pop saya.$O(\sqrt{n})$

Algoritme berikut tidak menggunakan ruang tambahan antara metode dan hanya ruang ekstra selama pelaksanaan Push dan Pop. Push memiliki O ( $O(1)$$O(\sqrt{n})$ waktu berjalan diamortisasi dan Pop memiliki waktu berjalan terburuk (dan diamortisasi).$O(1)$

Catatan untuk moderator: Saya tidak sepenuhnya yakin apakah keputusan saya untuk menjadikan ini jawaban terpisah adalah benar. Saya pikir saya tidak boleh menghapus jawaban asli saya karena mungkin masih ada relevansi dengan pertanyaan.

Algoritma

Kami memiliki dua antrian: antrian dan antrian s e c o n d . f i r s t akan menjadi 'cache' kami, sementara s e c o n d akan menjadi 'penyimpanan' utama kami. Kedua antrian akan selalu berada di 'susun urutan'. f i r s t akan berisi elemen-elemen di bagian atas tumpukan dan s e c o n d akan berisi elemen-elemen di bagian bawah tumpukan. Ukuran f i $first$$second$$first$$second$$first$$second$ akan selalu paling banyak menjadi akar kuadrat dari s e $first$ .$second$

• Dorong dilakukan dengan 'memasukkan' parameter pada awal antrian sebagai berikut: kita enqueue parameter ke , dan kemudian dequeue dan re-enqueue semua elemen lain di f i r s t . Dengan cara ini, parameter berakhir pada awal f $first$$first$ .$first$
• Jika menjadi lebih besar dari akar kuadrat dari s e c o n d , kita enqueue semua elemen s e c o n d ke f i r s t satu per satu dan kemudian bertukar f i r s t dan s e c o n d . Dengan cara ini, elemen f i r $first$$second$$second$$first$$first$$second$ (bagian atas tumpukan) berakhir di kepala s $first$ .$second$
• Pop dilakukan dengan dequeueing dan mengembalikan hasilnya jika f i r s t tidak kosong, dan sebaliknya dengan dequeueing s e c $first$$first$ dan mengembalikan hasilnya.$second$

Kode C # untuk algoritma pertama

Kode ini harus cukup mudah dibaca, bahkan jika Anda belum pernah melihat C # sebelumnya. Jika Anda tidak tahu apa itu generik, cukup ganti semua contoh 'T' dengan 'string' di pikiran Anda, untuk setumpuk string.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        // I'll explain what's happening in these comments. Assume we pushed
        // integers onto the stack in increasing order: ie, we pushed 1 first,
        // then 2, then 3 and so on.

        // Suppose our queues look like this:
        // first: in 5 6 out
        // second: in 1 2 3 4 out
        // Note they are both in stack order and first contains the top of
        // the stack.

        // Suppose value == 7:
        first.Enqueue(value);
        // first: in 7 5 6 out
        // second: in 1 2 3 4 out

        // We restore the stack order in first:
        for (int i = 0; i < first.Count - 1; i++)
            first.Enqueue(first.Dequeue());
        // first.Enqueue(first.Dequeue()); is executed twice for this example, the 
        // following happens:
        // first: in 6 7 5 out
        // second: in 1 2 3 4 out
        // first: in 5 6 7 out
        // second: in 1 2 3 4 out

        // first exeeded its capacity, so we merge first and second.
        if (first.Count * first.Count > second.Count) {
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());
            // first: in 4 5 6 7 out
            // second: in 1 2 3 out
            // first: in 3 4 5 6 7 out
            // second: in 1 2 out
            // first: in 2 3 4 5 6 7 out
            // second: in 1 out
            // first: in 1 2 3 4 5 6 7 out
            // second: in out

            Queue<T> temp = first; first = second; second = temp;
            // first: in out
            // second: in 1 2 3 4 5 6 7 out
        }
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else
            return first.Dequeue();
    }
}

Analisis

Jelas Pop bekerja di dalam kasus terburuk.$O(1)$

Push bekerja di waktu diamortisasi. Ada dua kasus: jika| first| $O(\sqrt{n})$lalu Push mengambilO$|first| < \sqrt{|second|}$waktu. Jika| first| ≥$O(\sqrt{n})$kemudian Push membutuhkanO(n)waktu, tetapi setelah operasi inifirstakan kosong. Itu akan membutuhkanO($|first| \geq \sqrt{|second|}$$O(n)$$first$waktu sebelum kita mendapatkan kasus ini lagi, jadi waktu diamortisasi adalahO($O(\sqrt{n})$waktu.$O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$

Saya mengklaim kami memiliki biaya perolehan diamortisasi per operasi. Algoritma Alex memberikan batas atas. Untuk membuktikan batas bawah saya berikan urutan terburuk dari gerakan PUSH dan POP.$\Theta(\sqrt{N})$

Urutan kasus terburuk terdiri dari operasi PUSH, diikuti oleh $N$ operasi PUSH dan$\sqrt{N}$ operasi POP, sekali lagi diikuti oleh$\sqrt{N}$ operasi PUSH dan$\sqrt{N}$ operasi POP, dll. Itu adalah:$\sqrt{N}$

$PUSH^N (PUSH^{\sqrt{N}} POP^{\sqrt{N}})^{\sqrt{N}}$

Pertimbangkan situasi setelah operasi PUSH awal . Tidak masalah bagaimana algoritme bekerja, setidaknya satu dari antrian harus memiliki setidaknya N / 2 entri di dalamnya.$N$$N/2$

Sekarang pertimbangkan tugas berurusan dengan (set pertama) $\sqrt{N}$ operasi PUSH dan POP. Taktik algoritmik apa pun harus jatuh ke dalam salah satu dari dua kasus:

Dalam kasus pertama, algoritme akan menggunakan kedua antrian. Semakin besar antrian ini memiliki setidaknya entri di dalamnya, jadi kita harus mengeluarkan biaya setidaknya N /$N/2$$N/2$ operasi antrian untuk akhirnya mengambil bahkan satu elemen yang kita ENQUEUE dan kemudian perlu DEQUEUE dari antrian yang lebih besar ini.

Dalam kasus kedua, algoritme tidak menggunakan kedua antrian. Ini mengurangi masalah untuk mensimulasikan tumpukan dengan antrian tunggal. Bahkan jika antrian ini pada awalnya kosong, kita tidak dapat melakukan lebih baik daripada menggunakan antrian sebagai daftar bundar dengan akses berurutan, dan tampaknya langsung bahwa kita harus menggunakan setidaknya operasi antrian rata-rata untuk masing-masing2$\sqrt{N}/2$Operasi N stack.$2\sqrt{N}$

Dalam kedua kasus, kami membutuhkan setidaknya waktu (operasi antrian) untuk menangani 2 $N/2$Operasi N stack. Karena kita dapat mengulangi proses ini$2\sqrt{N}$ kali, kita membutuhkanN$\sqrt{N}$waktu untuk memprosesoperasi stack3Nsecara total, memberikan batas bawahΩ($N\sqrt{N}/2$$3N$waktu diamortisasi per operasi.$\Omega(\sqrt{N})$

$O(\lg n)$$push$$pop$$pop$$O(\lg n)$$pop$ diminta dan antrian output kosong, Anda melakukan urutan shuffles sempurna untuk membalikkan antrian input dan menyimpannya dalam antrian output.

$O(1)$ memori.

Sejauh yang saya tahu, ini adalah ide baru ...

Tanpa menggunakan ruang ekstra, mungkin menggunakan antrian yang diprioritaskan dan memaksa setiap dorongan baru untuk memberikan prioritas yang lebih besar daripada yang sebelumnya? Tetap tidak akan menjadi O (1).

Saya tidak bisa mendapatkan antrian untuk mengimplementasikan tumpukan dalam waktu konstan diamortisasi. Namun, saya bisa memikirkan cara untuk mendapatkan dua antrian untuk mengimplementasikan tumpukan dalam waktu linear kasus terburuk.

• $A$$B$ .
• Setiap kali ada operasi push, balik bit dan masukkan elemen dalam antrian bit sekarang demarkasi. Pop semuanya dari antrian lain dan dorong ke antrian saat ini.
• Operasi pop melepas bagian depan antrian saat ini dan tidak menyentuh bit status eksternal.

Tentu saja, kita dapat menambahkan sedikit keadaan eksternal yang memberi tahu kita apakah operasi terakhir adalah push atau pop. Kita dapat menunda memindahkan semuanya dari satu antrian ke antrian yang lain sampai kita mendapatkan dua operasi push berturut-turut. Ini juga membuat operasi pop sedikit lebih rumit. Ini memberi kita O (1) kompleksitas diamortisasi untuk operasi pop. Sayangnya push tetap linier.

Semua ini bekerja karena setiap kali operasi push dilakukan, elemen baru diletakkan di kepala antrian kosong dan antrian penuh ditambahkan ke ujung ekornya, secara efektif membalikkan elemen.

Jika Anda ingin mendapatkan diamortisasi operasi waktu konstan, Anda mungkin harus melakukan sesuatu yang lebih pintar.

Ada solusi sepele, jika antrian Anda memungkinkan pemuatan di depan, yang hanya membutuhkan satu antrian (atau, lebih khusus, deque.) Mungkin ini adalah jenis antrian yang diinginkan TA dalam pertanyaan awal?

Tanpa memungkinkan pemuatan di depan, berikut adalah solusi lain:

Algoritma ini membutuhkan dua antrian dan dua pointer, kami akan memanggil mereka masing-masing Q1, Q2, primer, dan sekunder. Setelah inisilisasi, Q1 dan Q2 kosong, poin primer ke Q1 dan poin sekunder ke Q2.

Operasi PUSH itu sepele, hanya terdiri dari:

*primary.enqueue(value);

Operasi POP sedikit lebih terlibat; itu membutuhkan spooling semua kecuali item terakhir dari antrian utama ke antrian sekunder, menukar pointer, dan mengembalikan item yang tersisa terakhir dari antrian asli:

while(*primary.size() > 1)
{
    *secondary.enqueue(*primary.dequeue());
}

swap(primary, secondary);
return(*secondary.dequeue());

Tidak ada batas pemeriksaan dilakukan, dan itu bukan O (1).

Saat saya mengetik ini, saya melihat bahwa ini dapat dilakukan dengan antrian tunggal menggunakan for loop sebagai pengganti loop sementara, seperti yang telah dilakukan Alex. Either way, operasi PUSH adalah O (1) dan operasi POP menjadi O (n).

Berikut adalah solusi lain yang menggunakan dua antrian dan satu pointer, yang disebut Q1, Q2, dan queue_p, masing-masing:

Setelah inisialisasi, Q1 dan Q2 kosong dan queue_p menunjuk ke Q1.

Sekali lagi, operasi PUSH adalah sepele, tetapi memang membutuhkan satu langkah tambahan menunjuk queue_p di antrian lainnya:

*queue_p.enqueue(value);
queue_p = (queue_p == &Q1) ? &Q2 : &Q1;

Operasi operasi POP mirip dengan sebelumnya, tetapi sekarang ada n / 2 item yang perlu diputar melalui antrian:

queue_p = (queue_p == &Q1) ? &Q2 : &Q1;
for(i=0, i<(*queue_p.size()-1, i++)
{
    *queue_p.enqueue(*queue_p.dequeue());
}
return(*queue_p.dequeue());

Operasi PUSH masih O (1), tetapi sekarang operasi POP adalah O (n / 2).

Secara pribadi, untuk masalah ini, saya lebih suka ide menerapkan antrian tunggal, ganda (deque) dan menyebutnya stack ketika kita mau.

$k$$Θ(n^{1/k})$

$k$
$n$
$O(1)$ atau tidak.

$i$$Θ(n^{i/k})$$Θ(n^{i/k})$$O(1)$$i+1$$O(n^{1/k})$$i-1$$Θ(n^{1/k})$ (atau jika kita hanya memiliki satu tumpukan dan memungkinkan waktu pop diamortisasi).

$m$$m$$Ω(mn^{1/k})$$o(n^{1/k})$$Ω(n^{1/k})$$o(n^{2/k})$$k$$o(n)$

$Θ(\log n)$

Tumpukan dapat diimplementasikan menggunakan dua antrian dengan menggunakan antrian kedua sebagai ab uffer. Ketika item didorong ke tumpukan mereka ditambahkan ke ujung antrian. Setiap kali item muncul, elemen n - 1 dari antrian pertama harus dipindahkan ke yang kedua, sedangkan item yang tersisa dikembalikan. public class QueueStack mengimplementasikan IStack {private IQueue q1 = new Queue (); IQueue pribadi q2 = Antrian baru (); public void push (E e) {q1.enqueue (e) // O (1)} pop E publik (E e) {while (1 <q1.size ()) // O (n) {q2.enqueue ( q1.dequeue ()); } sw apQueues (); return q2.dequeue (); } p rivate void swapQueues () {IQueue Q = q2; q2 = q1; q1 = Q; }}