BAB II STACK Atau TUMPUKAN

Catatan Kuliah

STRUKTUR DATA

BAB II STACK Atau TUMPUKAN List Linear (Daftar Linear). List linier adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya disebut simpul (node). Simpul terdiri dari dua bagian yaitu Info dan Next. Secara umum list linear ditulis sebagai Type elemenN = Record Info : ; Next :

; End; Narwen, M.Si / Jurusan Matematika FMIPA Unand

1

Catatan Kuliah

STRUKTUR DATA

Dalam hal ini, Info adalah sebuah tipe terdefenisi yang menyimpan informasi dari sebuah elemen list atau node. Sedangkan Next adalah address dari elemen berikutnya (suksesor). Selain node pertama dan terakhir, maka setiap node memiliki sebuah node suksesor langsung dan predesesor langsung. Disini, banyak simpul dapat berubah-ubah. Dengan demikian, jika didefinisikan First adalah alamat elemen pertama dari list, maka elemen berikutnya dapat diakses secara suksesif dari elemen pertama tersebut. Narwen, M.Si / Jurusan Matematika FMIPA Unand

2

Catatan Kuliah

STRUKTUR DATA

Jadi, sebuah list linier dikenali: ● elemen pertamanya, biasanya melalui alamat elemen pertama yang disebut FIRST. ● alamat elemen berikutnya (suksesor), jika kita mengetahui alamat sebuah elemen, yang dapat diakses melalui field NEXT. ● setiap elemen mempunyai alamat, yaitu tempat elemen yang disimpan dapat diacu. Untuk mengacu sebuah elemen, alamat harus terdefenisi. Dengan alamat tersebut Informasi yang tersimpan pada elemen list dapat diakses. ● elemen terakhirnya. Ada berbagai cara untuk mengenali elemen akhir. Narwen, M.Si / Jurusan Matematika FMIPA Unand

3

Catatan Kuliah

STRUKTUR DATA

Jika L adalah list dan P adalah address maka alamat elemen pertama dari list L dapat diacu dengan notasi, First (L). Elemen yang diacu oleh address P dapat dikonsultasikan informasinya dengan notasi, Info(P) Next(P). Beberapa defenisi: 1. List L adalah List kosong, jika First (L) = Nil. 2. Elemen terakhir dikenali dengan salah satu cara adalah karena Next(Last) = Nil. Satu node dapat dihapus atau dimasukan sebagai anggota list pada posisi sembarang. Narwen, M.Si / Jurusan Matematika FMIPA Unand

4

Catatan Kuliah

STRUKTUR DATA

Contoh dari linked linear adalah : File, Stack atau tumpukan, Queue atau antrian dan Daftar berkait atau linear linked list atau one-way list.

Narwen, M.Si / Jurusan Matematika FMIPA Unand

5

Catatan Kuliah

STRUKTUR DATA

STACK atau TUMPUKAN. STACK (Tumpukan) adalah bentuk khusus dari list linier. Pada stack, penghapusan serta penyisipan elemennya hanya dapat dilakukan pada satu posisi akhir dari list. Posisi ini disebut puncak atau TOP dari stack. Elemen stack S pada posisi ini dinyatakan dengan TOP(S). Karena aturan penyisipan dan penghapusan semacam itu, maka TOP adalah satu-satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan menjadi elemen yang pertama akan dihapus. Dikatakan bahwa elemen Stack akan tersusun secara LIFO (Last In First Out). Narwen, M.Si / Jurusan Matematika FMIPA Unand

6

Catatan Kuliah

STRUKTUR DATA

Secara lojik, sebuah STACK dapat digambarkan sebagai list linier yang setiap elemennya adalah, Type ElemenS = Record Info : ; Next :

; End;

Dengan Tipe Info terdefinisi akan menentukan informasi yang disimpan pada setiap elemen stack, dan address adalah “alamat” dari elemen. Selain itu alamat elemen terbaru (TOP) dicatat, sedangkan alamat elemen yang paling “bawah”, yaitu yang paling lama biasanya disebut BOTTOM. TOP adalah elemen pertama list, supaya penambahan dan penghapusan dengan mudah dan efisien dapat dilakukan. Narwen, M.Si / Jurusan Matematika FMIPA Unand

7

Catatan Kuliah

STRUKTUR DATA

Sehingga, jika S adalah sebuah Stack, dan P adalah address maka, Top (S) adalah alamat elemen TOP, dimana operasi penyisipan/penghapusan dilakukan. Info (P) adalah informasi yang disimpan pada alamat P Next (P) adalah alamat suksesor P. ElemenS (P) adalah sebuah elemen stack yang beralamatkan P. Stack kosong adalah Stack dengan Top (S) = Nil, atau tidak terdefinisi. Narwen, M.Si / Jurusan Matematika FMIPA Unand

8

Catatan Kuliah

STRUKTUR DATA

