Struktur Data — Tumpukan

Dalam pemrograman, kita harus bekerja dengan banyak sekali data. Oleh karena itu kita perlu menyimpan dan mengatur data secara efisien. Ini adalah saat struktur data menjadi berguna. Kita dapat menggunakan struktur data untuk menyimpan, mengatur, memproses, dan mengambil data. Struktur data selanjutnya dapat dibagi menjadi 2 kategori tergantung pada bagaimana data disusun.

Pada artikel ini, saya akan berbicara tentang struktur linier ( Tumpukan ). Dibandingkan dengan struktur non-linier, konsep di balik struktur linier relatif lebih mudah dipahami. Beberapa contoh struktur linear tersebut adalah Stack, Queues, Deques, dan Lists. Kami akan melalui masing-masing struktur data ini satu per satu. Struktur linier ini dapat dianggap memiliki 2 ujung. (depan & belakang | kiri & kanan | atas & bawah) Beberapa struktur linier memungkinkan penyisipan atau penghapusan elemen hanya pada satu ujung, sementara beberapa struktur mengizinkannya di kedua ujungnya.

1. Tumpukan

• Jadi pada dasarnya, tumpukan adalah kumpulan elemen yang dipesan di mana penyisipan dan penghapusan item dilakukan di ujung yang sama. Akhir ini umumnya dikenal sebagai "Top". Juga, ujung yang berlawanan dengan bagian atas dikenal sebagai "Bawah"
• Selain itu, item yang lebih baru berada di dekat bagian atas, sedangkan item yang lebih lama berada di bagian bawah. Oleh karena itu urutan pengeluaran item dari stack akan menjadi kebalikan dari urutan pemasukan item ke dalam stack.
• Sekarang setelah kita memiliki pemahaman yang baik tentang perilaku tumpukan, mari kita lihat beberapa operasi penting yang terkait dengan struktur data tumpukan.
• push (element) — Metode push digunakan untuk memasukkan item ke bagian atas tumpukan.
• pop ()- Metode pop digunakan untuk menghapus bagian atas — sebagian besar item dari tumpukan
• peek () — Metode peek digunakan untuk melihat item paling atas saat ini dari tumpukan.
• size () — Mengembalikan jumlah item yang ada di tumpukan
• is_empty () — Metode ini berguna untuk memeriksa apakah stack kosong atau tidak
• Perhatikan bahwa di sini, akhir daftar dianggap sebagai bagian atas tumpukan. (Kompleksitas waktu — O(1)) Kita dapat menganggap awal daftar sebagai bagian atas tumpukan, namun, ini tidak akan sangat efisien karena kompleksitas waktu akan menjadi O(n) saat kita mendorong atau mengeluarkan item.
• Saat kami menganggap akhir daftar sebagai bagian atas tumpukan


• Sekarang setelah kita mengetahui cara mengimplementasikan tumpukan, sekarang mari kita lihat beberapa skenario di mana penggunaan struktur data tumpukan menjadi sangat penting.
• Konversi sistem bilangan
• Pertama-tama mari kita lihat bagaimana kita dapat mengonversi bilangan desimal menjadi biner menggunakan tumpukan.

• Sekarang mari kita kembangkan algoritme di atas untuk mengonversi bilangan desimal ke sistem bilangan apa pun antara 2 dan 16.


Hampir setiap bahasa pemrograman di luar sana menggunakan tanda kurung dalam sintaksnya. Oleh karena itu, jika kita tidak menggunakan tanda kurung secara seimbang, kesalahan sintaks dapat terjadi.

