Bagaimana cara menerapkan antrian dengan tiga tumpukan?

Saya menemukan pertanyaan ini dalam buku algoritme ( Algoritma, Edisi ke-4 oleh Robert Sedgewick dan Kevin Wayne).

Antrian dengan tiga tumpukan. Menerapkan antrean dengan tiga tumpukan sehingga setiap operasi antrean memerlukan jumlah operasi tumpukan yang konstan (kasus terburuk). Peringatan: tingkat kesulitan tinggi.

Saya tahu cara membuat antrian dengan 2 tumpukan tetapi saya tidak dapat menemukan solusi dengan 3 tumpukan. Ada ide ?

(oh dan, ini bukan pekerjaan rumah :))

RINGKASAN

• Algoritma O (1) dikenal untuk 6 stack
• Algoritma O (1) dikenal untuk 3 stack, tetapi menggunakan evaluasi malas yang dalam praktiknya sesuai dengan memiliki struktur data internal tambahan, jadi itu bukan merupakan solusi
• Orang-orang di dekat Sedgewick telah mengonfirmasi bahwa mereka tidak mengetahui solusi 3-tumpukan dalam semua batasan pertanyaan asli

DETAIL

Ada dua implementasi di balik tautan ini: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

Salah satunya adalah O (1) dengan tiga tumpukan TETAPI menggunakan eksekusi malas, yang dalam praktiknya membuat struktur data perantara tambahan (penutupan).

Yang lainnya adalah O (1) tetapi menggunakan SIX stack. Namun, ini berfungsi tanpa eksekusi yang lambat.

PEMBARUAN: Makalah Okasaki ada di sini: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps dan tampaknya dia sebenarnya hanya menggunakan 2 tumpukan untuk versi O (1) yang memiliki evaluasi malas. Masalahnya adalah itu benar-benar berdasarkan evaluasi malas. Pertanyaannya adalah apakah itu bisa diterjemahkan ke algoritma 3-stack tanpa evaluasi malas.

PEMBARUAN: Algoritme terkait lainnya dijelaskan dalam makalah "Stacks versus Deques" oleh Holger Petersen, yang diterbitkan dalam Konferensi Tahunan ke-7 tentang Komputasi dan Kombinatorik. Anda dapat menemukan artikel tersebut dari Google Buku. Periksa halaman 225-226. Tetapi algoritme sebenarnya bukan simulasi waktu nyata, melainkan simulasi waktu linier dari antrean berujung ganda pada tiga tumpukan.

gusbro: "Seperti yang dikatakan @Leonel beberapa hari yang lalu, saya pikir akan adil untuk menanyakan kepada Prof. Sedgewick apakah dia tahu solusi atau ada kesalahan. Jadi saya memang menulis kepadanya. Saya baru saja menerima tanggapan (meskipun bukan dari sendiri tetapi dari seorang kolega di Princeton) jadi saya ingin berbagi dengan Anda semua. Dia pada dasarnya mengatakan bahwa dia tidak mengetahui algoritme yang menggunakan tiga tumpukan DAN batasan lain yang diberlakukan (seperti tidak menggunakan evaluasi malas). Dia tahu tentang algoritme yang menggunakan 6 tumpukan seperti yang sudah kita ketahui dengan melihat jawabannya di sini. Jadi, saya kira pertanyaannya masih terbuka untuk menemukan algoritme (atau membuktikan bahwa tidak dapat ditemukan). "

Oke, ini sangat sulit, dan satu-satunya solusi yang bisa saya dapatkan, ingat saya tentang solusi Kirks untuk tes Kobayashi Maru (entah bagaimana curang): Idenya, adalah kita menggunakan tumpukan tumpukan (dan menggunakannya untuk membuat model daftar ). Saya menyebut operasi en / dequeue dan push and pop, lalu kita dapatkan:

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

