BAB 3 - Tumpukan [Stack]

Tumpukan adalah kumpulan elemen-elemen data yang disimpan dalam satu laju linier. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu pada posisi ATAS (TOP) tumpukan.Elemen-elemen dalam tumpukan dapat bertipe data integer, real, record dalam bentuk sederhana atau terstruktur. Tumpukan disebut juga “Push Down Stack” yaitu penambahan elemen baru (PUSH) dan penghapusan elemen dari Tumpukan (POP). Sistem pada pengaksesan pada Tumpukan menggunakan sistem LIFO (Last In First Out), artinya elemen yang terakhir masuk itu yang akan pertama dikeluarkan dari Tumpukan.

Contoh Tumpukan Kosong, Tumpukan dengan 1 elemen dan Tumpukan dengan N elemen. Tumpukan Kosong Tumpukan 1 Elemen Tumpukan N Elemen

TOP = 0 ‘A’ TOP = 1

‘D’ TOP = N

‘C’

‘B’

‘A’

Kamus Data Tumpukan Ada beberapa cara pendeklarasian struktur data Tumpukan, salah satunya dengan menggunakan tatasusunan linear (larik) dan sebuah variabel, yang dikemas dalam tipe data record. Berikut pendeklarasian struktur data Tumpukan dalam kamus data: Kamus Const Maks = 10 {kapasitas maksimal dalam Tumpukan} Type JenisElemen : Char Tumpukan = Record Elemen : Array [1..Maks] Of JenisElemen Atas : 0..Maks EndRecord Tumpukan adalah struktur data bertipe record yang terdiri dari field Elemen bertipe larik dengan indek 1 sampai dengan Maks, Atas bertipe integer berkisar dari 0 (saat kosong) sampai dengan Maks.

Operasi-Operasi Dasar pada Tumpukan Operasi yang sering diterapkan pada struktur data Tumpukan adalah PUSH dan POP. Operasi-operasi dasar yang dapat diterapkan adalah sebagai berikut: CREATESTACK (S), membuat Tumpukan baru S, dengan jumlah elemen kosong; MAKENULL (S), mengosongkan Tumpukan S, jika ada elemen maka semua elemen

dihapus; EMPTY, Tumpukan Kosong?, menguji apakah Tumpukan Kosong; PUSH (X,S), memasukan elemen baru X ke dalam Tumpukan S; POP (S), mengeluarkan elemen posisi atas pada Tumpukan S.

Ilustrasi Operasi POP dan PUSH terhadap TUMPUKAN Pada proses PUSH, Tumpukan harus diperiksa apakah jumlah elemen sudah mencapai maksimum atau tidak. Jika sudah mencapai maksimum maka OVERFLOW. Sedangkan pada proses POP, Tumpukan harus diperiksa apakah ada elemen yang hendak dikeluarkan atau tidak. Jika tidak ada maka UNDERFLOW.

Nomor Operasi Isi Tumpukan Nilai TOP

1 CREATESTACK (S) Kosong 0

2 PUSH (‘a’, S) ‘a’ 1

3 PUSH (‘b’, S) ‘a’ ‘b’ 2

4 PUSH (‘c’, S) ‘a’ ‘b’ ‘c’ 3

5 POP (S) ‘a’ ‘b’ 2

6 PUSH (‘d’, S) ‘a’ ‘b’ ‘d’ 3

7 PUSH (‘e’, S) ‘a’ ‘b’ ‘d’ ‘e’ 4

8 POP (S) ‘a’ ‘b’ ‘d’ 3

9 POP (S) ‘a’ ‘b’ 2

10 POP (S) ‘a’ 1

Operasi Dasar Tumpukan dalam Bahasa Pascal Program OperasiTumpukan; Const Maks = 10; Type JenisElemen = Char; Tumpukan = Record Elemen : Array [1..Maks] Of JenisElemen; Top : 0..Maks; End; Procedure CreateStack (Var S : Tumpukan); Begin S.Top := 0; End; Procedure MakeNull (Var S : Tumpukan); Begin S.Top := 0; End;

Procedure Push (ElemenBaru : JenisElemen; Var S : Tumpukan); Begin If (S.Top = Maks) Then Write (‘Overflow ...’) Else Begin S.Top := S.Top + 1; S.Elemen[S.Top] := ElemenBaru; End; End; Procedure Pop (Var S : Tumpukan; Var NilaiElemen : JenisElemen); Begin If (S.Top = 0) Then Write (‘Underflow ...’) Else Begin {untuk menyimpan elemen yang diambil} NilaiElemen := S.Elemen[S.Top]; S.Top := S.Top – 1; End; End;

{akan mengembalikan nilai TRUE jika tidak ada elemen dalam Tumpukan atau FALSE jika ada elemen dalam Tumpukan} Function IsEmpty (Var S : Tumpukan) : Boolean; Begin IsEmpty := S.Top = 0; End;