Operasi Pada Stack. 1. EMPTY(S) : memeriksa apakah stack S kosong atau tidak. Hasilnya data bertipe boolean. empty(S) bernilai true jika S kosong dan false kalau tidak kosong. 2. PUSH(S,E) : menambahkan elemen E pada stack S. Elemen E ditempatkan sebagai TOP(S). Kesalahan akan terjadi bila dilakukan PUSH(S,E) terhadap stack yang sudah penuh. 3. POP(S) : mengeluarkan elemen TOP(S) dari dalam Stack S. POP(S) akan mengurangi nilai NOEL(S) dgn 1. Kesalahan terjadi bila dilakukan POP(S) terhadap Stack S yang kosong. Narwen, M.Si / Jurusan Matematika FMIPA Unand

9

Catatan Kuliah

STRUKTUR DATA

Deklarasi Stack dengan PASCAL : Const maxstack = 100; Type Stack = Record item : array[1..maxstack] of Integer; top : 0..maxstack; end; Var S : Stack;

Function Empty(s:Stack) : boolean; Begin if S.top = 0 then empty := true else empty := false End;

Narwen, M.Si / Jurusan Matematika FMIPA Unand

10

Catatan Kuliah

STRUKTUR DATA

Procedure Push(var s:Stack; x : Integer); Begin if S.top = maxstack then “error(‘stack overflow’)” else begin s.top := s.top + 1; s.item[s.top] := x; end; End; Function Pop(var s:Stack): Integer; Begin if empty(S) then “error(‘stack underflow’)” else begin pop := s.item[s.top]; s.top := s.top - 1 end; End; Narwen, M.Si / Jurusan Matematika FMIPA Unand

11

Catatan Kuliah

STRUKTUR DATA

Aplikasi dari Stack. Stack sangat luas pemakaiannya. Beberapa pemakaian stack dapat dilihat pada contoh berikut.

1. Matching Parentheses (Penjodohan Tanda Kurung). Misalkan suatu ekspresi matematika berisi tanda kurung {, (, [, }, ) dan ]. Selanjutnya akan diperiksa apakah ekpresi tersebut valid atau tidak. Algoritmanya adalah sebagai berikut. Amati barisan elemen dari kiri ke kanan. - Bila ditemukan kurung pembuka, maka PUSH tanda kurung tersebut ke dalam stack S. - Bila ditemukan kurung penutup, lakukan <> jika stack S kosong maka ekspresi tidak valid dan selesai <> jika stack S tak kosong maka periksa, -- jika top dari stack S tidak sesuai dengan tanda kurung penutup maka ekspresi tidak valid dan selesai. Narwen, M.Si / Jurusan Matematika FMIPA Unand

12

Catatan Kuliah

STRUKTUR DATA

-- jika top dari stack S sesuai dengan tanda kurung penutup maka pop elemen dari stack S dan periksa elemen berikutnya dari ekspresi. - Bila sudah diakhir dan stack S kosong maka Ekspresi valid sebaliknya tidak valid..

