Coding Interview Prep · Pelajaran

Simulasi Saling Menggunakan Stack dan Queue

Implementasikan queue menggunakan dua stack dan stack menggunakan dua queue, serta jelaskan biaya teramortisasi setiap pendekatan.

Pelajaran 4 dari 413 langkah

Simulasi Saling Menggunakan Stack dan Queue adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Mengapa Menirukan Salah Satunya dengan yang Lain?

Mengimplementasikan antrean menggunakan dua tumpukan dan tumpukan menggunakan dua antrean adalah pertanyaan klasik dalam wawancara perancangan. Pertanyaan ini menguji pemahaman Anda tentang invarian kedua struktur data serta kemampuan Anda mempertahankan jaminan satu struktur saat menggunakan operasi dasar dari struktur lainnya. Pewawancara juga menggunakan pertanyaan ini sebagai pengantar untuk membahas kompleksitas amortisasi.

Wawasan utamanya: tumpukan bersifat LIFO, sedangkan antrean bersifat FIFO. Untuk mengubah satu struktur menjadi struktur lainnya, Anda harus membalik urutan — dan membalik tumpukan ke tumpukan lain menghasilkan urutan penyisipan semula, yaitu FIFO.

Antrean Menggunakan Dua Tumpukan (Pendekatan Tertunda)

Pendekatan tertunda: gunakan tumpukan inbox untuk operasi push dan tumpukan outbox untuk operasi pop. Saat operasi pengeluaran dari antrean dipanggil, jika outbox kosong, pindahkan semua elemen dari inbox ke outbox — pembalikan ini mengembalikan urutan FIFO. Jika outbox tidak kosong, keluarkan elemen langsung dari sana. Pemindahan dilakukan secara tertunda, sehingga biaya pemindahan O(n) diamortisasi di banyak operasi.

