 |
| Credit: dev.to |
Apa itu STACK?
Stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO, yaitu data yang terakhir kali dimasukkan akan pertama kali keluar dari tumpukan tersebut. Tumpukan dapat diimplementasikan sebagai representasi berkait atau kontigu.
Implementasi stack dapat menggunakan array atau linked list(sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu). Implementasi dengan array, kemungkinan stack dalam kondisi penuh. Implementasi dengan linked list, stack tidak pernah penuh
Ilustrasi Stack
Operasi Pop mengambil elemen/item dari stack
Elemen Stack
Stack terdiri dari :
1. Elemen: item yang diletakkan ke penyimpan
2.Top of Stack (TOS): informasi/index elemen teratas
Stack pada array
Stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO, yaitu data yang terakhir kali dimasukkan akan pertama kali keluar dari tumpukan tersebut. Tumpukan dapat diimplementasikan sebagai representasi berkait atau kontigu.
Implementasi stack dapat menggunakan array atau linked list(sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu). Implementasi dengan array, kemungkinan stack dalam kondisi penuh. Implementasi dengan linked list, stack tidak pernah penuh
Ilustrasi Stack
Elemen Stack
Stack terdiri dari :
1. Elemen: item yang diletakkan ke penyimpan
2.Top of Stack (TOS): informasi/index elemen teratas
Stack pada array
Operasi pada stack
1. Inisialisasi : untuk inisialisasi awal stack
2. Push : untuk menyimpan item pada stack
3. Pop : untuk mengambil item dari stack
4. Penuh : untuk cek stack dalam kondisi penuh
5. Kosong : untuk cek stack dalam kondisi kosong
1. OPERASI INISIALISASI
Tujuan: menginisialisasi agar TOS (Top Of Stack) menunjuk ke indeks array awal (indeks 0)
1. Inisialisasi : untuk inisialisasi awal stack
2. Push : untuk menyimpan item pada stack
3. Pop : untuk mengambil item dari stack
4. Penuh : untuk cek stack dalam kondisi penuh
5. Kosong : untuk cek stack dalam kondisi kosong
1. OPERASI INISIALISASI
Tujuan: menginisialisasi agar TOS (Top Of Stack) menunjuk ke indeks array awal (indeks 0)
2. OPERASI PENUH
- Melakukan pengecekan apakah stack Penuh atau Tidak (Jika penuh return value=1, sebaliknya value=0)
- Digunakan saat melakukan operasi PUSH agar tidak terjadi error stack over flow (melimpah)
- Melakukan pengecekan apakah stack Penuh atau Tidak (Jika penuh return value=1, sebaliknya value=0)
- Digunakan saat melakukan operasi PUSH agar tidak terjadi error stack over flow (melimpah)
3. OPERASI KOSONG
- Melakukan pengecekan apakah stack Kosong atau Tidak
- Jika kosong return value=1, sebaliknya value=0
- Digunakan saat melakukan operasi POP untuk agar tidak terjadi error saat mengambil item
4. OPERASI PUSH
- Untuk menyimpan data pada posisi teratas
- Bila array penuh, tidak dapat melakukan operasi Push
- Setelah dilakukan penyimpanan, posisi TOS di increment
5. OPERASI POP
- Mengambil data pada posisi teratas
- Bila array Kosong tidak dapat dilakukan operasi PoP
- Sebelum mengambil data TOS di-decrement
Penerapan Stack dalam penyelesaian ekspresi matematik
➣ Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung. Contoh : +AB, – +ABC, * + AB – CD.
➣ Infix adalah cara penulisan ungkapan dengan meletakkan operator di antara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi. Contoh : A+B, A+B-C, (A+B)*(C-D).
➣ Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung. Contoh : AB + , AB + C – , AB + CD -*.
Notasi infix ke posfix dengan stack
➣ Notasi infix dibaca satu per satu
➣ Jika berupa operand maka langsung dicetak dan tidak disimpan
➣ Stack hanya digunakan untuk menyimpan operator
➣ Operator mempunyai tingkatan level dengan urutan (dari level tertinggi ke terendah) : ‘^’, ‘*’ dan ‘/’, ‘+’ dan ‘-’
➣ Jika operator maka mengikuti aturan sbb: Jika notasi ‘(‘ PUSH ke stack
➣ Jika notasi ‘)’ POP dan cetak s/d tanda ‘)’ tetapi tidak dicetak
➣ Jika operator, cek bila stack Kosong atau level operator > level operator TOS maka PUSH
➣ Lainnya POP dan cetak lalu PUSH, ulangi perbandingan
➣ Jika notasi infix sudah berakhir, POP stack sampai Kosong
Menghitung hasil operasi postfix
1. Stack akan menyimpan operand dan hasil operasi
2. Siapkan variabel opLeft dan opRight untuk menyimpan operan kiri dan kanan
3. Dibaca satu persatu, misalnya : 34+
a. Ketemu operand ‘3’, maka PUSH ‘3’
b. Ketemu operand ‘4’, maka PUSH ‘4’
c. Ketemu Operator ‘+’, maka POP ‘4’ ke opRight, lalu POP ‘3’ ke opLeft, kemudian lakukan operasi ‘+’
d. Hasil operasinya ‘7’ lalu PUSH ke stack
4. Bila notasi berakhir, POP stack sebagai hasil operasi
Algoritma hasil postfix
1. Baca notasi postfix satu per satu
2. Jika notasi adalah operan maka PUSH ke stack
3. Jika notasi adalah operator maka
1. POP ke OpRight
2. POP ke OpLeft
3. Hasil = OpLeft operator OpRight
4. PUSH Hasil
4. Jika notasi postfix berakhir, POP stack sebagai hasil operasi
- Mengambil data pada posisi teratas
- Bila array Kosong tidak dapat dilakukan operasi PoP
- Sebelum mengambil data TOS di-decrement
Penerapan Stack dalam penyelesaian ekspresi matematik
 |