• Pada tahap pertama dari soal ini, saya hanya akan mempertimbangkan satu jenis tanda kurung, misalnya (). Yang perlu kita periksa adalah apakah himpunan tanda kurung seimbang atau tidak. Jika seimbang kita harus mengembalikan benar, jika tidak salah.
• ( ) — seimbang | ( ( ) ) — seimbang | ( ( ( )( ) ) ) — seimbang
• ( ( ) tidak seimbang | ( ) ( ) ( — tidak seimbang | ( ( ( ) ) ( ) — tidak seimbang

• ( [ ] ) — seimbang | ( ( ) { } ) — seimbang | ( ( [ { } [ ] ] ) ) — seimbang
• ( ( ) tidak seimbang | ( ) { } ]— tidak seimbang | ( ( { } [ [ ) — tidak seimbang


3. Balikkan string menggunakan tumpukan



4. Infiks | Notasi Postfix & Awalan

Dalam ilmu komputer, kita harus berurusan dengan banyak ekspresi aritmatika. Ekspresi terdiri dari operator (+, -, *, / etc) operan (A, B, c, d, 1, 2,… ), dan simbol seperti tanda kurung.

• Infix Notation — Dalam notasi ini operator ditempatkan di antara operand. (<operan> <operator> <operan>)
• Jika ekspresi hanya terdiri dari satu operator (mis: 2 + 3, 4 * 6) kita dapat langsung menyelesaikan ekspresi tersebut. Namun jika ekspresi memiliki lebih dari satu operator maka kita tidak dapat menyelesaikannya secara langsung karena ekspresi yang ambigu. Pertimbangkan ungkapan ini 1 + 4 * 5. Jika kita melakukan penjumlahan terlebih dahulu, kita mendapatkan jawabannya sebagai [ ( 1 + 4 ) * 5 ] = 25 dan jika kita melakukan perkalian terlebih dahulu, kita mendapatkan jawabannya sebagai [1 ​​+ (4 * 5 )] = 21. Seperti yang Anda lihat ada beberapa ambiguitas dalam notasi ini. Oleh karena itu untuk mengatasi ini kami menggunakan sesuatu yang disebut "operator didahulukan". Menurut operator perkalian harus didahulukan terlebih dahulu sebelum penjumlahan. Jadi jawaban yang benar seharusnya 21, bukan 25.
• Pada dasarnya, untuk menyelesaikan ekspresi yang ditulis dalam notasi infiks kita harus mengikuti seperangkat aturan, serta kita perlu menambahkan tanda kurung juga. Jadi notasi ini bisa memakan lebih banyak memori saat menyelesaikannya. Jadi untuk mengatasi tantangan ini para ilmuwan telah menemukan dua notasi lain, awalan dan akhiran.
• Dalam notasi awalan, operator ditempatkan sebelum operan, (<operator><operand> <operan>) sedangkan dalam notasi postfix operator ditempatkan setelah operan. (<operan> <operan><operator>)
• Dibandingkan dengan notasi infiks, dua notasi lainnya cukup sulit untuk dibaca dan dipahami oleh manusia. Namun karena kedua notasi ini tidak memiliki simbol tambahan seperti tanda kurung, dan tidak mengandung ambiguitas, ekspresi yang ditulis dalam 2 format ini dapat dengan mudah dibaca oleh komputer.


• Mengevaluasi ekspresi postfix : Ketika kita harus mengevaluasi ekspresi postfix kita harus memulai pemindaian dari kiri sampai kita menemukan operator. Setelah kami menemukan operator, kami harus melakukan operasi aljabar yang relevan pada 2 operan pertama di sebelah kiri operator.

• Pertama-tama perlu menghapus semua spasi di masukan kami. Oleh karena itu kita perlu menggunakan metode split. Kemudian kita perlu memindai ekspresi kita dari kiri ke kanan. Jika kami menemukan nomor, kami harus mendorongnya ke dalam tumpukan. Jika kami bertemu dengan seorang operator, maka kami harus mengeluarkan 2 item teratas di tumpukan kami. Kemudian kita harus memanggil fungsi pembantu kita untuk melakukan operasi aritmatika. Setelah itu kami akan mendorong hasilnya ke dalam tumpukan. Setelah selesai dengan pemindaian, kami akan mengembalikan apa yang tersisa di tumpukan kami, yang merupakan jawaban untuk ekspresi postfix yang dievaluasi.


• Sekarang mari kita lihat bagaimana kita bisa mengonversi ekspresi dalam format infix ke postfix menggunakan Python.