Bisakah tiga tumpukan diimplementasikan dalam satu larik, dengan O (1) waktu push / pop?

Dua tumpukan dapat diimplementasikan secara efisien menggunakan satu larik berukuran tetap: tumpukan # 1 mulai dari ujung kiri dan tumbuh ke kanan, dan tumpukan # 2 mulai dari ujung kanan dan tumbuh ke kiri. Apakah sama mungkin untuk tiga tumpukan?

Lebih khusus lagi, apakah mungkin untuk mengimplementasikan tiga tumpukan dengan ketentuan sebagai berikut:

Anda memiliki array ukuran tetap yang dapat menampung objek N.
Selama jumlah dari tiga ukuran stack adalah <N, push () seharusnya tidak gagal.
Operasi push () dan pop () harus menghabiskan waktu O (1).
Selain array, Anda hanya dapat menggunakan O (1) ruang tambahan.

Berikut adalah contoh solusi yang tidak memenuhi persyaratan ini:

Membagi array menjadi 3 bagian tetap dan menggunakan setiap bagian untuk tumpukan (melanggar 2).
Mirip dengan di atas tetapi dengan batas bergerak di antara tumpukan (melanggar 3).
Implementasi sederhana berdasarkan daftar tertaut (melanggar 4).

Saya akan menerima algoritma non-sepele atau bukti ketidakmungkinan bahkan jika mereka tidak memenuhi semua kondisi (1) - (4) persis, misalnya, sebuah algoritma di mana push / pop mengambil O (1) waktu diamortisasi, atau di mana memori tambahan lebih kecil dari O (N), misalnya O (log N). Atau bukti ketidakmungkinan yang menunjukkan bahwa misalnya, mengakses kurang dari 5 elemen array per push / pop tidak mungkin.

ds.data-structures lower-bounds pengguna1020406
sumber

Saya tidak tahu apakah Anda menganggap ini sebagai pelanggaran persyaratan 4, tetapi jika setiap "objek" dalam array objek N Anda dapat menyertakan bidang tambahan seperti indeks integer, maka Anda dapat menerapkan "daftar tertaut" di dalam array Anda. . Anda dapat memegang indeks bagian atas dari masing-masing 3 tumpukan menggunakan 3 variabel eksternal, dan setiap "objek" dapat menunjuk ke elemen sebelumnya yang ditumpuk.

Avi Tal

"Objek" yang saya maksud adalah hal-hal yang mendorong () menerima dan pop () kembali. Dari sudut pandang implementasi stack, mereka hanya gumpalan data buram (misalnya, objek bisa menjadi integer 32-bit). Implementasi stack tidak boleh memodifikasi objek ini dengan cara apa pun.

user1020406

Pertimbangkan Anda pertama kali melakukan urutan operasi push dan kemudian hanya melakukan operasi pop. Apakah ada yang diketahui tentang versi masalah ini?

N

$N$

Dmitri Urbanowicz

Apakah ruang tambahan memuaskan Anda?

O (\sqrt{N})

$O(\sqrt{N})$

Dmitri Urbanowicz

Re: "N mendorong dan kemudian N muncul" versi: Saya tidak tahu, tetapi bahkan mengidentifikasi ini sebagai subproblem yang menarik berguna karena bahkan di sana tidak jelas apakah solusi O (1) mungkin. Lihat jawaban @ Alexei dan utas komentarnya untuk batas atas. Sedangkan untuk solusi , ya saya akan menerimanya. Saya baru memposting pertanyaan di stackexchange, jadi saya tidak yakin bagaimana menangani kasus di mana solusi yang lebih baik dan lebih baik dapat diberikan dari waktu ke waktu. Satu pendekatan yang saya lihat adalah menunggu satu atau dua hari sebelum menerima jawaban jika ada sesuatu yang lebih baik diposting, jadi saya akan melakukannya.

O (\sqrt{N})

$O(\sqrt N)$

user1020406

Jawaban:

Fredman dan Goldsmith menunjukkan dalam "Three Stacks" (Journal of Algorithms, 1994) bahwa sedikit ruang yang terbuang dapat dicapai. Ini juga minimum yang diperlukan untuk array ukuran setidaknya 16 quattuordecillion yottabytes. Saya menggambarkan algoritma sederhana yang membuang-buang kata ruang di jawaban StackOverflow saya untuk pertanyaan ini . Seperti @ dmitri-urbanowicz disebutkan dalam komentar, ini pada dasarnya hanya memperlakukan array sebagai blok ukuran , di mana setiap blok digunakan untuk tepat satu tumpukan dan berisi satu pointer ke blok berikutnya dalam tumpukan itu. $\Theta(n^\varepsilon)$ $\Theta(\sqrt{n})$ $\sqrt{n}$ $\sqrt{n}$

jbapple
sumber

Misalkan N adalah panjang array yang mendasarinya. Saya bisa membayangkan tumpukan sebagai daftar tautan potongan besar, sehingga jumlah keseluruhan potongan tidak lebih dari O (log2 (N)). Tempatkan tumpukan ketiga di antara dua yang pertama, di indeks N / 2. Jadi kami memiliki 3 area yang ditempati dan 2 gratis. Ketika tumpukan tidak dapat menerima elemen berikutnya, ini berarti satu area bebas habis. Jika yang lain habis juga, maka seluruh memori habis. Jika tidak, ada area gratis lain dengan ukuran tidak lebih dari N / 2. Lanjutkan tumpukan yang meluap ke area bebas itu. sehingga seluruh konfigurasi menyerupai tata letak awal tumpukan. Karena memori bebas sekarang tidak lebih dari setengah dari inisial, tidak akan ada lebih dari log2 (N) dari operasi penautan tersebut. Setiap operasi penautan membutuhkan jumlah memori yang tetap untuk menyimpan status stack sebelumnya. Begitu,

Alexei Kaigorodov
sumber

Bagaimana Anda mendaur ulang memori yang diperoleh dengan melontarkan sesuatu dari salah satu bongkahan besar?

Emil Jeřábek

Pertanyaan bagus. Jawaban cepat adalah potongan yang menjadi bebas mengembalikan memorinya ke area bebas tempat sebelumnya diambil. Tetapi bagaimana jika area bebas menyusut sejak waktu memori alokasi untuk potongan itu, dan potongan sekarang tidak berdekatan dengannya? Ini mengarah pada fragmentasi memori bebas, mungkin ada lebih dari 2 area gratis, yang menghancurkan semua konstruksi saya.

Alexei Kaigorodov

Muncul memang masalah di sini, tetapi konstruksi Alexei memberikan batas atas yang bagus untuk versi masalah yang ditanyakan Dmitri dalam komentar: bagaimana jika kita membutuhkan semua dorongan untuk terjadi sebelum semua muncul? Saya bertanya-tanya apakah ada yang lebih baik daripada O (log N) dalam kasus ini.

user1020406