My first Magazine pemrograman-kompetitif-dasar | Page 94

8 Struktur Data Dasar
Gambar 8.2: Ilustrasi penambahan dan penghapusan data pada stack
Stack memiliki operasi sebagai berikut:
•
•
•
•
push, yaitu memasukkan elemen baru ke bagian atas tumpukan.
pop, yaitu membuang elemen paling atas tumpukan.
top, yaitu mengakses elemen paling atas tumpukan.
isEmpty, yaitu memeriksa apakah tumpukan saat ini kosong.
8.2.1
Aplikasi Stack
Stack digunakan dalam berbagai kasus, salah satunya eksekusi fungsi pada sejumlah bahasa
pemrograman. Biasanya, eksekusi fungsi terutama fungsi rekursif menggunakan struktur data
stack . Pemanggilan fungsi rekursif yang menambah kedalaman berarti melakukan "push " pada
stack eksekusi fungsi. Fungsi yang dieksekusi adalah fungsi di paling atas stack . Setelah fungsi
di paling atas selesai, dilakukan "pop " dan eksekusi fungsi dilanjutkan ke fungsi yang ada di
paling atas stack berikutnya. Oleh sebab itu, ketika pemanggilan fungsi terlalu dalam, terjadi
stack overflow.
Selain digunakan pada fungsi rekursi, stack juga digunakan pada kalkulator ekspresi mate-
matika dalam notasi postfix. Notasi postfix adalah notasi penulisan ekspresi matematika dengan
urutan operand, operand, dan operator. Contoh:
• "1 2 +" bermakna "1 + 2"
• "1 2 3 + −" bermakna "1 − (2 + 3)"
• "1 2 3 + − 4 ×" bermakna "(1 − (2 + 3)) × 4"
Notasi yang biasa kita gunakan adalah notasi infix, yaitu dengan urutan operand, operator, dan
operand.
Jika kita diberikan sebuah ekspresi dalam notasi postfix, nilai akhirnya dapat dicari dengan
skema kerja stack sebagai berikut:
• Pada awalnya, inisialisasi sebuah stack kosong.
• Proses ekspresi dari kiri ke kanan:
1. Jika ditemukan operand, push ke dalam stack .
2. Jika ditemukan operator, pop dua kali untuk mendapat dua operand teratas stack ,
hitung, lalu push kembali ke dalam stack .
• Satu-satunya nilai terakhir di dalam stack adalah hasil ekspresinya.
Contoh Soal 8.1: Menghitung ekspresi postfix
Anda diberikan sebagai berikut:
• 1 2 3 + − 4 ×
84