Struktur Data # 4 (Selasa, 2 april 2013 - semster 2)

Hari ini saya mengambil jadwal kuliah malam, jam 18.30 s/d 22.00 wib.  Dengan Mata Kuliah Struktur Data. Bersama Dosen Bapak Ganda Sirait. Pembahasan Bab 3, tumpukan/stack. berikut Resumenya:

 ==============STRUKTUR DATA TUMPUKAN (STACK)===================

STRUKTUR DATA TUMPUKAN (STACK)adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linier, kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu pada posisi ATAS (TOP) tumpukan.

Operasi-operasi dasar pada STACK (tumpukan):
a. CREATESTACK(S) : Membuat tumpukan baru S, dengan jumlah elemen kosong.
b. MAKENULL(S) : Mengosongkan tumpukan S, jika ada elemen maka semua elemen akan dihapus.
c. EMPTY : Tumpukan kosong? – menguji apakah tumpukan kosong.
d. PUSH(x,S) : Memasukan elemen baru x kedalam Tumpukan S.
e. POP(S) : Mengeluarkan elemen posisi atas pada Tumpukan S.

       Ilustrasi operasi POP dan PUSH terhadap stack (Tumpukan)

No. OPERASI                       ISI TUMPUKAN                 NILAI /TOP
1     CREATESTACK(S)                  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

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

Algoritma PUSH : PUSH(S, TOP, MAKSTUM, ELEMEN)
1. [Periksa kandungan tumpukan, apakah penuh?]
Jika TOP=MAKSTUM; Cetakan ‘OVERFLOW’
2. [Tambahkan TOP dengan 1]
TOP := TOP+1
3. [Masukan ELEMEN kedalam lokasi TOP yang baru]
S[TOP] := ELEMEN;
4. Return

Algoritma POP : POP(S, TOP, ELEMEN)
1. [Periksa kandungan Tumpukan, apakah kosong ?]
    Jika TOP = 0 ; Cetakan ‘UNDERFLOW’
2. [Simpan nilai teratas pada ELEMEN]
    ELEMEN := S[TOP]
3. [Kurangkan TOP dengan 1]
    TOP := TOP-1
4. Return

NOTASI ARITMETIK (INFIX, PREFIX, DAN POSTFIX)
Notasi aritmetik biasa ditulis dalam notasi Infix, missal A+B-C. Notasi infix mudah dimengerti oleh manusia, hanya saja dalam notasi infix perlu diperhatikan prioritas pengerjaan karena berhubungan dengan hirarki operator pada computer. Prioritas pengerjaannya adalah :
1. Tanda kurung : ( …. )
2. Eksponensial atau pangkat : ^
3. Perkalian, pembagian : * , /
4. Penjumlahan, Pengurangan : +, -

Contoh : (A-B) * (C+D)
Prioritas pengerjaan soal diatas adalah sebagai berikut :
a. Dalam kurung yang paling kiri : (A-B)
b. Dalam kurung yang kedua : (C-D)
c. Perkalian hasil pengurangan dengan hasil penjumlahan.

Notasi Prefix dan Notasi Postfix lebih mudah dikerjakan oleh computer.

PREFIX adalah keadaan dimana symbol operator diletakan sebelum dua operand.
POSTFIX adalah keadaan dimana symbol 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 (disebut juga Poslish Notation – PN)
- Notasi Postfix : Operand operand operator (disebut juga Reveser Polish Notation – RPN)

Contoh ke-1 : INFIX ke PREFIX (A+B) – (C*D)
Cara pengerjaan :
a. Pengerjaan dalam kurung ke-1 : (A+B), prefixnya adalah +AB
b. Pengerjaan dalam kurung ke-2 : (C*D), prefixnya adalah *CD
c. Terakhir adalah operator - , +AB - *CD, prefix nya adalah -+AB * CD

Contoh ke-2 : INFIX ke POSTFIX (A+B) – (C*D)
Cara pengerjaan :
a. Pengerjaan dalam kurung ke-1 : (A+B), postfixnya adalah AB+
b. Pengerjaan dalam kurung ke-2 : (C*D), postfixnya adalah CD*
c. Terakhir adalah operator - , AB+ - CD*, postfix nya adalah AB+ CD*-

Contoh ke-3 : PREFIX ke INFIX: +/*ABCD
Cara pengerjaan : mencari operator dimulai dari operand terkanan.
a. Cari operator ke-1 : *, ambil dua operand sebelumnya A dan B, sehingga infixnya adalah (A*B)
b. Cari operator ke-2 : /, ambil dua operand sebelumnya (A*B) dan C, sehingga infixnya adalah ((A*B)/C)
c. Cari operator ke-3 : +, ambil dua operand sebelumnya ((A*B)/C) dan D, sehingga infixnya adalah ((A*B)/C)+D


Contoh ke-4 : PREFIX ke POSTFIX: +/*ABCD
Cara pengerjaan : mencari operator dimulai dari operand terkanan.
a. Cari operator ke-1 : *, ambil dua operand sebelumnya A dan B, sehingga postfixnya adalah AB*
b. Cari operator ke-2 : /, ambil dua operand sebelumnya AB* dan C, sehingga postfixnya adalah AB* C/
c. Cari operator ke-3 : +, ambil dua operand sebelumnya AB* C/ dan D, sehingga postfixnya adalah AB* C/ D+


Contoh ke-5 : POSTFIX ke INFIX : ABCD*/-
Cara pengerjaan : mencari operator dimulai dari operand terkiri.
a. Cari operator ke-1 : *, ambil dua operand sebelumnya C dan D, sehingga infixnya adalah (C*D)
b. Cari operator ke-2 : /, ambil dua operand sebelumnya B dan (C*D), sehingga infixnya adalah (B/(C* D))
c. Cari operator ke-3 : -, ambil dua operand sebelumnya A dan (B/(C* D)), sehingga infixnya adalah A- (B/(C* D)).

Contoh ke-6 : POSTFIX ke PREFIX : ABCD*/-
Cara pengerjaan : mencari operator dimulai dari operand terkiri.
a. Cari operator ke-1 : *, ambil dua operand sebelumnya C dan D, sehingga prefixnya adalah *CD
b. Cari operator ke-2 : /, ambil dua operand sebelumnya B dan *CD, sehingga prefixnya adalah /B *CD
c. Cari operator ke-3 : - , ambil dua operand sebelumnya A dan /B *CD, sehingga prefixnya adalah –A /B *C

Sumber : Teddy Markus Zakaria, Agus Prijono.2005.Konsep dan Implementasi Struktur Data. Bandung : Penerbit Informatika