Persediaan Temu Duga Pengaturcaraan · Pelajaran

Simulasi Saling Tindanan dan Baris Gilir

Laksanakan baris gilir menggunakan dua tindanan dan tindanan menggunakan dua baris gilir, sambil menerangkan kos terlunas bagi setiap pendekatan.

Pelajaran 4 daripada 413 langkah

Simulasi Saling Tindanan dan Baris Gilir ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Mengapa Mensimulasikan Satu Struktur dengan Struktur yang Lain?

Melaksanakan baris gilir menggunakan dua tindanan dan tindanan menggunakan dua baris gilir ialah soalan temu duga reka bentuk yang klasik. Soalan ini menguji pemahaman anda tentang invarian kedua-dua struktur data serta keupayaan anda mengekalkan jaminan satu struktur ketika menggunakan operasi asas daripada struktur yang lain. Penemu duga juga menggunakan soalan ini sebagai asas untuk membincangkan kerumitan teramortisasi.

Wawasan utamanya: tindanan adalah LIFO dan baris gilir adalah FIFO. Untuk menukar antara kedua-duanya, anda perlu membalikkan tertib — dan membalikkan tindanan ke dalam tindanan yang lain menghasilkan tertib penyisipan asal, iaitu FIFO.

Baris Gilir Menggunakan Dua Tindanan (Pendekatan Malas)

Pendekatan malas: gunakan tindanan inbox untuk operasi push dan tindanan outbox untuk operasi pop. Apabila operasi mengeluarkan elemen daripada baris gilir dipanggil, jika outbox kosong, pindahkan semua elemen daripada inbox ke outbox — pembalikan ini memulihkan tertib FIFO. Jika outbox tidak kosong, lakukan pop terus daripadanya. Pemindahan berlaku secara malas, lalu kos pemindahan O(n) teramortisasi merentasi 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 O(1) Teramortisasi untuk Baris Gilir daripada Tindanan

Setiap elemen dipindahkan daripada inbox ke outbox paling banyak sekali. Apabila operasi pop daripada outbox ialah O(1) dan pemindahan hanya berlaku apabila outbox kosong, jumlah kerja bagi n operasi push dan n operasi pop ialah paling banyak 2n operasi tindanan — O(n) secara keseluruhan, iaitu O(1) secara teramortisasi bagi setiap operasi. Ini bermakna operasi individu boleh menjadi O(n) dalam kes terburuk, tetapi puratanya ialah 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

Tindanan Menggunakan Dua Baris Gilir (Pop Malas)

Melaksanakan tindanan dengan dua baris gilir kurang semula jadi kerana baris gilir adalah FIFO. Pendekatan pop malas: kekalkan satu baris gilir utama dan satu baris gilir sementara. Pada push, masukkan elemen ke dalam baris gilir utama (O(1)). Pada pop atau peek, keluarkan semua elemen kecuali elemen terakhir ke dalam baris gilir sementara, simpan elemen terakhir, kemudian tukar kedua-dua baris gilir. Ini ialah O(n) bagi setiap operasi pop tetapi O(1) bagi setiap operasi 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

Tindanan Menggunakan Satu Baris Gilir (Putar Semasa Push)

Pelaksanaan elegan menggunakan satu baris gilir: pada push, masukkan elemen baharu, kemudian putarkan baris gilir supaya elemen baharu berada di hadapan. Memutar bermaksud mengeluarkan dan memasukkan semula semua elemen yang telah berada di situ sebelum operasi push. Selepas itu, pop dan peek menjadi O(1) (hanya mengeluarkan atau melihat elemen di hadapan). Push ialah O(n) — pertukaran yang bertentangan dengan versi dua baris gilir.

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

Ringkasan Pertukaran: Varian Mana yang Perlu Dipilih?

Untuk baris gilir daripada dua tindanan: push O(1), pop/peek O(1) secara teramortisasi — pilih apabila operasi pop kerap berlaku. Untuk tindanan daripada dua baris gilir: push O(1), pop O(n) — pilih apabila operasi push jauh lebih kerap daripada pop. Untuk tindanan daripada satu baris gilir: push O(n), pop O(1) — pilih apabila operasi pop mendominasi. Nyatakan pertukaran ini dengan jelas dalam temu duga untuk menunjukkan bahawa anda berfikir melangkaui sekadar “ia berfungsi”.

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?

