Bagaimana dan mengapa harus mengantri di dua tumpukan

Halo, Habr!

Posting ini ditulis untuk pemula dalam pemrograman Olimpiade dan pengembang pemula yang sedang bersiap untuk menjalani wawancara algoritmik. Di akhir puzzle bonus. Jika tertarik, saya minta kucing :)

Pertama, mari kita ingat kembali dasar-dasarnya:

Tumpukan

Tumpukan mengimplementasikan prinsip LIFO (Eng. Terakhir masuk - pertama keluar, "terakhir datang, pertama keluar").

Tumpukan memiliki dua operasi utama:

• dorong - dorong item ke tumpukan
• pop - dapatkan elemen dari stack

Tumpukan biasanya diimplementasikan pada array (masih memungkinkan pada daftar tertaut). Anda dapat membaca lebih lanjut tentang stack dan implementasinya di sini.

Antrian

Antrian adalah struktur data dengan akses ke elemen FIFO (masuk pertama, keluar pertama - "pertama datang, pertama pergi")

Antrian memiliki dua metode utama di antarmuka:

• tekan - taruh item di akhir antrian
• pop - dapatkan elemen dari depan antrian

Baca lebih lanjut tentang antrian reguler di sini .

Biasanya mempertimbangkan dua pendekatan dasar untuk implementasi antrian:

1. Pada array
2. Di daftar tertaut

Mengapa stack lebih dingin dari garis

Bayangkan bahwa struktur data kami harus mendukung rangkaian operasi berikut:

• Dukungan Minimum (min)
• Dukungan Maksimal (maks)
• Dukungan Gcd (Pembagi umum terbesar di Inggris - pembagi umum terbesar)
• Dukungan Lcm (multiple paling tidak umum)

Semua operasi ini asosiatif (membentuk semigroup), tetapi tidak satu pun dari mereka yang memiliki elemen terbalik (tidak membentuk grup).

Untuk stack, Anda dapat dengan mudah mendukung salah satu dari operasi berikut: cukup simpan pasangan di atasnya:

$$

$$(elemen, operationResult)$$

di mana elemen kedua dari pasangan adalah hasil dari operasi yang diterapkan ke semua elemen stack.

Di bawah ini adalah contoh implementasi dukungan tumpukan minimum di Python:

class Stack: def __init__(self): self.stack = [] def __bool__(self): return bool(self.stack) def push(self, elem): if self.stack: self.stack.append((elem, min(elem, self.stack[-1][1]))) else: self.stack.append((elem, elem)) def pop(self): return self.stack.pop()[0] def get_min(self): if not self.stack: return math.inf return self.stack[-1][1] 

Sekarang pikirkan tentang bagaimana melakukan trik yang sama dengan antrian? Jika Anda mencoba dengan antrian klasik yang diorganisasikan pada sebuah array, kecil kemungkinan sesuatu akan berhasil. Ini disebabkan oleh fakta bahwa operasi minimum tidak memiliki operasi terbalik (seperti operasi penambahan memiliki operasi pengurangan, misalnya). Seperti yang mungkin sudah Anda duga, maka saya akan berbicara tentang implementasi antrian yang tidak terlalu klasik pada dua tumpukan.

Dua Tumpukan Antrian

Kondisi utama yang harus dipenuhi adalah bahwa semua operasi harus dilakukan untuk O diamortisasi (1).

Ambil dua tumpukan: s1 dan s2.

Operasi push akan selalu dilakukan pada tumpukan s1.

Operasi pop akan diatur sebagai berikut: jika tumpukan s2 kosong, kami mentransfer semua elemen dari s1 ke s2 dengan panggilan berturut-turut ke pop dan push. Sekarang s2 stack berisi elemen dalam urutan terbalik (elemen paling atas adalah elemen pertama yang kita putar).

Jika s2 tidak kosong, kita dengan bodohnya mengeluarkan elemen itu. Segera setelah s2 kosong lagi, kami mengulangi operasi yang sama.

Kode Python:

 class Queue: def __init__(self): self.s1 = Stack() self.s2 = Stack() def push(self, elem): self.s1.push(elem) def pop(self): if not self.s2: while self.s1: self.s2.push(self.s1.pop()) return self.s2.pop() def get_min(self): return min(self.s1.get_min(), self.s2.get_min()) 

Waktu kerja

Operasi push : Kami dengan bodohnya mendorong item ke tumpukan s1. Waktu pengoperasian O (1).

Operasi pop : Untuk setiap elemen, kami melakukan tidak lebih dari satu transfer dari tumpukan ke tumpukan, oleh karena itu, waktu kerja yang diamortisasi adalah O (1).

Operasi get_min : Minima dikenal untuk tumpukan s1 dan s2, jadi kami hanya mengambil minimum dari minima. Waktu pengoperasian O (1).

Tantangan Bonus

Diberikan urutan angka N. Angka M <N diberikan. Diperlukan dalam waktu linier untuk menemukan segmen panjang M di mana produk min * maks maksimum.

Kesimpulan

Terima kasih sudah membaca sampai akhir!

Jika Anda tertarik dengan topik ini, Anda dapat membaca cara membuat antrean persisten di dua tumpukan di sini , atau menunggu rilis topik berikutnya.

Tulis di komentar tugas-tugas apa pada dua tumpukan yang harus Anda selesaikan dalam wawancara atau kontes.