Apa gunanya menerapkan Stack menggunakan dua antrian?

Saya memiliki pertanyaan pekerjaan rumah berikut:

Terapkan metode stack push (x) dan pop () menggunakan dua antrian.

Ini aneh bagi saya karena:

• Stack adalah antrian (LIFO)
• Saya tidak mengerti mengapa Anda perlu dua antrian untuk mengimplementasikannya

Saya mencari di sekitar:

• GeeksForGeeks
• StackOverflow

dan menemukan beberapa solusi. Inilah yang akhirnya saya dapatkan:

public class Stack<T> {
    LinkedList<T> q1 = new LinkedList<T>();
    LinkedList<T> q2 = new LinkedList<T>();

    public void push(T t) {
        q1.addFirst(t);
    }

    public T pop() {
        if (q1.isEmpty()) {
            throw new RuntimeException(
                "Can't pop from an empty stack!");
        }

        while(q1.size() > 1) {
            q2.addFirst( q1.removeLast() );
        }

        T popped = q1.pop();

        LinkedList<T> tempQ = q1;
        q1 = q2;
        q2 = tempQ;

        return popped;
    }
}

Tapi saya tidak mengerti apa kelebihannya daripada menggunakan satu antrian; versi dua antrian tampaknya rumit tanpa tujuan.

Katakanlah kita memilih untuk mendorong menjadi lebih efisien dari 2 (seperti yang saya lakukan di atas), pushakan tetap sama, dan pophanya akan membutuhkan iterasi ke elemen terakhir, dan mengembalikannya. Dalam kedua kasus, pushakan menjadi O(1), dan popakan menjadi O(n); tetapi versi antrian tunggal akan lebih sederhana secara drastis. Seharusnya hanya membutuhkan satu loop.

Apakah saya melewatkan sesuatu? Setiap wawasan di sini akan dihargai.

Tidak ada keuntungan: ini murni latihan akademis.

Sebuah sangat lama lalu ketika saya masih mahasiswa baru di perguruan tinggi saya memiliki latihan yang sama ¹ . Tujuannya adalah untuk mengajarkan siswa bagaimana menggunakan pemrograman berorientasi objek untuk mengimplementasikan algoritma alih-alih menulis solusi berulang menggunakan forloop dengan penghitung loop. Alih-alih, gabungkan dan gunakan kembali struktur data yang ada untuk mencapai tujuan Anda.

Anda tidak akan pernah menggunakan kode ini di Dunia Nyata ^TM . Yang perlu Anda ambil dari latihan ini adalah bagaimana "berpikir di luar kotak" dan menggunakan kembali kode.

Harap perhatikan bahwa Anda harus menggunakan antarmuka java.util.Queue dalam kode Anda alih-alih menggunakan implementasi secara langsung:

Queue<T> q1 = new LinkedList<T>();
Queue<T> q2 = new LinkedList<T>();

Ini memungkinkan Anda untuk menggunakan Queueimplementasi lain jika diinginkan, serta menyembunyikan ² metode yang ada LinkedListyang mungkin menyiasati semangat Queueantarmuka. Ini termasuk get(int)dan pop()(saat kode Anda dikompilasi, ada kesalahan logika di sana mengingat kendala tugas Anda. Mendeklarasikan variabel Anda sebagai Queueganti LinkedListakan mengungkapkannya). Bacaan terkait: Memahami “pemrograman ke suatu antarmuka” dan Mengapa antarmuka bermanfaat?

^{1 _{Saya masih ingat: latihannya adalah membalikkan tumpukan dengan hanya menggunakan metode pada antarmuka Stack dan tidak ada metode utilitas di java.util.Collectionskelas utilitas "statis saja" lainnya. Solusi yang benar melibatkan penggunaan struktur data lain sebagai objek penampung sementara: Anda harus mengetahui struktur data yang berbeda, propertinya, dan cara menggabungkannya untuk melakukannya. Mengacaukan sebagian besar kelas CS101 saya yang belum pernah diprogram sebelumnya.}}

^{2 _{Metode ini masih ada, tetapi Anda tidak dapat mengaksesnya tanpa mengetik gips atau refleksi. Jadi tidak mudah untuk menggunakan metode non-antrian itu.}}

Tidak ada keuntungan. Anda telah benar menyadari bahwa menggunakan Antrian untuk mengimplementasikan Stack mengarah pada kompleksitas waktu yang mengerikan. Tidak ada (kompeten) programmer yang akan melakukan hal seperti ini di "kehidupan nyata".

Tapi itu mungkin. Anda dapat menggunakan satu abstraksi untuk mengimplementasikan yang lain, dan sebaliknya. Tumpukan dapat diimplementasikan dalam dua Antrian, dan Anda juga dapat menerapkan Antrian dalam dua tumpukan. Keuntungan dari latihan ini adalah:

