Implement Stack using Queues

+10

Buat stack last in, first out yang hanya menggunakan queue untuk menyimpan data. Queue hanya boleh menambahkan item di bagian belakang, menghapus atau membaca item di bagian depan, dan melaporkan ukurannya. Stack mendukung push x (menaruh x di bagian atas), pop (menghapus dan mengembalikan item teratas), top (mengembalikan item teratas dan menyimpannya) dan empty (apakah stack kosong?).

Operasi disediakan secara berurutan dalam ops, dengan args[i] berisi nilai untuk push dan 0 untuk operasi lainnya. Jalankan operasi tersebut pada satu stack kosong dan kembalikan satu string untuk setiap operasi: "null" untuk push, angka dalam bentuk teks untuk pop atau top, dan "true" atau "false" untuk empty.

Fungsi

stackOps(ops: string-array, args: integer-array) → string-array

opsstring-array: operasi, sesuai urutan pelaksanaannya
argsinteger-array: nilai untuk setiap push, 0 untuk setiap operasi lainnya
Mengembalikanstring-array: satu jawaban per operasi, sebagai teks

Batasan

1 ≤ ops.length ≤ 1000
args.length == ops.length
Setiap ops[i] adalah push, pop, top, atau empty.
-10⁹ ≤ args[i] ≤ 10⁹ untuk operasi push, dan args[i] == 0 untuk operasi lainnya.
pop dan top hanya dipanggil saat stack menyimpan setidaknya satu item.

Contoh

Input: ops = ["push", "push", "top", "pop", "empty"]args = [1, 2, 0, 0, 0]
Output: ["null", "null", "2", "2", "false"]
Penjelasan: 2 masuk terakhir, jadi berada di paling atas: top dan pop sama-sama mengembalikan "2". 1 masih ada di dalam, jadi empty mengembalikan "false".

Input: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
Output: ["null", "null", "7", "null", "9", "4", "true"]
Penjelasan: Pop pertama mengembalikan 7, item terbaru. 9 kemudian berada di atas 4 dan keluar lebih dahulu, jadi pop berikutnya mengembalikan "9" dan "4", lalu stack menjadi kosong.

Input: ops = ["empty", "push", "top", "pop", "empty"]args = [0, -3, 0, 0, 0]
Output: ["true", "null", "-3", "-3", "true"]
Penjelasan: Stack dimulai dalam keadaan kosong, jadi jawaban pertama adalah "true". Nilai negatif disimpan seperti nilai lainnya: top dan pop sama-sama mengembalikan "-3", dan stack kembali kosong.

Pertanyaan lanjutan

Bisakah kamu mempertahankan satu queue, tetapi memindahkan pekerjaan dari push ke pop agar push berkompleksitas O(1)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Queue mengeluarkan item yang paling lama terlebih dahulu, sedangkan stack mengeluarkan item yang paling baru terlebih dahulu, dan queue tidak pernah menampilkan item paling belakangnya. Satu-satunya alat yang kamu miliki adalah mengeluarkan item dari depan dengan dequeue dan memasukkan item di belakang dengan enqueue, yang memutar queue. Putar queue untuk membawa item terbaru ke depan, baik saat kamu perlu membacanya maupun tepat setelah item itu tiba.

Dua antrean, keluarkan item terbaru saat pop

Intuisi

Jaga item dalam queue main tetap sesuai urutan kedatangannya, sehingga item terbaru berada di belakang dan satu push berarti satu enqueue. Satu pop memindahkan setiap item lainnya ke queue kedua, spare, sampai tersisa satu item: item terbaru. Keluarkan item itu dengan dequeue lalu tukar queue, karena spare kini menyimpan item lainnya dalam urutan semula. Satu top melakukan proses yang sama, tetapi juga memasukkan item terbaru ke spare dengan enqueue.

Setiap pop atau top memindahkan setiap item yang tersimpan satu kali: 500 push, masing-masing diikuti top, membutuhkan 1 + 2 + ... + 500, sekitar 125.000 pemindahan.

Algoritma

Simpan dua queue: main dengan item dalam urutan kedatangan, dan spare yang kosong.
Untuk push x: masukkan x ke main.
Untuk pop dan top: pindahkan item dari main ke spare sampai tersisa satu, lalu keluarkan item itu sebagai jawaban. Untuk top, masukkan item itu ke spare juga. Tukar kedua queue.
Untuk empty: laporkan apakah main kosong.

from collections import deque

