Algoritma dan Struktur Data
STACK Teknik Informatika Universitas Muhammadiyah Malang 2016
Tujuan Instruksional • Mahasiswa mampu : – Memahami tentang konsep stack – Mengetahui mekanisme pengoperasian sebuah stack – Mengimplementasikan stack dengan array – Mengimplementasikan stack dengan linked list
Topik • • • •
Pengertian stack Operasi dasar pada stack Implementasi stack dengan array Implementasi stack dengan linked list
Pendahuluan • Stack Tumpukan, FIFO • Queue Antrian, LIFO • Implementasi : Bisa menggunakan Array atau Linkedlist
Konsep Stack
“Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack
Konsep Stack • Stack (tumpukan) adalah struktur data dimana proses pengambilan dan penambahan element dilakukan pada satu ujung yang sama. • Stack mengikuti konsep LIFO. • LIFO (Last In First Out) : elemen yang terakhir kali masuk akan menjadi elemen yang pertama kali keluar.
Konsep Stack • Operasi dasar pada stack adalah : pop dan push. Push : proses menambah item pada stack. Pop : proses mengambil item pada stack.
• Pop dan push sama-sama dilakukan pada item yang terakhir kali ditambahkan pada stack. PUSH
POP
Stack
Konsep Stack TOP
• Pointer TOP : digunakan untuk menunjuk element paling akhir yang dimasukkan kedalam stack.
Konsep Stack • Jika top tidak menunjuk pada element manapun hal ini menunjukkan bahwa stack dalam kondisi kosong (empty). • Pada array : top akan menyimpan index element paling akhir masuk. • Pada linked list : top akan menyimpan alamat node yang paling akhir ditambahkan.
Ilustrasi stack dengan array
-1
Top = 0
Top = 1
Top = 1
Top = 2
Top = 0
-1
Ilustrasi Stack dengan Linked List
Latihan Misal L adalah array. Gambarkan proses Stack untuk tiap operasi berikut dan tuliskan hasil akhirnya jika top menunjuk pada data f : L = {a,b,c,d,e,f} pop(); pop(); push(z); push(y); pop(); push(w);
Operasi pada Stack 1. 2. 3. 4. 5. 6. 7.
Deklarasi Inisialisasi Cek kosong Cek penuh Penambahan Pengambilan Pengaksesan
(1) Deklarasi • Proses yang harus dilakukan pertama kali adalah deklarasi/menyiapkan tempat. • Langkah yang harus dilakukan adalah : – Deklarasi class – Deklarasi struktur data (menggunakan array atau linked list) – Deklarasi pointer top
Deklarasi Stack dengan Array 1. Pembuatan class contoh :
2. Pembuatan variabel top : int top; 3. Pembuatan variabel untuk menampung panjang array : int array_size; (mendeklarasikan variabel bernama array_size dengan tipe integer)
4. Pembuatan variabel Array : int tumpukan[]; (mendeklarasikan variabel array bernama tumpukan dengan tipe integer)
Program Deklarasi (Array)
Deklarasi Stack dengan Linked-list 1. Pembuatan class stack contoh :
2. Pembuatan class Node 3. Pembuatan variabel head, tail dan top bertipe Node. Ketiga variabel ini dideklarasikan pada class Stack Node head,tail,top;
Contoh Class Node
Program Deklarasi (StackLinkedList.java)
(2) Inisialisasi • Merupakan proses pemberian nilai awal. • Pada Array : 1. Pembentukan obyek array beserta ukurannya. tumpukan = new int[10]; (pembentukan obyek array yang memiliki 10 element, dan alamat obyek akan disimpan pada variabel bernama tumpukan)
2. Pemberian nilai awal pada variabel top=-1. int top=-1;
Program Inisialisasi (Array)
(2) Inisialisasi...........(lanjutan) • Pada Linked List: Proses inisialisasi dilakukan dengan memberikan nilai awal pada variabel head, tail dan top dengan nilai null. head = tail = top = null;
Program Inisialisasi (Linked List)
(3) Cek Kosong • Operasi yang digunakan untuk mengecek kondisi stack dalam keadaan kosong. • Caranya : melihat nilai top. Jika nilainya sama seperti ketika inisialisasi berarti stack dalam kondisi kosong (top =-1 atau top=null). • Operasi ini harus dapat mengembalikan nilai true jika stack kosong dan false jika sebaliknya.
Program “isEmpty” (Array)
Program “isEmpty” (Linked List)
(4) Cek Penuh • Operasi yang hanya dapat diterapkan pada stack yang menggunakan array. • Operasi ini digunakan untuk mengecek kondisi stack dalam keadaan penuh. • Caranya : melihat nilai top. Jika nilai top sudah menunjuk n-1 (dimana n adalah ukuran array) maka dapat diindikasikan stack sudah dalam kondisi penuh. • Operasi ini harus dapat mengembalikan nilai true jika stack penuh dan false jika sebaliknya.
Program “isFull” (Array)
(5) Operasi POP • Pop adalah proses pengambilan data pada stack. • Ketika pop terjadi, element pada stack akan berkurang, yaitu element yang paling akhir ditambahkan. • Sehingga posisi pointer top juga akan bergeser : – Pada array : top di-decrement – Pada linked list : top menunjuk ke node sebelum node yang dihapus.
(5) Operasi POP...........(lanjutan) • Langkah-langkah : 1. Pengecekan stack dalam kondisi kosong dengan memanggil method isEmpty(). Jika nilai yang dikembalikan true maka pop tidak bisa dilakukan (penangkapan error oleh exception handling). Jika nilai yang dikembalikan false maka akan dilakukan langkah berikutnya (langkah 2 dan 3). 2. Data dari element paling belakang akan menjadi return value (nilai yang dikembalikan). 3. Pergeseran posisi top.
Program Pop (Array)
• Untuk menggunakan StackException() harus disertakan import package dari java.util.*
Program Pop (Linked List)
Program removeLast
(6) Operasi Push • Push adalah proses penambahan element pada stack. • Ketika push terjadi, element pada stack akan bertambah 1. • Posisi pointer top akan bergeser menunjuk pada element baru yang ditambahkan. – Pada array : top akan di-increment. – Pada linked list : top akan menunjuk ke node baru yang ditambahkan
(6) Operasi PUSH...........(lanjutan) • Langkah-langkah : 1. Penambahan element baru pada bagian belakang stack. 2. Pergeseran posisi top. • Khusus untuk array, terlebih dahulu harus dicek kondisi stack penuh dengan memanggil method isFull(). Jika nilai yang dikembalikan true maka bisa ditampilkan pesan kesalahan atau dilakukan resizing array.
Program Push (Array)
Program Rezising()
Program Push (Linked List)
Program addLast
(7) Operasi peek • Peek adalah proses pengaksesan element yang ditunjuk oleh top(yaitu element yang terakhir kali ditambahkan). • Operasi ini berbeda dengan pop karena tidak disertai dengan penghapusan data yang ada hanya pengaksesan (pengembalian data saja).
Program Peek (Array)
Program Peek (Linked List)
Penting! • Untuk linked list, jika operasi push dilakukan dari depan (addFirst) maka operasi pop juga dilakukan dari belakang (removeFirst). Sebaliknya, jika operasi push dari belakang (addLast) maka operasi pop juga dilakukan dari belakang (removeLast).
Contoh Penerapan Stack • • • •
Konversi Desimal ke Biner Notasi Polish Menara Hanoi Rat In a Maze
Latihan : implementasi stack • Konversi Bilangan Desimal ke Biner 1. Ambil sisa pembagian variable bilangan dengan angka 2, kemudian simpan dalam variable sisa. Kemudian simpan isi variable sisa ke dalam stack. 2. Bagi variable bilangan dengan angka 2. 3. Ulangi langkah 1 dan 2 selama bilangan tidak 0. Jika variable bilangan telah bernilai 0 maka lanjutkan ke langkah 4, 4. Lakukan perulangan untuk langkah 5 dan 6 selama stack masih mempunyai isi (tidak kosong). 5. ambil (pop) nilai yang ada di stack simpan di variable data. 6. Tulis isi variable data ke layar . 7. Selesai.
Implementasi Stack (Notasi Polish)
Notasi Polish (1) • Menggubah notasi infix menjadi notasi postfix. • Contoh : A+B (infix) AB+ (postfix)
Algoritma • Misal : Q = ekspresi matematika yang ditulis dalam notasi infix P = penampung ekspresi matematika dalam notasi postfix
Algoritma 1. Push tanda “(“ ke stack dan tambahkan tanda “)” di sentinel di Q. 2. Scan Q dari kiri ke kanan, kemudian ulangi langkah c s.d f untuk setiap elemen Q sampai stack Q kosong. 3. Jika yang discan adalah operand, maka tambahkan ke P 4. Jika yang discan adalah “(“ maka push ke stack 5. Jika yang discan adalah “)” maka pop isi stack sampai ditemukan tanda “(“, kemudian tambahkan ke P sedangkan tanda “(“ tidak disertakanke P. 6. Jika yang discan adalah operator, maka : - Jika elemen paling atas dari stack adalah operator yang mempunyai tingkatan sama atau lebih tinggi dari operator yang discan, maka pop operator tsb dan tambahkan ke P. - Push operator tersebut ke stack.
7. Keluar
Contoh Q=A+(B*C -(D/E^F)*G)*H
Penyelesaian Q=A+(B*C -(D/E^F)*G)*H >> setelah ditambahkan tanda “)” pada notasi sehingga terdapat 20 simbol sbb :
Penyelesaian
Penyelesaian • Hasil akhir : Dari proses di atas didapatkan notasi postfix Q = ABC*DEF^/G*-H*+
Notasi Polish (2) • Menghitung ekspresi matematika yang disusun dalam notasi postfix. • Contoh : 2,5,* (postfix) Hasil : 10
Algoritma • Misal : P adalah ekspresi matematika yang ditulis dalam notasi postfix. variable value sebagai penampung hasil akhir.
Algoritma 1. Tambahkan tanda “)” pada sentinel di P 2. Scan P dari kiri ke kanan, ulangi langkah c dan d untuk setiap elemen P sampai ditemukan sentinel. 3. Jika yang discan adalah operand, maka push ke stack. 4. Jika yang discan adalah operator (sebut opr1), maka
Pop 1 buah elemen teratas dari stack, simpan dalam variable var1. Pop 1 buah elemen teratas dari stack, simpan dalam variable var2. Hitung variable (var2 opr1 var1), simpan hasil di variable hitung. Push variable hitung ke stack.
5. Pop isi stack dan simpan di variable value. 6. Keluar.
Contoh Kasus • P = 5, 2, 6, +, *, 12, 4, /, -
Penyelesaian • P = 5, 2, 6, +, *, 12, 4, /, • Tambahkan tanda “)”pada sentinel P sehingga
P = 5, 2, 6, +, *, 12, 4, /, -, )
Didapatkan 10 simbol yaitu :
Penyelesaian
Hasil : Didapatkan Bilangan 37
Operator Priority ^ /, *
Pangkat, akar
+, -
Penambahan, pengurangan
Pembagian, perkalian
Latihan 1. Ubah notasi infix berikut ke dalam bentuk notasi postfix : A+((B*C/D)-(E^F)) M*(N^O)/P-(Q+R) (R*S+T)^U/(V-W+X)
Latihan 2. Hitung ekspresi matematika berikut yang disusun dalam bentuk postfix : • 2,2,3,+,*,3,2,-,* • B,2,^, 4, –, a, *, c, *, 2, a, *, /, p, q, *, a, b, +, /, +
Pustaka • Sartaj Sahni, Presentation L5 & L10 • Jokonowo, Bambang S.Si, “Pemrograman Berorientasi Obyek”, Pusat pengembangan bahan ajar UMB, 2006. • Noviyanto, “Pemrograman Berorientasi Obyek (PBO) – Array”, 2005 • Nugroho, Adi, “Algoritma dan Struktur Data Dalam Bahasa Java”, ANDI Yogyakarta, 2008. • Michaell Waite, ”Data Structures and Algorithms in Java”, SAMS, 2001
