MAKALAH ALGORITMA DAN STRUKTUR DATA (STACK)

RINGKASAN MATA KULIAH ALGORITMA DAN STRUKTUR DATA

TUMPUKAN (STACK)

Bp. MOH. Ahsan, S.kom

Kelompok satu :

1. Eko Fidi Winandar (140403020075)

2. Seli junita (140403020078)

3. Kyky ulan dhari (140403020077)

4. Qurotul ayuni (140403020074)

 

Departemen Pendidikan Dan Kebudayaan

Sistem Informasi Komputer

Universitas Kanjuruhan Malang

Tahun ajaran 2014-2015

KATA PENGANTAR

            Pada bab ini kita akan membahas struktur data tumpukan. Saat implementasi struktur data ini, biasanya menggunakan larik untuk menyimpan data sebuah variabel untuk menyimpan posisi atas (top).

Materi:

a.       Definisi

b.      Kamus data

c.       Operasi-operasi dasar tumpukan

d.      Notasi aritmatik (infix, prefix dan postfix)

e.       rekursif

DEFINISI TUMPUKAN

            Tumpukan 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. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (back track). Elemen-elemen didalam 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). Contoh pada PDA (Push Down Automaton). Sistem pada pengaksesan pada tumpukan menggunakan sistem LIFO (Last In First Out), artinya elemen yang terakhir masuk itu yang akan pertama dikeluarkan dari tumpukan. Ilustrasi tumpukan dapat digambarkan seperti tumpukan CD atau tumpukan sate.

KAMUS DATA TUMPUKAN

            Sebelum struktur data tumpukan ini bisa digunakan, harus dideklarasikan dahulu dalam kamus data. Ada beberapa cara pendeklarasian struktur data ini, salah satunya dengan menggunakan tata susunan linier (larik) dan sebuah variabel, yang dikemas dalam tipe data record. Berikut pendeklarasian struktur data tumpukan dalam kamus data:

Kamus data

Const

MAKSTUM = 80; {kapasitas maksimal dari tumpukan}

Type

Jenis Elemen = char;

Tumpukan = record

Elemen : Array[1...MAKSTUM] of JenisElemen;

Atas : 0..MAKSTUM;

end;

            Tumpukan adalah struktur data bertipe record yang terdiri dari field elemen, bertipe larik/array dengan indek dari 1 sampai dengan MaksTum.

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:

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 : Tumpukan kosong? – menguji apakah tumpukan kosong

d.      PUSH (x, S) – memasukan elemen baru x kedalam tumpukan S

e.       POP (S) – mengeluarkan elemen posisi atas tumpukan S

Ilustrasi operasi POP dan PUSH terhadap stack

            Apa yang terjadi bila dilakukan POP (S) sebanyak dua kali? Underflow, artinya tumpukan kosong tidak ada elemen yang dapat diambil. Apa yang terjadi bila dilakukan PUSH(x,S) sebanyak sepuluh kali, jika kapasitas tumpukan adalah lima lagi? Overflow, artinya tumpukan penuh tidak ada elemen yang dapat dimasukan kedalam 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.