• Anda rekap tumpukan
• Anda rekap Antrian
• Anda terbiasa dengan pemikiran algoritmik
• Anda mempelajari algoritma terkait tumpukan
• Anda bisa memikirkan pengorbanan dalam algoritma
• dengan menyadari kesetaraan Antrian dan Tumpukan, Anda menghubungkan berbagai topik kursus Anda
• Anda mendapatkan pengalaman pemrograman praktis

Sebenarnya, ini adalah latihan yang bagus. Saya harus melakukannya sendiri sekarang :)

Pasti ada tujuan nyata untuk membuat antrian dari dua tumpukan. Jika Anda menggunakan struktur data yang tidak dapat diubah dari bahasa fungsional, Anda dapat mendorong ke dalam tumpukan item yang dapat didorong, dan menarik dari daftar item yang dapat diperbaiki. Item yang dapat dibuka akan dibuat ketika semua item telah muncul, dan stack yang dapat dibuka adalah kebalikan dari stack yang dapat didorong, di mana stack yang dapat didorong yang baru sekarang kosong. Itu efisien.

Adapun tumpukan yang terbuat dari dua antrian? Itu mungkin masuk akal dalam konteks di mana Anda memiliki banyak antrian besar dan cepat yang tersedia. Ini benar-benar tidak berguna karena latihan Java semacam ini. Tetapi mungkin masuk akal jika itu adalah saluran atau antrian pengiriman pesan. (yaitu: N pesan enqueued, dengan operasi O (1) untuk memindahkan (N-1) item di depan ke antrian baru.)

Latihan ini dibuat dari sudut pandang praktis. Intinya adalah untuk memaksa Anda menggunakan antarmuka antrian dengan cara yang cerdas untuk mengimplementasikan tumpukan. Sebagai contoh, solusi "Satu antrian" Anda mengharuskan Anda mengulangi antrian untuk mendapatkan nilai input terakhir untuk operasi tumpukan "pop". Namun, struktur data antrian tidak memungkinkan untuk beralih pada nilai-nilai, Anda dibatasi untuk mengaksesnya di masuk pertama, keluar pertama (FIFO).

Seperti yang telah dicatat oleh orang lain: tidak ada keuntungan dunia nyata.

Bagaimanapun, satu jawaban untuk bagian kedua dari pertanyaan Anda, mengapa tidak hanya menggunakan satu antrian, berada di luar Jawa.

Di Jawa bahkan Queueantarmuka memiliki size()metode dan semua implementasi standar dari metode tersebut adalah O (1).

Itu belum tentu benar untuk daftar tertaut yang naif / kanonik seperti yang akan diimplementasikan oleh programmer C / C ++, yang hanya akan menyimpan pointer ke elemen pertama dan terakhir dan setiap elemen pointer ke elemen berikutnya.

Dalam hal ini size()adalah O (n) dan harus dihindari dalam loop. Atau implementasinya tidak jelas dan hanya menyediakan minimum add()dan minimum remove().

Dengan implementasi seperti itu Anda harus menghitung jumlah elemen terlebih dahulu dengan mentransfernya ke antrian kedua, mentransfer n-1elemen kembali ke antrian pertama dan mengembalikan elemen yang tersisa.

Yang mengatakan, itu mungkin tidak akan membuat sesuatu seperti ini jika Anda tinggal di tanah Jawa.

Sulit membayangkan penggunaan untuk implementasi seperti itu, itu benar. Tetapi sebagian besar intinya adalah untuk membuktikan bahwa itu bisa dilakukan .

Dalam hal penggunaan sebenarnya untuk hal-hal ini, saya dapat memikirkan dua hal. Satu kegunaan untuk ini adalah menerapkan sistem di lingkungan terbatas yang tidak dirancang untuknya : misalnya, blok redstone Minecraft berubah untuk mewakili sistem Turing-lengkap, yang telah digunakan orang untuk mengimplementasikan sirkuit logika dan bahkan seluruh CPU. Pada hari-hari awal game yang digerakkan oleh skrip, banyak bot game pertama juga diterapkan dengan cara ini.

Tetapi Anda juga dapat menerapkan prinsip ini secara terbalik, memastikan bahwa ada sesuatu yang tidak mungkin dalam sistem ketika Anda tidak menginginkannya . Ini dapat muncul dalam konteks keamanan: misalnya, sistem konfigurasi yang kuat dapat menjadi aset, tetapi masih ada tingkat daya yang Anda mungkin lebih suka tidak berikan kepada pengguna. Ini membatasi apa yang dapat Anda izinkan untuk melakukan bahasa konfigurasi, jangan sampai itu ditumbangkan oleh penyerang, tetapi dalam hal ini, itulah yang Anda inginkan.