| Credit: Slideserve by Waggoner Buckingham |
➣ Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung. Contoh : +AB, – +ABC, * + AB – CD.
➣ Infix adalah cara penulisan ungkapan dengan meletakkan operator di antara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi. Contoh : A+B, A+B-C, (A+B)*(C-D).
➣ Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung. Contoh : AB + , AB + C – , AB + CD -*.
Notasi infix ke posfix dengan stack
➣ Jika berupa operand maka langsung dicetak dan tidak disimpan
➣ Stack hanya digunakan untuk menyimpan operator
➣ Operator mempunyai tingkatan level dengan urutan (dari level tertinggi ke terendah) : ‘^’, ‘*’ dan ‘/’, ‘+’ dan ‘-’
➣ Jika operator maka mengikuti aturan sbb: Jika notasi ‘(‘ PUSH ke stack
➣ Jika notasi ‘)’ POP dan cetak s/d tanda ‘)’ tetapi tidak dicetak
➣ Jika operator, cek bila stack Kosong atau level operator > level operator TOS maka PUSH
➣ Lainnya POP dan cetak lalu PUSH, ulangi perbandingan
➣ Jika notasi infix sudah berakhir, POP stack sampai Kosong
Menghitung hasil operasi postfix
1. Stack akan menyimpan operand dan hasil operasi
2. Siapkan variabel opLeft dan opRight untuk menyimpan operan kiri dan kanan
3. Dibaca satu persatu, misalnya : 34+
a. Ketemu operand ‘3’, maka PUSH ‘3’
b. Ketemu operand ‘4’, maka PUSH ‘4’
c. Ketemu Operator ‘+’, maka POP ‘4’ ke opRight, lalu POP ‘3’ ke opLeft, kemudian lakukan operasi ‘+’
d. Hasil operasinya ‘7’ lalu PUSH ke stack
4. Bila notasi berakhir, POP stack sebagai hasil operasi
Algoritma hasil postfix
1. Baca notasi postfix satu per satu
2. Jika notasi adalah operan maka PUSH ke stack
3. Jika notasi adalah operator maka
1. POP ke OpRight
2. POP ke OpLeft
3. Hasil = OpLeft operator OpRight
4. PUSH Hasil
4. Jika notasi postfix berakhir, POP stack sebagai hasil operasi
Terima kasih telah membaca