(StackX = StackY bukanlah menyalin konten, hanya salinan referensi. Ini hanya untuk menjelaskannya dengan mudah. ​​Anda juga dapat menggunakan array 3 tumpukan dan mengaksesnya melalui indeks, di sana Anda hanya perlu mengubah nilai variabel indeks ). Semuanya ada di O (1) dalam istilah operasi tumpukan.

Dan ya saya tahu itu bisa diperdebatkan, karena kami memiliki lebih dari 3 tumpukan implisit, tapi mungkin itu memberi Anda ide-ide bagus kepada orang lain.

EDIT: Contoh penjelasan:

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

Saya mencoba di sini dengan sedikit seni ASCII untuk menunjukkan Stack1.

Setiap elemen dibungkus dalam satu tumpukan elemen (jadi kami hanya memiliki tumpukan tumpukan yang aman).

Anda lihat untuk menghapus pertama kita pop elemen pertama (tumpukan yang berisi di sini elemen 1 dan 2). Kemudian pop elemen berikutnya dan buka di sana 1. Setelah itu kita katakan bahwa poped stack pertama sekarang adalah Stack1 baru kita. Untuk berbicara sedikit lebih fungsional - ini adalah daftar yang diimplementasikan oleh tumpukan 2 elemen di mana elemen teratas ist cdr dan elemen teratas pertama / di bawah adalah mobil . 2 lainnya membantu tumpukan.

Yang paling rumit adalah memasukkan, karena Anda entah bagaimana harus menyelam jauh ke dalam tumpukan bersarang untuk menambahkan elemen lain. Itulah mengapa Stack2 ada di sana. Stack2 selalu merupakan tumpukan paling dalam. Menambahkan kemudian hanya mendorong elemen dan kemudian mendorong ke atas Stack2 baru (dan itulah mengapa kami tidak diizinkan untuk menyentuh Stack2 dalam operasi dequeue kami).

Saya akan mencoba bukti untuk menunjukkan bahwa itu tidak bisa dilakukan.

Misalkan ada antrian Q yang disimulasikan 3 stack, A, B dan C.

Pernyataan

• ASRT0: = Selanjutnya, asumsikan bahwa Q dapat mensimulasikan operasi {queue, dequeue} dalam O (1). Ini berarti bahwa terdapat urutan tertentu dari tumpukan push / pops untuk setiap operasi antrian / dequeue yang akan disimulasikan.

• Tanpa kehilangan keumuman, asumsikan operasi antrian bersifat deterministik.

Biarkan elemen yang dimasukkan ke dalam Q diberi nomor 1, 2, ..., berdasarkan urutan antriannya, dengan elemen pertama yang dimasukkan ke dalam Q didefinisikan sebagai 1, yang kedua sebagai 2, dan seterusnya.

Menetapkan

• Q(0) := Keadaan Q ketika ada 0 elemen di Q (dan dengan demikian 0 elemen di A, B dan C)
• Q(1) := Keadaan Q (dan A, B dan C) setelah operasi antrian 1 Q(0)
• Q(n) := Keadaan Q (dan A, B dan C) setelah operasi antrian n Q(0)

Menetapkan

• |Q(n)| :=jumlah elemen dalam Q(n)(oleh karena itu |Q(n)| = n)
• A(n) := status tumpukan A saat status Q adalah Q(n)
• |A(n)| := jumlah elemen dalam A(n)

Dan definisi serupa untuk tumpukan B dan C.

Sepele,

|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---

|Q(n)| jelas tidak terikat pada n.

Oleh karena itu, setidaknya satu dari |A(n)|, |B(n)|atau |C(n)|tidak terikat pada n.

WLOG1, misalkan tumpukan A tidak dibatasi dan tumpukan B dan C dibatasi.

Tentukan * B_u :=batas atas B * C_u :=batas atas C *K := B_u + C_u + 1

WLOG2, untuk n seperti itu |A(n)| > K, pilih K elemen dari Q(n). Misalkan 1 dari elemen tersebut ada di A(n + x), untuk semua x >= 0, yaitu elemen selalu dalam tumpukan A tidak peduli berapa banyak operasi antrian yang dilakukan.