Apabila elemen 1, 2, 3 dimasukkan melalui push ke dalam tindanan (peti masuk), elemen tersebut berada dalam tertib dari bawah ke atas sebagai 1, 2, 3. Melakukan pop pada semuanya ke dalam tindanan kedua (peti keluar) membalikkan tertib itu: tindanan kedua mempunyai 3 di bawah dan 1 di atas. Melakukan pop daripada tindanan kedua memberikan 1, kemudian 2, kemudian 3 — tepat mengikut tertib penyisipan FIFO. Inilah sebabnya dua pembalikan tepat (dua tindanan) memulihkan FIFO, manakala satu tindanan sahaja 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: Laksanakan Baris Gilir Menggunakan Tindanan

LeetCode 232 ialah masalah langsung “baris gilir daripada dua tindanan”. Penyelesaian yang dijangka ialah pemindahan malas ke peti keluar. Dalam temu duga, nyatakan bahawa setiap elemen bergerak daripada peti masuk ke peti keluar paling banyak sekali, menjadikan semua operasi O(1) secara teramortisasi. Nyatakan bahawa panggilan pop individu boleh menjadi O(n) dalam kes terburuk (apabila peti keluar kosong), tetapi purata bagi n operasi ialah 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: Laksanakan Tindanan Menggunakan Baris Gilir

LeetCode 225 ialah masalah “tindanan daripada baris gilir”. Penyelesaian satu baris gilir dengan putaran semasa push ialah yang paling kemas. Selepas melakukan push pada elemen x, putarkan baris gilir dengan memindahkan semua elemen yang sudah berada di situ ke belakang x. Kosnya ialah O(n) bagi setiap push, tetapi top dan pop menjadi O(1). Nyatakan pertukaran ini dan sahkan bahawa ia sepadan dengan kekangan (contohnya, beban kerja yang mempunyai sedikit operasi push atau banyak operasi 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

Mengembangkan Tiga Timbunan dalam Satu Tatasusunan

Satu lagi cabaran reka bentuk yang berkaitan ialah melaksanakan tiga timbunan menggunakan satu tatasusunan. Satu pendekatan membahagikan tatasusunan kepada tiga bahagian tetap yang sama besar. Pendekatan yang lebih fleksibel menggunakan storan berselang-seli dengan penuding, membesarkan setiap timbunan dalam kawasannya dan menyalin elemen apabila sempadan bertembung. Ini menguji pengurusan tatasusunan dinamik dan sering ditanyakan dalam temu duga peringkat kanan. Pendekatan bahagian tetap lebih mudah, tetapi membazir ruang jika timbunan berkembang secara 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

Kesimpulan Utama: Corak Simulasi

Masalah simulasi timbal balik mengajar prinsip yang lebih luas: apa-apa struktur data boleh dibina daripada struktur data lain jika terdapat penimbalan perantaraan dan pembalikan yang mencukupi. Kos simulasi bergantung pada operasi yang anda optimumkan — anda sentiasa boleh menjadikan push atau pop O(1), tetapi menjadikan kedua-duanya O(1) memerlukan pengamortisan atau beberapa struktur tambahan.

Dalam temu duga, sentiasa tanyakan: 'Operasi yang manakah lebih kerap digunakan?' Ini membantu menentukan pilihan varian pelaksanaan dan menunjukkan pemikiran peringkat kanan tentang keperluan operasi.

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Imbas Kembali Pelajaran

Dalam pelajaran ini, anda telah mempelajari bahawa: baris gilir daripada dua timbunan mencapai pop O(1) secara diamortisasi dengan memindahkan elemen daripada kotak masuk ke kotak keluar hanya apabila perlu, timbunan daripada satu baris gilir mencapai pop O(1) dengan memutarkan baris gilir pada setiap push (push O(n)), dan pilihan operasi yang hendak dijadikan O(1) bergantung pada corak penggunaan. Selepas ini, kita akan meneroka bahagian dalaman peta cincang dan pengendalian perlanggaran.

Percuma untuk bermula

Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 90
Pelajaran: 360

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Simulasi Saling Tindanan dan Baris Gilir” percuma?

Ya — teks penuh “Simulasi Saling Tindanan dan Baris Gilir” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Simulasi Saling Tindanan dan Baris Gilir”?

Laksanakan baris gilir menggunakan dua tindanan dan tindanan menggunakan dua baris gilir, sambil menerangkan kos terlunas bagi setiap pendekatan. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.

Berapa lamakah pelajaran “Simulasi Saling Tindanan dan Baris Gilir” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?

Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

Pelaksanaan Tindanan dan Aplikasinya
Pelaksanaan Baris Gilir dan Deque
Corak Tindanan Monotonik
Simulasi Saling Tindanan dan Baris Gilir

← Kembali ke Persediaan Temu Duga Pengaturcaraan