My first Magazine pemrograman-kompetitif-dasar | Page 95

8.2 Stack
• 1 2 × 4 × 3 5 ×−
• 5 6 + 1 2 + 4 2 × −×
Carilah hasil dari setiap ekspresi yang diberikan!
Mari kita coba selesaikan ekspresi pertama dengan menggunakan stack .
1.
2.
3.
4.
5.
Pada mulanya, kita memiliki stack kosong : [].
Push angka 1 ke dalam stack . Isi stack : [1].
Push angka 2 ke dalam stack . Isi stack : [1, 2].
Push angka 3 ke dalam stack . Isi stack : [1, 2, 3].
Ditemukan operator +:
• Pop dua kali, didapat nilai 3 dan 2. Isi stack : [1].
• Operasikan 2 + 3 = 5, lalu push hasilnya. Isi stack : [1, 5]
6. Ditemukan operator -:
• Pop dua kali, didapat nilai 5 dan 1. Isi stack : [].
• Operasikan 1 - 5 = -4, dan push hasilnya. Isi stack : [-4]
7. Push angka 4 ke dalam stack . Isi stack : [-4, 4].
8. Ditemukan operator ×:
• Pop dua kali, didapat nilai 4 dan -4. Isi stack : [].
• Operasikan -4 × 4, dan push hasilnya. Isi stack : [-16]
9. Karena rangkaian ekspresi postfix sudah selesai, kita lihat angka yang ada pada stack ,
yaitu -16. Dengan demikian, 1 2 3 + − 4 × = −16.
Anda dapat mencoba menyelesaikan ekspresi-ekspresi lainnya sebagai sarana berlatih.
Aplikasi lainnya dari stack adalah sebagai struktur data yang menampung data saat melaku-
kan depth-first search. Kita akan mempelajari depth-first search pada Bab 9.
8.2.2
Implementasi Stack
Anda dapat mengimplementasikan stack menggunakan sebuah array dan variabel penunjuk.
Variabel penunjuk ini menyatakan indeks array yang menjadi elemen paling atas stack , dan
bergerak maju/mundur sesuai dengan perintah push /pop. Seluruh operasi dapat dilakukan dalam
O(1). Algoritma 41 ini merupakan pseudocode implementasi stack menggunakan array .
Algoritma 41 Implementasi stack menggunakan array .
stack ← new integer[maxSize] . Buat array global stack berukuran maxSize
procedure INITIALIZE S TACK ()
topO f Stack ← 0
4: end procedure . topO f Stack juga merupakan variabel global
1:
2:
3:
85