Misalkan kita memiliki dua tumpukan dan tidak ada variabel sementara lainnya.
Apakah mungkin untuk "membangun" struktur data antrian hanya menggunakan dua tumpukan?
algorithm
data-structures
stack
queue
Nitin
sumber
sumber
A - Cara Membalik Stack
Untuk memahami cara membuat antrian menggunakan dua tumpukan, Anda harus memahami cara membalikkan tumpukan sebening kristal. Ingat bagaimana tumpukan bekerja, ini sangat mirip dengan tumpukan piring di dapur Anda. Hidangan dicuci terakhir akan berada di atas tumpukan bersih, yang disebut sebagai L ast saya n F irst O ut (LIFO) dalam ilmu komputer.
Mari kita bayangkan tumpukan kita seperti botol seperti di bawah ini;
Jika kita mendorong bilangan bulat masing-masing 1,2,3, maka 3 akan berada di atas tumpukan. Karena 1 akan didorong pertama, maka 2 akan diletakkan di atas 1. Terakhir, 3 akan diletakkan di atas tumpukan dan status terbaru tumpukan kami direpresentasikan sebagai botol akan seperti di bawah ini;
Sekarang tumpukan kami telah diwakili karena botol diisi dengan nilai 3,2,1. Dan kami ingin membalikkan tumpukan sehingga elemen atas tumpukan menjadi 1 dan elemen dasar tumpukan akan menjadi 3. Apa yang bisa kita lakukan? Kita dapat mengambil botol dan memegangnya terbalik sehingga semua nilai harus terbalik agar?
Ya kita bisa melakukan itu, tapi itu sebotol. Untuk melakukan proses yang sama, kita perlu memiliki tumpukan kedua yang akan menyimpan elemen tumpukan pertama dalam urutan terbalik. Mari kita letakkan tumpukan terisi ke kiri dan tumpukan kosong baru di sebelah kanan. Untuk membalik urutan elemen, kita akan membuang setiap elemen dari tumpukan kiri, dan mendorongnya ke tumpukan kanan. Anda dapat melihat apa yang terjadi saat kami melakukannya pada gambar di bawah ini;
Jadi kita tahu cara membalikkan tumpukan.
B - Menggunakan Dua Tumpukan Sebagai Antrian
Pada bagian sebelumnya, saya telah menjelaskan bagaimana cara membalik urutan elemen tumpukan. Ini penting, karena jika kita mendorong dan membuka elemen ke stack, hasilnya akan persis dalam urutan antrian yang terbalik. Berpikir tentang contoh, mari kita dorong array bilangan bulat
{1, 2, 3, 4, 5}
ke tumpukan. Jika kita pop elemen dan mencetaknya sampai tumpukan kosong, kita akan mendapatkan array dalam urutan terbalik dari urutan dorong, yang akan{5, 4, 3, 2, 1}
Ingat bahwa untuk input yang sama, jika kita membagi antrian sampai antrian kosong, output akan{1, 2, 3, 4, 5}
. Jadi jelas bahwa untuk urutan input elemen yang sama, output antrian persis kebalikan dari output stack. Seperti yang kita tahu cara membalikkan tumpukan menggunakan tumpukan tambahan, kita dapat membangun antrian menggunakan dua tumpukan.Model antrian kami akan terdiri dari dua tumpukan. Satu tumpukan akan digunakan untuk
enqueue
operasi (tumpukan # 1 di sebelah kiri, akan disebut sebagai Input Stack), tumpukan lain akan digunakan untukdequeue
operasi (tumpukan # 2 di sebelah kanan, akan disebut sebagai Output Stack). Lihat gambar di bawah ini;Kode semu kami adalah seperti di bawah ini;
Operasi Enqueue
Operasi Dequeue
Mari kita
{1, 2, 3}
masing-masing membuat bilangan bulat . Integer akan didorong pada Input Stack ( Stack # 1 ) yang terletak di sebelah kiri;Lalu apa yang akan terjadi jika kita menjalankan operasi dequeue? Setiap kali operasi dequeue dijalankan, antrian akan memeriksa apakah Output Stack kosong atau tidak (lihat kode semu di atas) Jika Output Stack kosong, maka Stack Input akan diekstraksi pada output sehingga elemen-elemen Input Stack akan dibalik. Sebelum mengembalikan nilai, antrian akan seperti di bawah ini;
Lihat urutan elemen dalam Output Stack (Stack # 2). Sudah jelas bahwa kita dapat memunculkan elemen dari Output Stack sehingga hasilnya akan sama seperti jika kita keluar dari antrian. Jadi, jika kita menjalankan dua operasi dequeue, pertama kita akan mendapatkan
{1, 2}
masing-masing. Kemudian elemen 3 akan menjadi satu-satunya elemen dari Stack Output, dan Stack Input akan kosong. Jika kita memberikan elemen 4 dan 5, maka status antrian adalah sebagai berikut;Sekarang Output Stack tidak kosong, dan jika kita menjalankan operasi dequeue, hanya 3 yang akan muncul dari Output Stack. Maka negara akan terlihat seperti di bawah ini;
Sekali lagi, jika kita menjalankan dua operasi dequeue lagi, pada operasi dequeue pertama, antrian akan memeriksa apakah Output Stack kosong, yang benar. Kemudian keluarkan elemen-elemen dari Input Stack dan dorong mereka ke Output Stack sampai Input Stack kosong, maka status Antrian akan seperti di bawah ini;
Mudah dilihat, output dari dua operasi dequeue akan menjadi
{4, 5}
C - Implementasi Antrian Dibangun dengan Dua Tumpukan
Berikut ini adalah implementasi di Jawa. Saya tidak akan menggunakan implementasi Stack yang sudah ada sehingga contoh di sini akan menemukan kembali roda;
C - 1) Kelas MyStack: Implementasi Simple Stack
C - 2) Kelas MyQueue: Implementasi Antrian Menggunakan Two Stacks
C - 3) Kode Demo
C - 4) Contoh Output
sumber
Anda bahkan dapat mensimulasikan antrian menggunakan hanya satu tumpukan. Tumpukan kedua (sementara) dapat disimulasikan oleh tumpukan panggilan panggilan rekursif ke metode insert.
Prinsipnya tetap sama ketika memasukkan elemen baru ke dalam antrian:
Kelas antrian hanya menggunakan satu tumpukan, akan menjadi sebagai berikut:
sumber
n items
dalam antrian menggunakan struktur data di atas. jumlah(1 + 2 + 4 + 8 + .... + 2(n-1))
menghasilkan~O(n^2)
. Saya harap Anda mengerti maksudnya.Kompleksitas waktu akan lebih buruk. Implementasi antrian yang baik melakukan semuanya dalam waktu yang konstan.
Edit
Tidak yakin mengapa jawaban saya dibatalkan di sini. Jika kami memprogram, kami peduli dengan kompleksitas waktu, dan menggunakan dua tumpukan standar untuk membuat antrian tidak efisien. Ini poin yang sangat valid dan relevan. Jika ada orang lain yang merasa perlu untuk lebih banyak mengurungkan hal ini, saya akan tertarik untuk mengetahui alasannya.
Sedikit lebih detail : tentang mengapa menggunakan dua tumpukan lebih buruk daripada hanya antrian: jika Anda menggunakan dua tumpukan, dan seseorang memanggil dequeue saat kotak keluar kosong, Anda perlu waktu linier untuk sampai ke bagian bawah kotak masuk (seperti yang Anda lihat dalam kode Dave).
Anda dapat menerapkan antrian sebagai daftar yang terhubung sendiri-sendiri (setiap elemen menunjuk ke elemen yang disisipkan berikutnya), menyimpan pointer tambahan ke elemen yang dimasukkan terakhir untuk mendorong (atau menjadikannya daftar siklik). Menerapkan antrian dan dequeue pada struktur data ini sangat mudah dilakukan dalam waktu yang konstan. Itu waktu terburuk terburuk, tidak diamortisasi. Dan, seperti komentar tampaknya meminta klarifikasi ini, waktu konstan terburuk terburuk lebih baik daripada waktu konstan diamortisasi.
sumber
Biarkan antrian diimplementasikan menjadi q dan tumpukan digunakan untuk mengimplementasikan q menjadi stack1 dan stack2.
q dapat diimplementasikan dalam dua cara:
Metode 1 (Dengan membuat operasi enQueue mahal)
Metode ini memastikan bahwa elemen yang baru dimasukkan selalu di atas tumpukan 1, sehingga operasi deQueue hanya muncul dari stack1. Untuk meletakkan elemen di atas stack1, stack2 digunakan.
Metode 2 (Dengan membuat operasi deQueue menjadi mahal)
Dalam metode ini, dalam operasi en-antrian, elemen baru dimasukkan di bagian atas stack1. Dalam operasi de-antrian, jika stack2 kosong maka semua elemen dipindahkan ke stack2 dan akhirnya atas stack2 dikembalikan.
Metode 2 jelas lebih baik daripada metode 1. Metode 1 memindahkan semua elemen dua kali dalam operasi enQueue, sedangkan metode 2 (dalam operasi deQueue) memindahkan elemen sekali dan hanya memindahkan elemen jika stack2 kosong.
sumber
Solusi dalam c #
sumber
Dua tumpukan dalam antrian didefinisikan sebagai stack1 dan stack2 .
Enqueue: Unsur-unsur euqueued selalu didorong ke stack1
Dequeue: Bagian atas stack2 dapat muncul karena itu adalah elemen pertama yang dimasukkan ke dalam antrian ketika stack2 tidak kosong. Ketika stack2 kosong, kami mengeluarkan semua elemen dari stack1 dan mendorongnya stack2 satu per satu. Elemen pertama dalam antrian didorong ke bagian bawah stack1 . Itu dapat muncul keluar langsung setelah muncul dan mendorong operasi karena berada di atas stack2 .
Berikut ini adalah kode sampel C ++ yang sama:
Solusi ini dipinjam dari blog saya . Analisis lebih rinci dengan simulasi operasi langkah demi langkah tersedia di halaman web blog saya.
sumber
Anda harus membuang semuanya dari tumpukan pertama untuk mendapatkan elemen bawah. Kemudian kembalikan semuanya ke tumpukan kedua untuk setiap operasi "dequeue".
sumber
untuk c # developer di sini adalah program lengkap:
sumber
Terapkan operasi antrian berikut menggunakan tumpukan.
push (x) - Elemen push x ke belakang antrian.
pop () - Menghapus elemen dari depan antrian.
mengintip () - Dapatkan elemen depan.
kosong () - Kembali apakah antrian kosong.
sumber
sumber
Implementasi antrian menggunakan dua tumpukan di Swift:
sumber
Meskipun Anda akan mendapatkan banyak posting terkait dengan mengimplementasikan antrian dengan dua tumpukan: 1. Entah dengan membuat proses enQueue jauh lebih mahal 2. Atau dengan membuat proses deQueue jauh lebih mahal
https://www.geeksforgeeks.org/queue-using-stacks/
Salah satu cara penting yang saya temukan dari posting di atas adalah membangun antrian dengan hanya struktur data stack dan stack panggilan rekursi.
Meskipun orang dapat berpendapat bahwa secara harfiah ini masih menggunakan dua tumpukan, tetapi idealnya ini hanya menggunakan satu struktur data tumpukan.
Di bawah ini adalah penjelasan masalahnya:
Nyatakan satu tumpukan untuk enQueuing dan deQueing data dan dorong data ke dalam stack.
sementara deQueueing memiliki kondisi dasar di mana elemen stack muncul ketika ukuran stack adalah 1. Ini akan memastikan bahwa tidak ada stack overflow selama rekursi deQueue.
Sementara deQueueing pertama-tama munculkan data dari atas tumpukan. Idealnya elemen ini akan menjadi elemen yang ada di bagian atas tumpukan. Sekarang setelah ini selesai, panggil fungsi deQueue secara rekursif dan kemudian dorong elemen yang muncul di atas kembali ke dalam tumpukan.
Kode akan terlihat seperti di bawah ini:
Dengan cara ini Anda dapat membuat antrian menggunakan struktur data tumpukan tunggal dan tumpukan panggilan rekursi.
sumber
Di bawah ini adalah solusi dalam bahasa javascript menggunakan sintaks ES6.
Stack.js
QueueUsingTwoStacks.js
Di bawah ini adalah penggunaannya:
index.js
sumber
stack1
. Ketika Anda pergi kedequeue
lagi, Anda akan memindahkannya ke itemstack2
, menempatkan mereka di atas apa yang sudah ada di sana.Saya akan menjawab pertanyaan ini di Go karena Go tidak memiliki banyak koleksi di perpustakaan standarnya.
Karena stack sangat mudah diimplementasikan, saya pikir saya akan mencoba dan menggunakan dua tumpukan untuk mencapai antrian yang berakhir ganda. Untuk lebih memahami bagaimana saya sampai pada jawaban saya, saya telah membagi implementasi menjadi dua bagian, bagian pertama mudah-mudahan lebih mudah dipahami tetapi tidak lengkap.
Ini pada dasarnya dua tumpukan di mana kita membiarkan bagian bawah tumpukan dimanipulasi oleh satu sama lain. Saya juga menggunakan konvensi penamaan STL, di mana operasi push, pop, peek tradisional stack memiliki awalan depan / belakang apakah mereka merujuk ke depan atau belakang antrian.
Masalah dengan kode di atas adalah tidak menggunakan memori dengan sangat efisien. Sebenarnya, ia tumbuh tanpa henti hingga Anda kehabisan ruang. Itu sangat buruk. Cara mengatasinya adalah dengan menggunakan kembali bagian bawah ruang stack jika memungkinkan. Kami harus memperkenalkan offset untuk melacak ini karena sepotong di Go tidak dapat tumbuh di depan setelah menyusut.
Ini banyak fungsi kecil tapi dari 6 fungsi 3 di antaranya hanyalah cermin dari yang lain.
sumber
di sini adalah solusi saya di java menggunakan linkedlist.
}
Catatan: Dalam hal ini, pengoperasian pop sangat memakan waktu. Jadi saya tidak akan menyarankan untuk membuat antrian menggunakan dua tumpukan.
sumber
Dengan
O(1)
dequeue()
, yang sama dengan jawaban pythonquick :Dengan
O(1)
enqueue()
(ini tidak disebutkan dalam posting ini jadi jawaban ini), yang juga menggunakan backtracking untuk muncul dan mengembalikan item paling bawah.Jelas, ini merupakan latihan pengkodean yang bagus karena tidak efisien namun elegan.
sumber
** Solusi JS Mudah **
sumber
Untuk setiap operasi enqueue, kami menambahkan ke bagian atas stack1. Untuk setiap dequeue, kami mengosongkan konten stack1 ke stack2, dan menghapus elemen di atas stack. Kompleksitas waktu adalah O (n) untuk dequeue, karena kami harus menyalin stack1 ke stack2. kompleksitas waktu enqueue sama dengan tumpukan biasa
sumber
if (stack2 != null)
selalu benar karenastack2
dipakai di konstruktor.Implementasi antrian menggunakan dua objek java.util.Stack:
sumber
return inbox.isEmpty() && outbox.isEmpty()
danreturn inbox.size() + outbox.size()
, masing-masing. Kode Dave L. sudah melempar pengecualian ketika Anda keluar dari antrian kosong. Pertanyaan aslinya bahkan bukan tentang Jawa; itu tentang struktur data / algoritma secara umum. Implementasi Java hanyalah ilustrasi tambahan.