• X := elemen itu

Kemudian kita bisa mendefinisikan

• Abv(n) :=jumlah item dalam tumpukan A(n)yang di atas X

• Blo(n) :=jumlah elemen dalam tumpukan A(n)yang di bawah X

  | A (n) | = Abv (n) + Blo (n)

ASRT1 :=Jumlah munculan yang diperlukan untuk membatalkan antrean X Q(n)setidaknyaAbv(n)

Dari ( ASRT0) dan ( ASRT1), ASRT2 := Abv(n)harus dibatasi.

Jika Abv(n)tidak dibatasi, maka jika 20 dequeue diperlukan untuk menghapus X dari Q(n), itu akan membutuhkan setidaknya Abv(n)/20pop. Yang tidak terbatas. 20 bisa konstan.

Karena itu,

ASRT3 := Blo(n) = |A(n)| - Abv(n)

harus tidak terikat.

WLOG3, kita dapat memilih elemen K dari bagian bawah A(n), dan salah satunya ada di A(n + x)semuax >= 0

X(n) := elemen itu, untuk n tertentu

ASRT4 := Abv(n) >= |A(n)| - K

Kapanpun sebuah elemen dimasukkan ke dalam Q(n)...

WLOG4, misalkan B dan C sudah terisi hingga batas atasnya. Misalkan batas atas untuk elemen di atas X(n)telah tercapai. Kemudian, elemen baru memasuki A.

WLOG5, misalkan sebagai hasilnya, elemen baru harus masuk di bawah X(n).

ASRT5 := Jumlah pop yang diperlukan untuk meletakkan elemen di bawah X(n) >= Abv(X(n))

Dari (ASRT4), Abv(n)tidak dibatasi pada n.

Oleh karena itu, jumlah pop yang diperlukan untuk meletakkan elemen di bawah X(n)ini tidak terbatas.

Ini bertentangan ASRT1, oleh karena itu, tidak mungkin untuk mensimulasikan O(1)antrian dengan 3 tumpukan.

Yaitu

Setidaknya 1 tumpukan harus dilepas.

Untuk elemen yang tetap dalam tumpukan itu, jumlah elemen di atasnya harus dibatasi, atau operasi dequeue untuk menghapus elemen itu tidak akan dibatasi.

Namun jika jumlah elemen di atasnya dibatasi, maka akan mencapai batasnya. Di beberapa titik, elemen baru harus masuk di bawahnya.

Karena kita selalu dapat memilih elemen lama dari salah satu dari sedikit elemen terendah dari tumpukan itu, mungkin ada sejumlah elemen tak terbatas di atasnya (berdasarkan ukuran tak terbatas dari tumpukan tak terbatas).

Untuk memasukkan elemen baru di bawahnya, karena ada elemen dalam jumlah tak terbatas di atasnya, jumlah pop tak terbatas diperlukan untuk meletakkan elemen baru di bawahnya.

Dan dengan demikian kontradiksi.

Ada 5 pernyataan WLOG (Tanpa kehilangan keumuman). Dalam beberapa hal, mereka dapat dipahami secara intuitif sebagai kebenaran (tetapi mengingat nilainya 5, mungkin perlu waktu). Bukti formal bahwa tidak ada hal umum yang hilang dapat diturunkan, tetapi sangat panjang. Mereka dihilangkan.

Saya mengakui bahwa kelalaian seperti itu mungkin akan membuat pernyataan WLOG dipertanyakan. Dengan paranoia programmer terhadap bug, harap verifikasi pernyataan WLOG jika Anda mau.

Tumpukan ketiga juga tidak relevan. Yang penting adalah ada satu set tumpukan terbatas, dan satu set tumpukan tidak terbatas. Minimal yang dibutuhkan untuk sebuah contoh adalah 2 tumpukan. Jumlah tumpukan harus, tentu saja, terbatas.

