Implement Queue Using Stacks
Buat antrean first in, first out yang hanya menggunakan dua stack sebagai penyimpanan. Stack hanya dapat menambahkan item di bagian atas, menghapus item teratas, membaca item teratas, dan memberi tahu apakah stack kosong. Antrean mendukung push x (menambahkan x di bagian belakang), pop (menghapus dan mengembalikan item terdepan), peek (mengembalikan item terdepan), dan empty (apakah antrean kosong?).
Kamu mendapatkan operasi secara berurutan dalam ops, dengan args[i] yang menyimpan nilai untuk push dan 0 untuk setiap operasi lainnya. Jalankan operasi tersebut pada satu antrean yang awalnya kosong, lalu kembalikan satu string untuk setiap operasi: "null" untuk push, angka dalam bentuk teks untuk pop atau peek, dan "true" atau "false" untuk empty.
Fungsi
- opsstring-array
- operasi-operasi, sesuai urutan pelaksanaannya
- argsinteger-array
- nilai untuk setiap push, 0 untuk semua operasi lainnya
- Mengembalikanstring-array
- satu jawaban untuk setiap operasi, sebagai teks
Batasan
1 ≤ ops.length ≤ 2000args.length == ops.length- Setiap
ops[i]adalahpush,pop,peekatauempty. -109 ≤ args[i] ≤ 109untuk operasi push, danargs[i] == 0untuk operasi lainnya.popdanpeekhanya dipanggil ketika antrean berisi setidaknya satu item.
Contoh
- Input
- ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
- Output
- ["null", "null", "1", "1", "false"]
- Penjelasan
- Setelah memasukkan 1 lalu 2, bagian depan adalah 1, jadi
peekdanpopsama-sama mengembalikan"1". Angka 2 masih berada di dalam, jadiemptymengembalikan"false".
- Input
- ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
- Output
- ["null", "null", "4", "null", "7", "9", "true"]
- Penjelasan
- Pop pertama mengembalikan 4, item yang paling lama. 9 tiba saat 7 masih menunggu, dan 9 keluar setelah 7 karena 9 masuk setelahnya. Antrean kemudian kosong, jadi jawaban terakhir adalah
"true".
- Input
- ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
- Output
- ["true", "null", "-3", "-3", "true"]
- Penjelasan
- Queue dimulai dalam keadaan kosong, jadi jawaban pertama adalah
"true". Angka negatif disimpan seperti angka lainnya: peek dan pop sama-sama mengembalikan"-3", lalu queue kembali kosong.
Pertanyaan lanjutan
Bagaimana kamu menambahkan operasi back yang mengembalikan item terbaru dalam O(1), tanpa merusak batas amortisasi operasi lainnya?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Stack mengeluarkan item dengan urutan yang paling baru terlebih dahulu, sedangkan queue mengeluarkan item yang paling lama terlebih dahulu. Apa yang terjadi pada urutannya saat kamu mengeluarkan semua item dari satu stack lalu memasukkannya ke stack lain?
Memindahkan isi satu tumpukan ke tumpukan lainnya akan membalik urutannya, sehingga item terlama berada di atas. Beri setiap tumpukan tugas: satu menerima item baru yang di-push, sedangkan yang lain melayani operasi pop dan peek.
Pindahkan isi dari stack push ke stack pop hanya saat stack pop kosong. Jika dipindahkan lebih awal, item yang lebih lama dan masih menunggu akan tertimbun di bawah item yang lebih baru. Dengan begitu, setiap item hanya berpindah paling banyak satu kali.
Solusi
stack mengembalikan item dari yang terbaru terlebih dahulu, sedangkan queue mengembalikan item dari yang terlama terlebih dahulu. Menuangkan satu stack ke stack lain membalik urutannya, sehingga urutan stack berubah menjadi urutan queue. Pertanyaannya adalah kapan harus menuang: jika dilakukan setiap operasi, biayanya O(n) setiap kali, sedangkan jika menuang hanya saat stack kedua kehabisan item, setiap item hanya dipindahkan sekali.
Susun ulang seluruh tumpukan setiap kali push
Intuisi
Simpan semua item dalam satu stack, main, dengan item tertua di atas, agar pop, peek, dan empty menjadi operasi stack tunggal. Operasi push harus menempatkan item baru di bagian bawah: pindahkan semua item ke helper, masukkan item baru ke main yang kosong, lalu pindahkan semuanya kembali. Dua kali pembalikan akan mengembalikan urutannya, dengan item baru di bagian bawah.
Setiap operasi push memindahkan semua item yang tersimpan dua kali. Memasukkan 1.000 item berturut-turut memerlukan sekitar 2 × (0 + 1 + ... + 999), hampir satu juta perpindahan.
Algoritma
- Simpan dua stack,
maindengan item tertua di atas, danhelperyang kosong. - Untuk
push x: keluarkan setiap item darimainkehelper, masukkanxkemain, lalu keluarkan setiap item darihelperkembali kemain. - Untuk
popdanpeek: keluarkan atau baca item teratas darimain. - Untuk
empty: laporkan apakahmainkosong.
class TwoStackQueue:
def __init__(self):
self.main = [] # the oldest item is on top
self.helper = []
def push(self, x):
# Move everything aside, put x at the bottom, move everything back.
while self.main:
self.helper.append(self.main.pop())
self.main.append(x)
while self.helper:
self.main.append(self.helper.pop())
def pop(self):
return self.main.pop()
def peek(self):
return self.main[-1]
def empty(self):
return not self.main
def queueOps(ops, args):
queue = TwoStackQueue()
result = []
for op, arg in zip(ops, args):
if op == "push":
queue.push(arg)
result.append("null")
elif op == "pop":
result.append(str(queue.pop()))
elif op == "peek":
result.append(str(queue.peek()))
else:
result.append("true" if queue.empty() else "false")
return resultStack inbox dan outbox dengan pemindahan tertunda
Intuisi
Beri setiap stack tugas yang berbeda. Operasi push masuk ke inbox. Operasi pop dan peek membaca outbox, dengan item tertua selalu berada di posisi teratas. Saat outbox kosong, tuangkan seluruh isi inbox ke dalamnya: item terbaru keluar lebih dulu dari inbox dan berada di bagian bawah, sehingga item tertua berada di bagian atas.
Tuangkan hanya saat outbox kosong. Selama masih berisi item, item-item itu lebih lama daripada apa pun di inbox dan harus keluar lebih dulu. Dalam contoh kedua, 4 dan 7 dituangkan untuk operasi pop pertama, sementara 9 menunggu di inbox sampai 7 keluar.
Setiap nilai di-push ke inbox satu kali, dipindahkan ke outbox satu kali, dan di-pop satu kali, sehingga total biaya n operasi adalah O(n).
Algoritma
- Siapkan dua stack kosong,
inboxdanoutbox. - Untuk
push x: tambahkanxkeinbox. - Untuk
popataupeek: jikaoutboxkosong, pindahkan setiap item dariinboxkeoutboxdengan operasi pop. Lalu, lakukan pop atau baca item teratas darioutbox. - Untuk
empty: laporkan apakah kedua stack kosong.
class TwoStackQueue:
def __init__(self):
self.inbox = [] # new items go on top
self.outbox = [] # the oldest item is on top
def push(self, x):
self.inbox.append(x)
def _refill(self):
# Only when the outbox is empty: pouring the inbox over reverses it,
# so the oldest item lands on top.
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._refill()
return self.outbox.pop()
def peek(self):
self._refill()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
def queueOps(ops, args):
queue = TwoStackQueue()
result = []
for op, arg in zip(ops, args):
if op == "push":
queue.push(arg)
result.append("null")
elif op == "pop":
result.append(str(queue.pop()))
elif op == "peek":
result.append(str(queue.peek()))
else:
result.append("true" if queue.empty() else "false")
return result
Jebakan dan kasus tepi
- Memindahkan item saat
outboxmasih berisi item. Item yang lebih baru berada di atas item yang lebih lama dan keluar lebih dulu: pada contoh kedua, 9 akan keluar sebelum 7. - Melaporkan
emptyhanya berdasarkanoutbox. Tepat setelah push, item berada diinbox, jadi antrean tidak kosong. - Mengisi ulang saat
pop, tetapi tidak saatpeek. Pada contoh pertama, peek setelah dua push mendapatioutboxkosong. - Mengembalikan angka atau boolean. Setiap jawaban berupa string, termasuk
"null"untuk push.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu antrean yang dibuat dari dua stack?
Push memiliki kompleksitas O(1), sedangkan pop dan peek memiliki kompleksitas O(1) secara amortisasi. Satu pemanggilan dapat memindahkan semua item sekaligus, tetapi biaya pemindahan itu ditanggung oleh operasi push sebelumnya, karena setiap item hanya dipindahkan sekali. Sebanyak n operasi membutuhkan paling banyak sekitar 4n langkah stack, dan penggunaan ruangnya adalah O(n).
Mengapa kamu membutuhkan dua stack, bukan satu?
Sebuah stack hanya menampilkan item terbarunya, sedangkan queue membutuhkan item terlamanya. Untuk mencapai bagian bawah, kamu harus menghapus semua item di atasnya, dan item-item itu perlu tempat untuk menunggu: stack kedua. Memindahkan item-item tersebut membalik urutannya, sehingga urutan dari yang terbaru terlebih dahulu berubah menjadi yang terlama terlebih dahulu.
Bisakah kamu mengimplementasikan stack menggunakan queue?
Ya, tetapi tanpa penghematan amortisasi. Dengan satu antrean, setelah menambahkan item baru, ambil setiap item yang lebih lama dari bagian depan lalu tambahkan ke bagian belakang, sehingga item baru berada di bagian depan. Operasi push menjadi O(n) dan pop O(1).
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def queueOps(ops, args):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
ops = ["push", "push", "peek", "pop", "empty"] args = [1, 2, 0, 0, 0]
Output yang diharapkan
["null", "null", "1", "1", "false"]