STRUKTUR DATA Pertemuan 4
Struktur Data prepared by Suyanto
1
Definisi Stack atau Tumpukan adalah suatu struktur data yang terbentuk dari barisan hingga yang terurut dari satuan data. Pada Stack, penambahan dan penghapusan elemennya hanya dapat dilakukan pada satu posisi, yaitu posisi akhir stack. Posisi ini disebut Puncak atau Top dari stack.
Struktur Data prepared by Suyanto
2
Stack. . . Elemen Stack S yang berada pada posisi Top / Puncak dinyatakan dengan : TOP(S). Jika stack S = [S1,S2, . . . ,ST] maka : TOP(S) = ST Sedang banyaknya elemen stack S dinyatakan dengan : NOEL(S) = T. Struktur Data prepared by Suyanto
3
Representasi Stack
S
=
6 5 4 3 2 1
Maks. Stack
D C B A
TOP
TOP(S) = D NOEL(S) = 4
Struktur Data prepared by Suyanto
4
Operasi Stack 1.
CREATE(S) Adalah operator yang menyebabkan Stack S menjadi suatu stack hampa. Jadi NOEL(CREATE(S)) adalah 0 dan TOP(CREATE(S)) adalah tak terdefinisi.
2.
ISEMPTY(S) Adalah operator yang berfungsi untuk memeriksa apakah Stack(S) hampa (kosong) atau tidak. Hasil dari operasi ISEMPTY adalah Boolean yaitu TRUE jika kosong dan FALSE jika isi.
Struktur Data prepared by Suyanto
5
Operasi Stack (lanjutan… 3.
PUSH(S,elemen) PUSH(S,E) adalah operator yang berfungsi menambahkan elemen E ke Stack. Elemen E akan ditempatkan pada posisi TOP(S). Suatu error akan terjadi jika PUSH dioperasikan pada stack yang sudah mencapai maksimal stack.(Overflow)
4.
POP(S) Adalah operator yang berfungsi mengeluarkan atau menghapus elemen TOP(S) dari dalam stack. POP(S) akan mengurangi nilai NOEL(S) dengan 1. Suatu error akan terjadi jika POP(S) dilakukan pada stack yang hampa / kosong. (Underflow) Struktur Data prepared by Suyanto
6
Contoh CREATE(S)
S
PUSH(S,’K’)
TOP(S) = ~ Top = 0 NOEL(S) = 0
1 A
TOP(S) = K Top = 2 NOEL(S) = 2
POP(S)
PUSH(S,’A’)
1 A
2 K
TOP(S) = A Top = 1 NOEL(S) = 1
1 A
Struktur Data prepared by Suyanto
TOP(S) = A Top = 1 NOEL(S) = 1
7
Algoritma 1.
Algoritma PUSH(Stack,item) 1. 2. 3. 4.
2.
IF MaxStk = Top THEN Overflow Top = Top + 1 STACK[Top] = item Exit
Algoritma POP(Stack) 1. 2. 3. 4.
IF Top = 0 THEN Underflow; Exit Item = Stack[Top] Top = Top – 1 Exit
Struktur Data prepared by Suyanto
8
TUGAS 1 1. 2. 3. 4. 5. 6. 7. 8. 9.
CREATE(S) PUSH(S,’K’) IF NOEL(S)>5 THEN GOTO 6 PUSH(S,’E’) GOTO 2 IF ISEMPTY(S) THEN GOTO 9 PRINT TOP(S) PRINT NOEL(S) END Gambarkan keadaan Stack S selama proses diatas berlangsung. Struktur Data prepared by Suyanto
9
TUGAS 2 CREATE(S) WHILE NOEL(S) <= 5 DO PUSH(S,item) PRINT TOP(S) PRINT NOEL(S) ENDWHILE REPEAT POP(S) IF NOEL(S)=2 THEN PRINT TOP(S) UNTIL NOEL(S)=1 PRINT TOP(S) PRINT NOEL(S) PRINT ISEMPTY(S) END Jelaskan hasil dari algoritma diatas, lengkapi dengan hasil output yang mungkin muncul.
Struktur Data prepared by Suyanto
10
APLIKASI STACK Aplikasi stack bisa diterapkan dalam bidang arithmatika yaitu dalam penulisan ekspresi matematika. Dalam penulisannya harus memperhatikan hierarki Operator yaitu : 1. (…) 2. ^ (pangkat) 3. /, *, DIV, MOD 4. +, -
Operator Logika : 1. NOT 2. AND 3. OR
Struktur Data prepared by Suyanto
11
Aplikasi stack... Bentuk notasi penulisan ekspresi matematika 1. Infix Notation A+B 2. Prefix Notation +AB 3. Postfix Notation AB+
Operand, Operator, Operand Operator, Operand, Operand Operand, Operand, Operator
Contoh : Infix (4 – 3) * (12 / 3) Prefix *, - ,4, 3, /, 12, 3 Postfix 4, 3, -, 12, 3, /, * Contoh Soal : 1. Tentukan hasil dari : 12, 7, 3, -, /, 2, 1, 5, +, *, + 2. 5+3^2–8/4+3+6 3. 3, 1, + 2, ^, 7, 4, -, 2, *, +, 5, 4. (A * (( B + D) / E)) - (F * (G + (H / K)))
Struktur Data prepared by Suyanto
12
Algoritma Postfix Untuk membuat notasi infix ke postfix, berikut ini adalah algoritmanya: Algoritma PostFix(Q, P) {Q=Infix, P=Postfix} 1. Masukkan ‘(‘ ke dalam Stack dan ‘)’ ke akhir infix. 2. Telusuri Q sampai elemen yang terakhir 3. Jika menemukan Operand, maka masukkan ke P. 4. Jika menemukan ‘(‘, maka masukkan ke dalam Stack. 5. Jika menemukan operator, maka : 1. Ulangi POP(S) setiap Operator yang sama atau lebih tinggi hirarkinya
dan masukkan ke P 2. Masukkan operator tadi ke Stack. 6.
Jika menemukan ‘)’, maka : 1. Ulangi POP(S) setiap Operator sampai menemukan ‘(‘ dan masukkan ke
dalam P. 2. Hapus ‘(‘ 7.
Selesai
Struktur Data prepared by Suyanto
13
Penerapan Algoritma Postfix Q = A + (B * C – (D / E ^ F) * G) * H Q
STACK
POSTFIX
( 1
A
(
A
2
+
(+
A
3
(
(+(
A
4
B
(+(
AB
5
*
(+(*
AB
6
C
(+(*
ABC
7
-
(+(-
ABC*
8
(
(+(-(
ABC*
9
D
(+(-(
ABC*D
Struktur Data prepared by Suyanto
14
Q
STACK
POSTFIX
10
/
(+(-(/
ABC*D
11
E
(+(-(/
ABC*DE
12
^
(+(-(/^
ABC*DE
13
F
(+(-(/^
ABC*DEF
14
)
(+(-
ABC*DEF^/
15
*
(+(-*
ABC*DEF^/
16
G
(+(-*
ABC*DEF^/G
17
)
(+
ABC*DEF^/G*-
18
*
(+*
ABC*DEF^/G*-
19
H
(+*
ABC*DEF^/G*-H
20
)
...
ABC*DEF^/G*-H*+ Struktur Data prepared by Suyanto
15
Contoh Aplikasi Menara Hanoi Contoh : Tower Menara Hanoi Tujuan : Memindahkan lempengan di A ke C dengan babntuan B. Aturan : 1. Pemindahan = POP pada stack yaitu 1 elemen sekali POP. 2. Yang terkecil selalu diatas yang besar. Ditanya : 1. Berapa langkah untuk memindahkan lempengan tersebut.
Struktur Data prepared by Suyanto
16
1.
Rumus mencari langkah : J = 2n – 1 n = Banyak Lempengan
Struktur Data prepared by Suyanto
17
Q
STACK
POSTFIX
( 1
A
(
A
2
+
(+
A
3
(
(+(
A
4
B
(+(
AB
5
*
(+(*
AB
6
C
(+(*
ABC
7
-
(+(-
ABC*
8
(
(+(-(
ABC*
9
D
(+(-(
ABC*D
Struktur Data prepared by Suyanto
18
Q
STACK
POSTFIX
10
/
(+(-(/
ABC*D
11
E
(+(-(/
ABC*DE
12
^
(+(-(/^
ABC*DE
13
F
(+(-(/^
ABC*DEF
14
)
(+(-
ABC*DEF^/
15
*
(+(-*
ABC*DEF^/
16
G
(+(-*
ABC*DEF^/G
17
)
(+
ABC*DEF^/G*-
18
*
(+*
ABC*DEF^/G*-
19
H
(+*
ABC*DEF^/G*-H
20
)
……HABIS
ABC*DEF^/G*-H*+
Struktur Data prepared by Suyanto
19
ABC-^D/E*F+ 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
A^B-C/D*E+F A^B-C/D*E+F A^B/C-D*E+F A(B-C)^D/E*F+ (A^(B-C))D/E*F+ ((A^(B-C))/D)E*F+ A^(B-C)/D*E+F A^-BC/D*E+F ^A-BC/D*E+F /^A-BCD*E+F +*/^A-BCDEF
1. +*/^A-BCDEF 2. ^-/*+ABCDEF 3. +*/^AB-CDEF
Struktur Data prepared by Suyanto
20
Tugas 1
(A * (( B + D) / E)) - (F * (G + (H / K))) Ubah ke dalam notasi Postfix dengan menggunakan Algoritma Postfix.
Struktur Data prepared by Suyanto
21
Tugas 2 1. Ubah Notasi infix ini ke prefix dan postfix a. A/B-C/D b. (A+B)^3-C*D c. A^(B+C) 2. Ubah notasi Prefix ini ke dalam infix dan postfix a. +-/ABC^DE b. -+DE/XY c. ^+23-CD 3. Ubah notasi Postfix ini ke dalam infix dan prefix a. ABC+b. GH+IJ/* c. AB^CD+-
Struktur Data prepared by Suyanto
22