Notasi Aritmatik (Infix, Prefix dan Postfix) Notasi Aritmatik biasa ditulis dalam notasi Infix, misal A + B – C. Notasi infix mudah dimengerti , hanya saja dalam notasi infix perlu diperhatikan prioritas pengerjaan karena berhubungan dengan hirarki operator pada komputer. Prioritas pengerjaannya adalah sebagai berikut: 1. Tanda Kurung : ( ..... ) 2. Eksponensial atau Pangkat : ^ 3. Perkalian, Pembagian : *, / 4. Penjumlahan, Pengurangan : +, - Contoh: (A – B) * (C + D) Prioritas pengerjaan soal di atas adalah sebagai berikut: Dalam kurung yang paling kiri : (A – B) Dalam kurung yang kedua : (C + D) Perkalian hasil pengurangan dengan hasil penjumlahan Notasi Infix untuk penulisan artimatik, biasa diubah ke dalam Notasi Prefix atau Postfix saat kompilasi. Notasi Prefix maupun Postfix akan lebih mudah dikerjakan oleh komputer, karena tidak perlu mencari urutan pengerjaan seperti pada Notasi Infix....

Prefix adalah keadaan dimana simbol operator diletakan sebelum dua operand. Postfix adalah keadaan dimana simbol operator diletakan sesudah dua operand. Aturan Notasi Infix, Prefix dan Postfix: Notasi Infix : operand operator operand A + B Notasi Prefix : operator operand operand + A B (Polish Notation – PN)

Notasi Postfix : operand operand operator A B + (Reveser Polish Notation – RPN)

Contoh 1 Infix ke Prefix : (A + B) – (C * D) Untuk pengerjaan Infix, perlu diperhatikan urutan sebagai berikut: 1. Pengerjaan dalam kurung ke 1 : (A + B), Prefix-nya : + A B 2. Pengerjaan dalam kurung ke 2 : (C * D), Prefix-nya : * C D 3. Terakhir adalah operator -, : + A B - * C D, Prefix-nya : - + A B * C D

Contoh 2 Infix ke Postfix : (A + B) – (C * D) Untuk pengerjaan Infix, perlu diperhatikan urutan sebagai berikut: 1. Pengerjaan dalam kurung ke 1 : (A + B), Postfix-nya : A B + 2. Pengerjaan dalam kurung ke 2 : (C * D), Postfix-nya : C D * 3. Terakhir adalah operator -, : A B + - C D *, Prefix-nya : A B + C D * -

Contoh 3 Prefix ke Infix : + / * A B C D Untuk pengerjaan Prefix, mencari operator dimulai operand terkanan sebagai berikut: 1. Cari operator ke 1 : *

Ambil dua operand sebelumnya A dan B, Infix-nya : (A * B) 2. Cari operator ke 2 : /

Ambil dua operand sebelumnya (A * B) dan C, Infix-nya : ((A * B) / C) 3. Cari operator ke 3 : +

Ambil dua operand sebelumnya ((A * B) / C) dan D, Infix-nya : ((A * B) / C) + D Contoh 4 Prefix ke Postfix : + / * A B C D Untuk pengerjaan Prefix, mencari operator dimulai operand terkanan sebagai berikut: 1. Cari operator ke 1 : *

Ambil dua operand sebelumnya A dan B, Postfix-nya : A B * 2. Cari operator ke 2 : /

Ambil dua operand sebelumnya A B * dan C, Postfix-nya : A B * C / 3. Cari operator ke 3 : +

Ambil dua operand sebelumnya A B * C / dan D, Postfix-nya : A B * C / D +

Contoh 5 Postfix ke Infix : A B C D * / - Untuk pengerjaan Postfix, mencari operator dimulai operand terkiri sebagai berikut: 1. Cari operator ke 1 : *

Ambil dua operand sebelumnya C dan D, Infix-nya : (C * D) 2. Cari operator ke 2 : /

Ambil dua operand sebelumnya B dan (C * D), Infix-nya : (B / (C * D)) 3. Cari operator ke 3 : -

Ambil dua operand sebelumnya A dan (B / (C * D)), Infix-nya : A - (B / (C * D)) Contoh 6 Postfix ke Prefix : A B C D * / - Untuk pengerjaan Postfix, mencari operator dimulai operand terkiri sebagai berikut: 1. Cari operator ke 1 : *

Ambil dua operand sebelumnya C dan D, Prefix-nya : * C D 2. Cari operator ke 2 : /

Ambil dua operand sebelumnya B dan * C D, Prefix-nya : / B * C D 3. Cari operator ke 3 : -

Ambil dua operand sebelumnya A dan / B * C D, Prefix-nya : - A / B * C D

Ubah Notasi Infix ini ke Prefix dan Postfix ! a. A / B – C / D b. (A + B) ^ 3 – C * D c. A ^ (B + C)

Ubah Notasi Prefix ini ke dalam Infix dan Postfix ! a. + - / A B C D ^ D E b. - + D E / X Y c. ^ + 2 3 – C D Ubah Notasi Postfix ini ke dalam Infix dan Prefix ! a. A B C + - b. G H + I J / * c. A B ^ C D + -