4. STACK / TUMPUKAN TUJUAN PRAKTIKUM 1. Praktikan mengenal tipe khusus dari link list yaitu stack/tumpukan beserta seluruh operasi yang ada padanya. 2. Praktikan diharapkan dapat menerapkan teori mengenai single link list di dalam pembuatan program stack. 3. Praktikan mengerti akan overflow dan underflow 4. Praktikan mengerti tentang notasi infix dan postfix
TEORI PENUNJANG
4.1. Pengertian Stack/Tumpukan Stack/Tumpukan adalah bentuk khusus dari list linear. Pada stack, penghapusan serta pemasukan elemennya hanya dapat dilakukan pada satu posisi, yakni posisi akhir dari list. Posisi ini disebut puncak atau Top dari stack. Elemen stack S pada posisi ini dinyatakan dengan TOP(S). Jelasnya, bila stack S = [A, B, C, D, E], maka TOP(S) adalah E. banyaknya elemen pada stack S pada suatu saat tertentu biasa kita sebut sebagai NOEL(S). Jadi untuk stack diatas NOEL(S) = 5. Seperti halnya link list, pada stack juga terdapat operasi penghapusan dan pemasukkan elemen list. Operator penghapusan pada stack kita kenal dengan nama POP, sedangkan operator pemasukkan elemen disebut PUSH. Berikut ini merupakan ilustrasi dari penggunaan operator-operator diatas yang dimulai dari sebuah stack S kosong, S = [ ].
S
NOEL(S) = 0, TOP(S) tidak terdefinisi
Lab. Teknik Informatika – Struktur Data
1
Mula-mula kita PUSH elemen A, diperoleh Stack S = [A].
S
NOEL(S) = 1, TOP(S) = A
A
Setelah itu kita PUSH elemen B, diperoleh Stack S = [A,B].
S
NOEL(S) = 2, TOP(S) = B
B A
Kemudian kita PUSH kembali elemen C, diperoleh Stack S = [A,B,C].
C B A
S
NOEL(S) = 3, TOP(S) = C
Apabila kita lakukan POP sekali, diperoleh Stack S = [A,B].
S
NOEL(S) = 2, TOP(S) = B
B A
Kemudian kita PUSH elemen D, diperoleh Stack S = [A,B,D].
D B A
S
NOEL(S) = 3, TOP(S) = D
Dari ilustrasi diatas dapat dilihat bahwa operasi pop dan operasi push dilakukan pada posisi paling atas dari stack. Dengan kata lain operasi itu bersifat Terakhir Masuk Pertama Keluar atau Last In First Out (LIFO). Pada dasarnya kita tidak membatasi berapa banyak elemen yang dapat masuk ke dalam stack apalagi jika kita menggunakan tipe data link list yang tidak mempunyai batas, tetapi jika kita menggunakan tipe data Array jumlah elemen
Lab. Teknik Informatika – Struktur Data
2
yang dapat masuk ke dalam stack dibatasi tergantung dari batas atas array (upper bound). Hal ini akan menyebabkan adanya kondisi Overflow pada stack jika kita mencoba melakukan operasi PUSH pada stack yang sudah penuh. Atau juga akan terjadi kondisi Underflow pada stack jika kita mencoba unruk melakukan operasi POP pada stack yang kosong. Pada praktikum ini kita akan mencoba mengimplementasikan stack dari link list tapi yang mempunyai batasan agar kondisi overflow dan underflow dapat diterapkan.
4.2. Deklarasi Stack Dalam Link List Pendeklarasian Stack di dalam link list sama seperti kita mendeklarasikan link list. Menggunakan pointer sebagai variabel yang menunjuk ke elemen Stack selanjutnya.
Deklarasi Stack menggunakan Linked List di dalam Pascal : Type Stack Simpul
= ^Simpul = Record Info : Char; Next : Stack; End;
Var Head, Tail : Stack; Max : Byte; Link list yang kita gunakan ialah jenis Header Single Link List. Kita menggunakan jenis link list ini karena pada bagian header dapat kita manfaatkan untuk menyimpan informasi mengenai banyaknya elemen dalam stack (NOEL(S)). Selain itu jika kita menggunakan posisi Head, operasi POP yang akan dilakukan pada posisi Head akan menyebabkan timbul kondisi UNDERFLOW demikian juga jika kita melakukan operasi PUSH pada posisi Tail akan menyebabkan kondisi OVERFLOW.
Lab. Teknik Informatika – Struktur Data
3
4.3. Operasi Pada Stack Terdapat empat operasi pada Stack, yakni CREATE(Stack), ISEMPTY(Stack), PUSH(Elemen,Stack) dan POP(Stack). 1.
CREATE(Stack) Operator ini menyebabkan Stack menjadi suatu Stack hampa. Jika terdapat operasi NOEL(CREATE(S)) hasilnya adalah 0 dan TOP(CREATE(S)) hasilnya adalah tidak terdefinisi. Procedure CREATE selengkapnya adalah sebagai berikut: Procedure CREATE(Var Head : Stack); Begin New(Head); Head^.Info:= 0; { Menunjukkan NOEL(S) = 0 } End;
2.
ISEMPTY(Stack) Operator ini berfungsi untuk memeriksa apakah Stack S hampa atau tidak. Keluaran dari operator ini bertipe
boolean. Jika NOEL(S) = 0 maka
ISEMPTY(S) = True dan jika NOEL(S) > 0 maka ISEMPTY(S) = False. Kita menerapkan ISEMPTY sebagai sebuah Function, Function ISEMPTY selengkapnya adalah sebagai berikut :
Function ISEMPTY(Head, Tail : Stack) : Boolean; Begin ISEMPTY := False; If (Tail = NIL) or (Head^.Info = 0) Then ISEMPTY:=True; End;
3.
PUSH(Elemen,Stack) Operator ini digunakan untuk menambahkan elemen E pada Stack S. E ditempatkan pada posisi paling atas / TOP(S).
Lab. Teknik Informatika – Struktur Data
4
Procedure PUSH(Var Head, Tail : Stack; Elemen : Char); Var Temp : Stack; Begin New(Temp); Temp^.Info := Elemen; If (Head^.Info = Max) { Jika Stack Sudah Penuh } Writeln(„OVERFLOW Euy…!‟) Else Begin If Tail = NIL Then { Jika Stack Masih Kosong } Tail := Temp Else Tail^.Next := Temp; Tail := Temp; Tail^.Next := NIL; Inc(Head^.Info); { Naikkan banyaknya elemen } End; End; 4.
POP(Stack) Operator ini digunakan jika kita ingin menghapus elemen terakhir dari stack. Di lakukan jika stack tidak kosong (ISEMPTY = False).
Procedure POP(Var Head, Tail : Stack); Var Temp : Stack; Begin Temp := Head; If Not ISEMPTY(Head,Tail) Then { Jika Stack tidak kosong } Begin Repeat Temp := Temp^.Next; Until (Temp^.Info = Tail^.Info); Tail := Temp; Dispose(Temp); Dec(Head^.Info); End Else Writeln(„UNDERFLOW Euy…!‟); End;
Lab. Teknik Informatika – Struktur Data
5
4.4. Aplikasi Stack Salah satu pemanfaatan dari stack adalah untuk menulis ungkapan-ungkapan menggunakan notasi tertentu. Seperti kita ketahui, dalam penulisan ungkapan, khususnya ungkapan numeris, kita selalu menggunakan tanda kurung untuk mengelompokkan bagian mana yang harus dikerjakan lebih dahulu.
Sebagai contoh, dalam ungkapan :
((A + B) * (C – D))
suku (A + B) akan dikerjakan lebih dahulu, kemudian suku (C – D), dan terakhir mengalikan hasil yang diperoleh dari dua suku ini.
Sedangkan dalam ungkapan :
A+B*C–D
Maka B * C akan dikerjakan terlebih dahulu karena operator * (perkalian) mempunyai prioritas yang lebih tinggi dibandingkan dengan operator + (penjumlahan) dan operator – (pengurangan).
Cara penulisan ungkapan sering disebut dengan notasi Infix, yang artinya adalah bahwa operator ditulis di antara dua operand.
Dalam ungkapan-ungkapan yang rumit, pemakaian tanda kurung ini tidak bisa dihindari. Semakin rumit suatu ungkapan semakin banyak yang dibutuhkan tanda kurung. Hal ini membawa suatu konsekuensi bahwa penulisan tanda kurung itupun harus benar-benar terhindar dari kesalahan. Seorang ahli matematikawan yang bernama Jan Lukasiewicsz kemudian mengembangkan suatu cara penulisan ungkapan numeris yang selanjutnya disebut Notasi Prefix atau Notasi Postfix atau Notasi Suffix. Berikut ini diberikan sebuah algoritma untuk mengubah notasi infix kedalam notasi postfix. Sebuah stack digunakan untuk keperluan ini. Ekspresi diamati satu persatu dari kiri ke kanan.
Lab. Teknik Informatika – Struktur Data
6
Pada algoritma ini terdapat 4 aturan dasar, sebagai berikut : 1.
Jika simbol adalah “(“ (kurung buka), maka ia kita PUSH ke dalam Stack.
2.
Jika simbol adalah “)” (kurung tutup), maka POP dari Stack elemen-elemen Stack sampai pertama kali kita POP simbol “(“. Semua elemen stack yang di POP tersebut merupakan output, kecuali “(“ tadi.
3.
Jika simbol adalah sebuah Operand, tanpa melakukan perubahan elemen stack, operand tersebut langsung merupakan output.
4.
Jika simbol adalah sebuah operatot, maka jika TOP stack adalah operator dengan level lebih tinggi atau sama, maka elemen TOP kita POP, sekaligus keluar sebagai output, dilanjutkan proses seperti ini sampai TOP merupakan “(“ atau operator dengan level yang lebih rendah. Kalau hal ini terjadi, operator (yang diamati) kita PUSH kedalam stack. Dapat dicatat bahwa terdapat 3 level operator yakni : Level tertinggi
: Pemangkatan (^)
Level menengah
: Perkalian (*) dan Pembagian (/)
Level terendah
: Penjumlahan (+) dan Pengurangan (-).
Untuk memahami algoritma diatas, kita mencoba mengubah ungkapan berikut, yang ditulis menggunakan notasi infix, menjadi notasi postfix, yaitu: ((A + B) * (C – D))
Ilustrasi pengubahan notasi infix diatas menjadi notasi postfix secara lengkap tersaji dalam tabel berikut :
Proses Karakter ke Dibaca
Isi Stack
1
(
(
2
(
((
3
A
((
4
+
+((
5
B
+((
Lab. Teknik Informatika – Struktur Data
Karakter Tercetak
Notasi Postfix terbentuk
A
A
yang
A B
AB
7
6
)
(
+
7
*
*(
8 9 10 11 12 13
( C D ) )
(*( (*( -(*( -(*( *( (
AB+ AB+
AB+ C AB+C AB+C D AB+CD AB+CD* AB+CD-* Ujung Tumpukan (TOP)
Dari ilustrasi ditas bisa kita lihat bahwa notasi postfix dari ungkapan : ((A + B) * (C – D))
Adalah
AB+CD-*
LAPORAN PENDAHULUAN 1. Pengertian Stack / Tumpukan beserta cara pendefinisiannya. 2. Jelaskan istilah-istilah pada stack : Create, Push, Pop, Top, IsEmpty & Noel 3. Berikan contoh soal mengenai operasi stack Push dan pop seperti pada ilustrasi stack diatas.Kapan kondisi Overflow dan Underflow terjadi. 4. Apa yang anda ketahui tentang notasi infix dan postfix serta bagaimana algoritma perubahan dari notasi infix menjadi postfix.
MATERI PRAKTIKUM 1. Praktikan memahami tentang Stack, Operasi pada stack. 2. Membuat program sederhana yang berhubungan dengan Stack, dapat juga diberikan program mengenai notasi Postfix dan notasi Infix. 3. Nilai K (Keterampilan) didapat jika praktikan melengkapi program tentang operasi pada Stack.
Lab. Teknik Informatika – Struktur Data
8
LAPORAN AKHIR Buat Algoritma dari program sebelumnya terutama mengenai program infix postfix, ditambah dengan ringkasan tentang operasi stack.
Lab. Teknik Informatika – Struktur Data
9