ALGORITMA PUSH: PUSH (S,POP,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

Untuk lebih jelasnya perhatikan operasi-operasi dasar pada tumpukan yang ditulis dalam bahasa pascal.

Program Operasi_tumpukan;

Const

            MAKSTUM = 80;

Type

JenisElemen = Char
Tumpukan = Record
Elemen:Array[1..MAKSTUM] of jenisElemen;
Top:0..MAKSTUM;
end;

{Operasi 1}
Procedure CreateStack(Var S:Tumpukan);
Begin

            S.Top := 0;

End;

{Operasi 2}
Procedure MakeNull(Var S:Tumpukan);
Begin

            S.Top :=0;

End;

{Operasi 3 : PUSH}
Procedure Push (Elemen Baru : jenis elemen ; Var S: tumpukan);
Begin

If  S.Top= MAKSTUM then
writeln (‘OverFlow’)
else
Begin
S.Top := S.Top +1;
S.Elemen[S.Top] := Elemen Baru;
End;

End;

{Operasi 4 : POP, agar elemen yang diambil dari tumpukan bisa disimpan diperlukan variabel nilai elemen}

Procedure Pop(Var S: tumpukan; Var nilai elemen: jenis Elemen);
Begin

If  S.Top=0 then
writeln (‘UnderFlow’)
else
Begin
NilaiElemen: = S.Elemen[S.Top];
S.Top:= S.Top-1;
End;

End;

{Operasi 5: tumpukan kosong}

{Akan memulangkan nilai TRUE jika tiada elemen dalam tumpukan atau FALSE jika ada elemen dalam tumpukan}

Function Empty (Var S:Tumpukan) : Boolean;

Begin

            Empty := S.Top = 0;

End;

NOTASI ARITMETIK(INFIX, PREFIX DAN POSTFIX)

            Notasi aritmatik biasa ditulis dalam notasi infix, misal A+B-C. Notasi Infix mudah dimengerti oleh manusia, hanya saja dalam nitasi infix perlu diperhatikan prioritas pengerjaan karena berhubungan dengan hierarki operator pada komputer. 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.      Didalam kurung yang kedua : (C+D)

c.       Perkalian hasil pengurangan dengan hasil penjumlahan

Notasi infix untuk penulisan aritmatik, biasa diubah 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
(disebut juga polish notation – PN)

·         Notasi postfix             : operand operand operator A B +
(disebut juga reveser polish notation – RPN)

Untuk lebih jelasnya, berikut contoh konfersi dari satu notasi ke notasi lainnya.

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

Untuk pengerjaan infix, perlu diperhatikan urutan sebagai berikut :

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, prefixnya adalah - +AB * CD

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

Untuk pengerjaan infix, perlu diperhatikan urutan sebagai berikut:

a.       Pengerjaan dalam kurung ke 1: (A+B), postfixnya adalah AB+

b.      Pengerjaan dalam kurung ke 2: (C * D), postfixnya adalah CD*

c.       Terkhir adalah operator -, AB+ - CD*, postfixnya adalah AB+ CD*-

Contoh ke 3 : PREFIX ke INFIX : +/* A B C D

Untuk pengerjaan prefix, mencari operator dimulai dari operand tekanan sebagai berikut:

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 tiga : +, ambil dua operand sebelumnya (( A * B)/ C) dan D, sehingga infixnya adalah (( A * B)/ C) + D

Contoh ke 4 : PREFIX ke POSTFIX : +/ * A B C D

Untuk mengerjakan prefix, mencari operator dimulai dari operand tekanan sebagai berikut :

a.       Cari operator ke 1 :  *, ambil dua operand sebelumnya A dan B , sehingga postfixnya adalah A B *

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: A B C D * /-

Untuk pengerjaan postfix, mencari operator dimulai dari operand terkiri sebagai berikut :

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), sehinga 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))

REKURSIF

            Fungsi / prosedur rekursif adalah fungsi / prosedur yang memanggil dirinya sendiri, sebagai contoh adalah factorial.
Pemanggilan terhadap dirinya sendiri, menyebabkan fungsi melakukan proses pengulangan (looping).
Agar pengulangan tidak terjadi terus menerus, maka harus ada kondisi yang menyebabkan proses pengulangan berhenti. Kondisi ini disebut sebagai base. Dengan demikian badan fungsi akan dibagi atas dua bagian, yaitu :

·         Base                : kondisi berhenti

·         Recurrence      : proses pengulangan (pemanggilan dirinya sendiri)

Ilustrasi pembuatan bujur sangakr didalam bujur sangkar dan segitiga didalam segitiga dapat membantu memahami konsep rekursif. Pertama-tama dibuat bujur sangkar besar ( sisi = 1), kemudian didalamnya dibuat bujur sangkar yang lebih kecil ( sisi  < 1). Proses ini berulang sampai pembuatan bujur sangkar berhenti.

Contoh program FAKTORIAL TANPA REKURSIF dalam bahasa pascal :

Function Fact (n: integer):integer

Begin Fact := 1 ; For | ; = 1 to n do Fact ;= fact * |; End ;

Contoh program FAKTORIAL DENGAN REKURSIF dalam bahasa pascal :

Function Fact (n: integer):integer

Begin If (n=0) or (n=1) then Fact : =1 Else Fact := n * fact (n-1) ; End;

            Fungsi yang dibuat dengan rekursif akan memakan waktu lebih lama disbanding fungsi tanpa rekursif. Fungsi rekursif menggunakan struktur data tumpukan untuk menyimpan nilai sebelumnya.