struktur data part 4

Pertemuan 3Heny Pratiwi, S.Kom., M.Pd.

Teknik InformatikaSemester 2

Setelah mengikuti perkuliahan ini mahasiswa semester 2S1 Teknik Informatika STMIK Widya Cipta Dharma mampumeningkatkan pemahaman struktur data dan penanganan databagi perencanaan algoritma dan penyusunan program, misalnyasebagai dasar teknik dari sebuah penyusunan database.

Mahasiswa dapat menjelaskan Pengertian Stack dan Aplikasinya (Tumpukan)

2

Heny Pratiwi, S.Kom., M.Pd.

Standar Kompetensi

Kompetensi Dasar

Tumpukan (Stack) dan Aplikasinya

3

Heny Pratiwi, S.Kom., M.Pd.

Uraian Materi

1. Definisi Tumpukan2. Kamus Data Tumpukan3. Operasi-Operasi Dasar Pada Tumpukan4. Notasi Aritmetik (Infix, Prefix dan Postfix)5. Rekursif

M a t e r i

Heny Pratiwi, S.Kom., M.Pd.

Kumpulan elemen-elemen data yang disimpan dalam satu

lajur linier

4

Kumpulan hanya boleh diakses pada satu lokasi saja yaitu pada posisi ATAS (TOP) tumpukan.

Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation), dan

algoritma penjejahan balik (backtrack)

Heny Pratiwi, S.Kom., M.Pd.

• Tumpukan disebut juga Push down Stack

• Yaitu penambahan elemen baru (PUSH) dan penghapusan elemen dari tumpukan (POP)

• Sistem pengaksesan pada Tumpukan menggunakan sistem LIFO (Last In First Out) artinya elemen yang terakhir masuk akan jadi yang pertama keluar dari tumpukan.

5

Heny Pratiwi, S.Kom., M.Pd.

Contoh Tumpukan

6

Heny Pratiwi, S.Kom., M.Pd.

2. Kamus Data Tumpukan

Kamus DataConst

makstum = 80; {Kapasitas maksimal dari Tumpukan}

Type

jenis elemen = char;

tumpukan = record;

elemen : array[1..makstum] of jeniselemen;

atas : 0..makstum;

End;

7

Heny Pratiwi, S.Kom., M.Pd.

3. Operasi-Operasi Dasar Pada Tumpukan

a. CREATESTACK(S) : Membuat tumpukan baru S, dengan jumlah elemen kosong

b. MAKENULL(S) : Mengosongkan tumpukan S, jika ada elemen maka semua elemen dihapus.

c. EMPTY : Menguji apakah tumpukan itu kosong

d. PUSH (x,S) : Memasukkan elemen baru x ke dalam tumpukan S

e. POP(S) : mengeluarkan elemen posisi atas pada tumpukan S

8

Heny Pratiwi, S.Kom., M.Pd.

Ilustrasi operasi POP dan PUSH terhadap Stack

No OPERASI ISI TUMPUKAN

NILAI TOP

1 CREATESTACK(S) : <kosong> 02 PUSH (‘a’, S) : a 13 PUSH (‘b’, S) : a b 24 PUSH (‘c’, S) : a b c 35 POP (S) : a b 26 PUSH (‘d’, S) : a b d 37 PUSH (‘e’, S) : a b d e 48 POP (S) : a b d 39 POP (S) : a b 210 POP (S) : a 1

9

Heny Pratiwi, S.Kom., M.Pd.

Apa yang terjadi bila dilakukan POP (S) sebanyak dua kali ? Underflow

Apa yang terjadi bila dilakukan PUSH (x, S) sebanyak sepuluh kali, jika kapasitas tumpukan adalah 5 lagi? Overflow, artinya tumpukan penuh tidak ada elemen yang dapat dimasukkan ke dalam tumpukan.

10

Heny Pratiwi, S.Kom., M.Pd.

Contoh : (A - B) * (C + D)

• Dalam kurung yang paling kiri : (A-B)• Dalam kurung yang kedua : (C+D)• Perkalian hasil pengurangan dengan

hasil penjumlahan

11

Heny Pratiwi, S.Kom., M.Pd.

• Prefix : Keadaan dimana simbol operator diletakkan sebelum dua operand.

• Notasi Infix untuk penulisan aritmatik, biasa diubah kedalam notasi prefix atau postfix saat kompilasi.

• Postfix : Keadaan dimana simbol operator diletakkan sesudah dua operand

12

INFIXPREFIX POSTFIX

Heny Pratiwi, S.Kom., M.Pd.

• Notasi Infix : operand operatoroperand A + B

• Notasi Prefix : operator operand operand + A B (disebut juga Polish Notation – PN)