class MyQueue:
    def __init__(self):
        self.inbox  = []
        self.outbox = []

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

    def _transfer(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._transfer()
        return self.outbox.pop()

    def peek(self):
        self._transfer()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

q = MyQueue()
q.push(1); q.push(2); q.push(3)
print(q.peek())  # 1
print(q.pop())   # 1
print(q.pop())   # 2
q.push(4)
print(q.pop())   # 3

Analisis Amortisasi O(1) untuk Antrean dari Tumpukan

Setiap elemen dipindahkan dari inbox ke outbox paling banyak sekali. Mengeluarkan elemen dari outbox memerlukan O(1), dan pemindahan hanya terjadi saat outbox kosong. Dengan demikian, total pekerjaan untuk n operasi push dan n operasi pop paling banyak adalah 2n operasi tumpukan — total O(n), atau O(1) secara amortisasi untuk setiap operasi. Artinya, operasi individual dapat memiliki kompleksitas O(n) dalam kasus terburuk, tetapi rata-ratanya adalah O(1).

# Trace transfer costs for 10 push/pop interleaved
class TrackedQueue:
    def __init__(self):
        self.inbox = []; self.outbox = []; self.transfers = 0

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

    def pop(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.transfers += 1
        return self.outbox.pop()

q = TrackedQueue()
for i in range(5):
    q.push(i)
for _ in range(5):
    q.pop()
q.push(10); q.push(20)
q.pop()
print('Total transfer operations:', q.transfers)  # at most n

Tumpukan Menggunakan Dua Antrean (Pop Tertunda)

Mengimplementasikan tumpukan dengan dua antrean kurang alami karena antrean bersifat FIFO. Pendekatan pop tertunda: pertahankan satu antrean utama dan satu antrean sementara. Saat push, masukkan elemen ke antrean utama (O(1)). Saat pop atau peek, keluarkan semua elemen kecuali elemen terakhir ke antrean sementara, simpan elemen terakhir, lalu tukar kedua antrean. Operasi ini memerlukan O(n) untuk setiap pop, tetapi O(1) untuk setiap push.

from collections import deque

class MyStack:
    def __init__(self):
        self.main = deque()
        self.temp = deque()

    def push(self, x):
        self.main.append(x)   # O(1)

    def pop(self):
        # Move all but last element to temp
        while len(self.main) > 1:
            self.temp.append(self.main.popleft())
        val = self.main.popleft()   # the 'top'
        self.main, self.temp = self.temp, self.main  # swap
        return val

    def top(self):
        while len(self.main) > 1:
            self.temp.append(self.main.popleft())
        val = self.main[0]
        self.temp.append(self.main.popleft())
        self.main, self.temp = self.temp, self.main
        return val

    def empty(self):
        return len(self.main) == 0

s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top())  # 3
print(s.pop())  # 3
print(s.pop())  # 2

Tumpukan Menggunakan Satu Antrean (Rotasi saat Push)

Implementasi satu antrean yang elegan: saat push, masukkan elemen baru ke antrean, lalu putar antrean agar elemen baru berada di depan. Memutar berarti mengeluarkan dari antrean lalu memasukkan kembali semua elemen yang sudah ada sebelum push. Setelah itu, pop dan peek memerlukan O(1) (cukup mengeluarkan atau melihat elemen depan). Push memerlukan O(n) — pertukaran kinerja yang berlawanan dengan versi dua antrean.

from collections import deque

class MyStackOneQueue:
    def __init__(self):
        self.q = deque()

    def push(self, x):
        self.q.append(x)
        # Rotate: move all preceding elements behind x
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

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

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

    def empty(self):
        return len(self.q) == 0

s = MyStackOneQueue()
s.push(1); s.push(2); s.push(3)
print(s.top())  # 3
print(s.pop())  # 3
print(s.top())  # 2

Rangkuman Pertukaran: Varian Mana yang Dipilih?

Untuk antrean dari dua tumpukan: push O(1), pop/peek O(1) secara amortisasi — pilih ini jika operasi pop sering dilakukan. Untuk tumpukan dari dua antrean: push O(1), pop O(n) — pilih ini jika push jauh lebih sering daripada pop. Untuk tumpukan dari satu antrean: push O(n), pop O(1) — pilih ini jika pop lebih dominan. Jelaskan pertukaran ini secara eksplisit dalam wawancara untuk menunjukkan bahwa Anda memikirkan lebih dari sekadar 'programnya berjalan'.

print('Queue from 2 stacks: push O(1), pop O(1) amortised')
print('Stack from 2 queues: push O(1), pop O(n)')
print('Stack from 1 queue:  push O(n), pop O(1)')

Mengapa Pembalikan Memulihkan FIFO?

Saat elemen 1, 2, 3 di-push ke sebuah tumpukan (tumpukan masukan), elemen-elemen tersebut tersusun dari bawah ke atas sebagai 1, 2, 3. Dengan mengeluarkan semuanya ke tumpukan kedua (tumpukan keluaran), urutannya terbalik: tumpukan keluaran memiliki 3 di bagian bawah dan 1 di bagian atas. Mengeluarkan elemen dari tumpukan keluaran menghasilkan 1, lalu 2, lalu 3 — persis seperti urutan penyisipan FIFO. Inilah alasan tepat dua pembalikan (dua tumpukan) memulihkan FIFO, sedangkan satu tumpukan akan menghasilkan LIFO.

# Demonstrate double-reversal = FIFO
inbox  = [1, 2, 3]   # pushed in this order
outbox = []
while inbox:
    outbox.append(inbox.pop())
print('outbox (one reversal):', outbox)  # [3, 2, 1] top-to-bottom

# Pop from outbox gives FIFO
result = []
while outbox:
    result.append(outbox.pop())
print('dequeued:', result)  # [1, 2, 3] — FIFO!

LeetCode 232: Mengimplementasikan Antrean Menggunakan Tumpukan

LeetCode 232 adalah masalah langsung 'antrean dari dua tumpukan'. Solusi yang diharapkan adalah pemindahan tertunda ke tumpukan keluaran. Dalam wawancara, nyatakan bahwa setiap elemen berpindah dari tumpukan masukan ke tumpukan keluaran paling banyak sekali, sehingga semua operasi memiliki kompleksitas O(1) secara amortisasi. Jelaskan bahwa pemanggilan pop individual dapat memiliki kompleksitas O(n) dalam kasus terburuk (saat tumpukan keluaran kosong), tetapi rata-rata untuk n operasi adalah O(1).

class MyQueue:
    def __init__(self):
        self.inbox  = []
        self.outbox = []

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

    def pop(self):
        self.peek()             # ensure outbox is populated
        return self.outbox.pop()

    def peek(self):
        if not self.outbox:
            while self.inbox:   # transfer lazily
                self.outbox.append(self.inbox.pop())
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

# Simulation
q = MyQueue()
q.push(1); q.push(2)
print(q.peek())  # 1
print(q.pop())   # 1
print(q.empty()) # False

LeetCode 225: Mengimplementasikan Tumpukan Menggunakan Antrean

LeetCode 225 adalah masalah 'tumpukan dari antrean'. Solusi satu antrean dengan rotasi saat push merupakan solusi yang paling rapi. Setelah melakukan push terhadap elemen x, putar antrean dengan memindahkan semua elemen yang sudah ada ke belakang x. Biayanya O(n) untuk setiap push, tetapi membuat top dan pop memiliki kompleksitas O(1). Jelaskan pertukaran ini dan pastikan bahwa solusi tersebut sesuai dengan batasan, misalnya beban kerja dengan sedikit push atau banyak pop.

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x):       # O(n)
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):           # O(1)
        return self.q.popleft()

    def top(self):           # O(1)
        return self.q[0]

    def empty(self):
        return len(self.q) == 0