Terakhir, jika saya benar bahwa tidak ada bukti, maka harus ada bukti induktif yang lebih mudah tersedia. Mungkin berdasarkan pada apa yang terjadi setelah setiap antrean (pantau terus bagaimana hal itu memengaruhi kasus dequeue terburuk mengingat kumpulan semua elemen dalam antrean).

Catatan: Ini dimaksudkan sebagai komentar untuk implementasi fungsional antrian real-time (kasus terburuk waktu konstan) dengan daftar tertaut tunggal. Saya tidak dapat menambahkan komentar karena reputasi, tetapi alangkah baiknya jika seseorang dapat mengubah ini menjadi komentar yang ditambahkan ke jawaban oleh antti.huima. Kemudian lagi, ini agak panjang untuk sebuah komentar.

@ antti.huima: Daftar tertaut tidak sama dengan tumpukan.

• s1 = (1 2 3 4) --- daftar tertaut dengan 4 node, masing-masing menunjuk ke satu di sebelah kanan, dan memegang nilai 1, 2, 3 dan 4

• s2 = muncul (s1) --- s2 sekarang (2 3 4)

Pada titik ini, s2 setara dengan popped (s1), yang berperilaku seperti tumpukan. Namun, s1 masih tersedia untuk referensi!

• s3 = muncul (muncul (s1)) --- s3 adalah (3 4)

Kita masih bisa mengintip s1 untuk mendapatkan 1, sedangkan dalam implementasi stack yang tepat, elemen 1 dihapus dari s1!

Apa artinya ini?

• s1 adalah referensi ke bagian atas tumpukan
• s2 adalah referensi ke elemen kedua dari tumpukan
• s3 adalah referensi ke ...

Daftar tertaut tambahan yang dibuat sekarang masing-masing berfungsi sebagai referensi / penunjuk! Jumlah tumpukan yang terbatas tidak bisa melakukan itu.

Dari apa yang saya lihat di makalah / kode, semua algoritme menggunakan properti daftar tertaut ini untuk menyimpan referensi.

Sunting: Saya hanya mengacu pada algoritma daftar tertaut 2 dan 3 yang menggunakan properti daftar tertaut ini, saat saya membacanya terlebih dahulu (terlihat lebih sederhana). Ini tidak dimaksudkan untuk menunjukkan bahwa mereka dapat atau tidak berlaku, hanya untuk menjelaskan bahwa daftar tertaut tidak selalu identik. Saya akan membaca yang dengan 6 saat saya senggang. @Welbog: Terima kasih atas koreksinya.

Kemalasan juga dapat mensimulasikan fungsionalitas penunjuk dengan cara yang serupa.

Menggunakan daftar tertaut memecahkan masalah yang berbeda. Strategi ini dapat digunakan untuk mengimplementasikan antrian real-time di Lisp (Atau setidaknya Lisps yang bersikeras membangun segala sesuatu dari daftar tertaut): Lihat "Operasi Antrian Waktu Nyata di Lisp Murni" (ditautkan ke melalui tautan antti.huima). Ini juga merupakan cara yang bagus untuk merancang daftar yang tidak dapat diubah dengan waktu operasi O (1) dan struktur bersama (tidak dapat diubah).

Anda dapat melakukannya dalam waktu konstan diamortisasi dengan dua tumpukan:

------------- --------------
            | |
------------- --------------

Menambah O(1)dan menghapus adalah O(1)jika sisi yang ingin Anda ambil tidak kosong dan O(n)sebaliknya (bagi tumpukan lainnya menjadi dua).

Triknya adalah dengan melihat bahwa O(n)operasi hanya akan dilakukan setiap O(n)saat (jika Anda membelah, misalnya menjadi dua bagian). Oleh karena itu, waktu rata-rata untuk suatu operasi adalah O(1)+O(n)/O(n) = O(1).

Meskipun ini mungkin jahitan seperti masalah, jika Anda menggunakan bahasa imperatif dengan tumpukan berbasis array (tercepat), Anda hanya akan mengamortisasi waktu konstan.