Contoh. Periksa apakah ekspresi berikut valid atau tidak. a. {[a+b]-[(c-d)] b. {x+(y-[a+b])*c-[(d+e)]}/(h-(j-(k-[l-n]))) Latihan. Buat program pascal untuk menyelesaikan masalah matching parentheses tersebut.

Narwen, M.Si / Jurusan Matematika FMIPA Unand

13

Catatan Kuliah

STRUKTUR DATA

2. Menghitung nilai ekspresi. Diberikan sebuah ekspresi matematika. Akan dihitung berapa nilai dari ekspresi tersebut bila diketahui nilai-nilai dari variabelnya. Algoritmanya sebagai berikut. Modifikasi algoritma untuk menyelesaikan masalah matching parentheses. Amati baris elemen dari kiri ke kanan. - Bila ditemukan kurung pembuka, maka PUSH tanda kurung tersebut ke dalam stack S1. - Bila ditemukan operand, maka push operand tersebut ke dalam stack S2. - Bila ditemukan operator, maka push operator tersebut ke dalam stack S3. - Bila ditemukan kurung penutup, maka <> jika stack S1 kosong maka ekspresi tidak valid dan selesai Narwen, M.Si / Jurusan Matematika FMIPA Unand

14

Catatan Kuliah

STRUKTUR DATA

<> jika stack S1 tak kosong maka periksa, jika top dari stack S1 sesuai dengan tanda kurung maka * POP elemen dari stack S1 * POP dua elemen dari stack S2 * POP elemen dari stack S3 * operasikan dua elemen stack S2 dengan elemen S3 * PUSH hasilnya ke dalam stack S2, periksa elemen berikutnya dari ekspresi. Contoh. Hitung nilai ekspresi (((y-1)/x)*(x+y)), bila diketahui nilai x = 2 dan y = 5.

Latihan. Buat program pascal untuk menyelesaikan masalah menghitung nilai ekspresi tersebut. Narwen, M.Si / Jurusan Matematika FMIPA Unand

15

Catatan Kuliah

STRUKTUR DATA

3. Notasi INFIX, POSTFIX dan PREFIX. Awalan pre, post dan in menyatakan posisi relatif dari operator terhadap operand. - Infix : bentuk penulisan dimana operator terletak antara dua operand. - Postfix : bentuk penulisan dimana operator didahului oleh dua operand. - Prefix : bentuk penulisan dimana operator mendahului dua operand. Misalnya, A+B AB+ +AB

Infix Postfix Prefix

Narwen, M.Si / Jurusan Matematika FMIPA Unand

16

Catatan Kuliah

STRUKTUR DATA

Pada operator biner, hirarki pengerjaan dimulai dari : 1. Pangkat ($), 2. Perkalian dan pembagian (*, /), 3. Penjumlahan dan pengurangan (+, -). Tapi bila digunakan tanda kurung, maka hirarki di atas tidak berlaku lagi. Dalam notas infix, penggunaan tanda kurung akan menentukan makna dari bentuk ekspresi. Tanpa tanda kurung, maka ekspresi matematika dapat bermakna ganda. Untuk menghindari makna ganda tersebut, maka ekspresi dapat ditulis dalam bentuk postfix atau prefix. Operator *, +, - dan / dalam infix tanpa tanda kurung dibaca dari kiri ke kanan, sedangkan operator $ dibaca dari kanan ke kiri. Narwen, M.Si / Jurusan Matematika FMIPA Unand

17

Catatan Kuliah

STRUKTUR DATA

Contoh : Rubah ke notasi prefix dan postfix dari bentuk infix berikut. a. a – b + c b. ( a + b ) * ( c – d ) c. a + b * c – d d. a $ b * c – d + e / f / ( g + h ) e. ( ( a + b ) * c – ( d – e ) ) $ ( f + g ) f. a – b / ( c * d $ e )

Narwen, M.Si / Jurusan Matematika FMIPA Unand

18

Catatan Kuliah

STRUKTUR DATA

Menghitung nilai dari ekspresi Postfix. - Setiap operator dari bentuk postfix mengacu pada dua operand yang mendahuluinya. Akibatnya ada satu operand yang merupakan hasil aplikasi dari operator tersebut. - Bila diaplikasikan ke Stack, maka setiap kali ditemukan operand, lakukan PUSH pada stack dan bila ditemukan operator, lakukan POP terhadap dua elemen TOP dari stack, kemudian lakukan operasi matematika terhadap kedua elemen tersebut sesuai dengan operator yang ditemukan. Selanjutnya lakukan PUSH terhadap hasil operasi itu. Algoritmanya adalah sebagai berikut, Narwen, M.Si / Jurusan Matematika FMIPA Unand

19

Catatan Kuliah

STRUKTUR DATA

Inisialisasi nilai Stack,opnstk ke kosong; Baca input string per elemen dan masukkan ke symb; While masih ada karakter dalam input string do Begin symb := input karakter if symb adalah operand then push(opnstk,symb) else begin opnd2 := pop(opnstk); opnd1 := pop(opnstk); value := hasil aplikasi symb terhadap opd1,opnd2; push(opnstk,value); end; End;

Contoh. Hitung nilai dari ekpspresi postfix berikut: 623+-382/+*2$3+ Narwen, M.Si / Jurusan Matematika FMIPA Unand

20

Catatan Kuliah

STRUKTUR DATA

Mengkonversi bentuk Infix ke Postfix. - Urutan operand dalam postfix harus sama dengan urutan operand dalam infix. - Kalau infix tanpa tanda kurung, maka urutan sesuai dengan hirarki. - Maka definisikan fungsi, Prcd (op1,op2 : char) : boolean; Fungsi ini bernilai ‘True’, jika op1 muncul lebih dahulu dari op2 dalam urutannya, sebaliknya bernilai ‘False’. Misalnya : prcd(‘*’,’+’) dan prcd(‘+’,’+’) bernilai true prcd(‘+’,’*’) bernilai false. Algoritmanya adalah sebagai berikut, Narwen, M.Si / Jurusan Matematika FMIPA Unand

21

Catatan Kuliah

STRUKTUR DATA

Inisialisasi nilai Stack,opnstk ke kosong; Inisialisasi string postfix ke blank Baca input string per elemen dan masukkan ke symb; While masih ada karakter dalam input string do Begin symb := input karakter if symb adalah operand then tambahan symb ke string postfix else begin while (not empty(opstk)) and (prcd(stacktop(opstk),symb)) do begin topsymb := pop(opstk); tambahkan topsymb ke string postfix end; push(opstk,symb); (*) end;End; While not empty(opstk); Do begin topsymb := pop(opstk) tambahkan topsymb ke string postfix End;end; Narwen, M.Si / Jurusan Matematika FMIPA Unand

22

Catatan Kuliah

STRUKTUR DATA

Algoritma di atas digunakan kalau bentuk infix tanpa tanda kurung. Kalau infix dengan tanda kurung, maka ganti garis bertanda (*) pada algoritma di atas menjadi, If (empty(opstk)) or (symb <> ‘ ‘) then push(opnstk,symb) else topsymb := pop(opnstk);

Contoh. Konversi bentuk infix berikut ke bentuk postfix. 1. A + B * C 2. (A + B ) * C 3. (( A – ( B + C )) * D ) $ (E + F)

Narwen, M.Si / Jurusan Matematika FMIPA Unand

23