• Notation Postfix : operand operand operator A B + (disebut juga Reveser Polish Notation-RPN)

13

Heny Pratiwi, S.Kom., M.Pd.

INFIX ke PREFIX : (A+B) – (C*D)

a. (A+B), prefik nya +ABb. (C*D), prefik nya *CDc. Operator -

Maka, Prefiknya adalah- + A B * C D

14

Heny Pratiwi, S.Kom., M.Pd.

INFIX ke POSTFIX : (A+B) – (C*D)

a. (A+B), prefik nya AB+b. (C*D), prefik nya CD*c. Operator -

Maka, Postfiknya adalahA B + C D * -

15

Heny Pratiwi, S.Kom., M.Pd.

PREFIX ke INFIX : +/*ABCD

a. Cari operator 1 : * ambil 2 operand sebelumnya A dan B, maka infiknya A*B

b. (A*B)/Cc. ((A*B)/C)+D

Maka, Infixnya adalah((A*B)/C)+D

16

Heny Pratiwi, S.Kom., M.Pd.

PREFIX ke POSTFIX : +/*ABCD

a. Cari operator 1 : * ambil 2 operand sebelumnya A dan B, maka infiknya AB*

b. AB*C/c. AB*C/D+

Maka, Postfixnya adalahAB*C/D+

17

Heny Pratiwi, S.Kom., M.Pd.

POSTFIX ke INFIX : ABCD*/-

a. C*Db. B/C*Dc. A-B/C*D

Maka, Infixnya adalahA-B/C*D

18

Heny Pratiwi, S.Kom., M.Pd.

POSTFIX ke PREFIX : ABCD*/-

a. *CDb. /B*CDc. -A/B*CD

Maka, Prefixnya adalah-A/B*CD

19

Heny Pratiwi, S.Kom., M.Pd.

Evaluasi Nilai Postfix menggunakan Tumpukan

• Infix (2-4*3)+1• Ke Postfix Menjadi : 243*-1+

20

2

42

342

122 -10

1-10 -9

2 4 3 * - 1 +

Heny Pratiwi, S.Kom., M.Pd.

Evaluasi Nilai Prefix Menggunakan Tumpukan

• Infix (2-4*3)+1• Ke Prefix Menjadi : +-2*431

21

1

31

431

121

2121

-101 -9

1 3 4 * 2 - +

Heny Pratiwi, S.Kom., M.Pd.

5. Rekursif

• Fungsi/prosedur Rekursif adalah Fungsi/prosedur yang memanggil dirinya sendiri, contoh : Faktorial

• Pemanggilan dirinya sendiri menyebabkan fungsi melakukan proses pengulangan (looping).

Badan fungsi dibagi atas dua bagian :1. Base : Kondisi Berhenti2. Recurrence : Proses pengulangan (pemanggilan

dirinya sendiri)

22

Heny Pratiwi, S.Kom., M.Pd.

Program Faktorial tanpa Rekursif

Funct Fact(n:integer);Begin

Fact :=1;For i := 1 to n do

Fact := Fact*i;End;

23

Heny Pratiwi, S.Kom., M.Pd.

Program Faktorial Dengan Rekursif

Function Fact(n:integer):integer;Begin

If (n=0) or (n=1) thenFact :=1

ElseFact :=n*fact(n-1);

End;

24

Heny Pratiwi, S.Kom., M.Pd.

Formulasi Pemecahan Masalah

Fact(n) = n * (n-1) * (n-2)* ... *3*2*1akan sama dengan

Fact(n) = n * F(n-1)

25

Heny Pratiwi, S.Kom., M.Pd.

Contoh Faktorial

• Penelusuran Fact(4) menggunakan rekursif :

• Fact(4)= 4 * fact(3)= 4 * (3*fact(2))= 4 * (3*(2*fact(1))= 4 * (3*2*1) = 24

26

Referensi

Materi Ini Bisa Di Download Pada:

www.henypratiwi.com

Hariyanto, Bambang. 2008. Struktur Data : Pondasi Membuat Program Yang Elegan dan Efisien. Bandung: Informatika.

Shalahuddin, M. dan Rosa A.S. 2012. Modul Pembelajaran Struktur Data. Bandung: Modula.

Zakaria, Teddy Marcus dan Agus Prijono. 2006. Konsep dan Implementasi Struktur Data. Bandung: Informatika.

Heny Pratiwi, S.Kom., M.Pd.

Penyusun :

Email : ayokitakuliah@gmail.comFanspage : ayokitakuliahTwitter : @ayokitakuliahWebsite : www.henypratiwi.com

Heny Pratiwi, S.Kom., M.Pd.STMIK Widya Cipta DharmaSAMARINDA - KALTIM

29