s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top())  # 3
print(s.pop())  # 3
print(s.top())  # 2
print(s.empty()) # False

Memperluas ke Tiga Tumpukan dalam Satu Larik

Tantangan desain terkait: implementasikan tiga tumpukan menggunakan satu larik. Salah satu pendekatan membagi larik menjadi tiga bagian tetap yang sama besar. Pendekatan yang lebih fleksibel menggunakan penyimpanan berselang-seling dengan penunjuk, memperbesar setiap tumpukan dari wilayahnya dan menyalin data ketika batas-batasnya bertabrakan. Ini menguji pengelolaan larik dinamis dan ditanyakan dalam wawancara tingkat senior. Pendekatan bagian tetap lebih sederhana, tetapi memboroskan ruang jika pertumbuhan tumpukan tidak seimbang.

class ThreeStacks:
    def __init__(self, size):
        self.data = [0] * (3 * size)
        self.tops = [-1, -1, -1]  # relative top of each stack
        self.size = size

    def push(self, stack_num, val):
        self.tops[stack_num] += 1
        if self.tops[stack_num] >= self.size:
            raise OverflowError('stack full')
        self.data[stack_num * self.size + self.tops[stack_num]] = val

    def pop(self, stack_num):
        if self.tops[stack_num] < 0:
            raise IndexError('stack empty')
        val = self.data[stack_num * self.size + self.tops[stack_num]]
        self.tops[stack_num] -= 1
        return val

ts = ThreeStacks(5)
ts.push(0, 10); ts.push(1, 20); ts.push(2, 30)
print(ts.pop(0), ts.pop(1), ts.pop(2))  # 10 20 30

Inti Penting: Pola Simulasi

Masalah simulasi timbal balik mengajarkan prinsip yang lebih luas: struktur data apa pun dapat dibangun dari struktur data lain jika tersedia cukup penyanggaan perantara dan pembalikan. Biaya simulasi bergantung pada operasi mana yang Anda optimalkan — Anda selalu dapat membuat push O(1) atau pop O(1), tetapi membuat keduanya O(1) memerlukan amortisasi atau beberapa struktur tambahan.

Dalam wawancara, selalu tanyakan: 'Operasi mana yang lebih sering digunakan?' Hal ini membantu menentukan pilihan varian implementasi dan menunjukkan pemikiran tingkat senior tentang kebutuhan operasional.

Pemeriksaan Singkat

Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Jawab di pelajaran interaktif

Ringkasan Pelajaran

Dalam pelajaran ini Anda mempelajari: antrean dari dua tumpukan mencapai pop O(1) dengan amortisasi melalui pemindahan elemen secara bertahap saat diperlukan dari kotak masuk ke kotak keluar, tumpukan dari satu antrean mencapai pop O(1) dengan memutar antrean setiap kali push (push O(n)), dan pilihan operasi yang dibuat O(1) bergantung pada pola penggunaan. Selanjutnya kita akan mempelajari internal peta hash dan penanganan tabrakan.

Gratis untuk memulai

Belajar Coding Interview Prep dengan tutor AI — gratis

Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.

Kursus: 90
Pelajaran: 360

Mulai belajar gratis Lihat kursus lengkapnya

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Simulasi Saling Menggunakan Stack dan Queue” gratis?

Ya — teks lengkap “Simulasi Saling Menggunakan Stack dan Queue” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Simulasi Saling Menggunakan Stack dan Queue”?

Implementasikan queue menggunakan dua stack dan stack menggunakan dua queue, serta jelaskan biaya teramortisasi setiap pendekatan. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “Simulasi Saling Menggunakan Stack dan Queue” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

Implementasi Stack dan Penerapannya
Implementasi Queue dan Deque
Pola Stack Monotonik
Simulasi Saling Menggunakan Stack dan Queue

← Kembali ke Coding Interview Prep