class QueueStack:
    def __init__(self):
        self.main = deque()    # the oldest item at the front, the newest at the back
        self.spare = deque()   # empty between operations

    def push(self, x):
        self.main.append(x)

    def _move_all_but_newest(self):
        # Pass every item except the newest to the spare queue, in order.
        while len(self.main) > 1:
            self.spare.append(self.main.popleft())

    def pop(self):
        self._move_all_but_newest()
        newest = self.main.popleft()
        self.main, self.spare = self.spare, self.main
        return newest

    def top(self):
        self._move_all_but_newest()
        newest = self.main.popleft()
        self.spare.append(newest)   # top keeps the item
        self.main, self.spare = self.spare, self.main
        return newest

    def empty(self):
        return not self.main

def stackOps(ops, args):
    stack = QueueStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(stack.pop()))
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append("true" if stack.empty() else "false")
    return result

Satu queue, putar setelah setiap push

Intuisi

Jaga antrean agar selalu mengikuti urutan stack, dengan item terbaru di depan. Dengan begitu, pop berarti dequeue, top membaca bagian depan, dan antrean kedua tidak diperlukan. Item baru x bergabung di bagian belakang, di belakang item lama yang sudah tersusun dari yang terbaru. Keluarkan item paling depan, lalu masukkan kembali ke bagian belakang sebanyak size-1 kali: setiap langkah memindahkan satu item yang lebih lama ke belakang x sambil mempertahankan urutannya, sehingga x berakhir di bagian depan.

Pada contoh pertama, memasukkan 2 ke [1] menghasilkan [1, 2], lalu satu rotasi menghasilkan [2, 1]. Memasukkan item ke antrean berisi k item memerlukan k rotasi, jadi operasi memasukkan item berkompleksitas O(n), sedangkan operasi lainnya berkompleksitas O(1).

Algoritma

Pertahankan satu queue yang bagian depannya selalu menjadi bagian atas stack.
Untuk push x: masukkan x ke queue, lalu ulangi sebanyak size-1 kali: keluarkan item paling depan, lalu masukkan kembali ke queue.
Untuk pop: keluarkan item paling depan, lalu kembalikan item tersebut.
Untuk top: kembalikan item paling depan tanpa menghapusnya.
Untuk empty: laporkan apakah queue kosong.

from collections import deque

class QueueStack:
    def __init__(self):
        self.queue = deque()   # the newest item is always at the front

    def push(self, x):
        self.queue.append(x)
        # Rotate the older items behind x, so x comes out first.
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self):
        return self.queue.popleft()

    def top(self):
        return self.queue[0]

    def empty(self):
        return not self.queue

def stackOps(ops, args):
    stack = QueueStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(stack.pop()))
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append("true" if stack.empty() else "false")
    return result

Jebakan dan kasus tepi

Memutar sebanyak size kali, bukan size-1 kali. Satu putaran penuh membuat x berada di bagian belakang, sehingga pop berikutnya mengembalikan item tertua.
Memutar sebelum memasukkan x ke antrean. Item yang lebih lama berputar dalam lingkaran dan x tetap berada di bagian belakang.
Dengan dua antrean, tidak memasukkan kembali item ke top. Pop berikutnya lalu mengembalikan item di bawahnya.
Dengan dua antrean, tidak menukarnya. Item berada di spare, dan empty menjawab "true" terlalu cepat.
Mengembalikan angka atau boolean. Setiap jawaban berupa string, termasuk "null" untuk push.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu stack yang dibuat dari queue?

Dengan satu queue yang berotasi setiap kali push, push memiliki kompleksitas O(n), sedangkan pop, top, dan empty memiliki kompleksitas O(1). Dengan dua queue yang memindahkan item setiap kali pop, push memiliki kompleksitas O(1), sedangkan pop dan top memiliki kompleksitas O(n). Dalam kedua cara tersebut, setiap item disimpan satu kali, sehingga penggunaan ruang adalah O(n).

Mengapa stack yang dibuat dari queue lebih lambat daripada queue yang dibuat dari stack?

Memindahkan isi satu stack ke stack lain membalik urutannya, sehingga satu kali pemindahan mengubah urutan stack menjadi urutan queue dan setiap item hanya berpindah sekali selama masa hidupnya. Memindahkan item antar-queue mempertahankan urutannya, sehingga tidak ada pemindahan yang membalik urutan. Karena itu, satu operasi di sini selalu membutuhkan biaya O(n).

Apakah push atau pop yang seharusnya menjadi operasi yang mahal?

Buat operasi yang lebih jarang terjadi menanggung biayanya. Jika stack dibaca dengan top dan pop jauh lebih sering daripada ditambah, lakukan rotasi saat push agar setiap pembacaan berbiaya O(1). Jika banyak push terjadi sebelum beberapa pop, pertahankan push dengan biaya O(1) dan lakukan pemindahan saat pop.

def stackOps(ops, args):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

ops = ["push", "push", "top", "pop", "empty"]
args = [1, 2, 0, 0, 0]

Output yang diharapkan

["null", "null", "2", "2", "false"]